Quantum Circuit - Reversible Circuits

Reversible Circuits

Again we consider first reversible classical computation. Conceptually there is no difference between a reversible n bit circuit and a reversible n bit logical gate: it is just an invertible function on the space of n bit data. However, as we mentioned in the previous section, for engineering reasons we would like to have a small number of reversible gates, that can be put together to assemble any reversible circuit. To explain this assembly process, suppose we have a reversible n bit gate f and a reversible m bit gate g. Putting them together means producing a new circuit by connecting some set k < n of the outputs of f to some set of k inputs of g as in the figure below. In that figure n=5, k =3 and m = 7. The resulting circuit is also reversible and operates on n+m-k bits.

We will refer to this scheme as a classical assemblage; (Remark: this concept corresponds to a technical definition in Kitaev's pioneering paper cited below.) In composing these reversible machines, it is important to ensure that the intermediate machines are also reversible. This condition assures that intermediate garbage is not created (the net physical effect would be to increase entropy, which is one of the motivations for going through this exercise). Now it is possible to show that the Toffoli gate is a universal gate. This means that given any reversible classical n bit circuit h, we can construct a classical assemblage of Toffoli gates in the above manner to produce an n+m bit circuit f such that

where there are m underbraced zeroed inputs and

.

Notice that the end result always has a string of m zeros as the ancilla bits! No rubbish is ever produced, and so this computation is indeed one that, in a physical sense, generates no entropy. This issue is carefully discussed in Kitaev's article.

It follows immediately from this result that any function f (bijective or not) can be simulated by a circuit of Toffoli gates. Obviously, if the mapping fails to be injective, at some point in the simulation (for example as the last step) some garbage has to be produced.

For quantum circuits a similar composition of qubit gates can be defined. That is associated to any classical assemblage as above, we can produce a reversible quantum circuit when in place of f we have an n qubit gate U and in place of g we have an m qubit gate W. See illustration below:

The fact that connecting gates this way gives rise to a unitary mapping on n+m-k qubit space is an easy check, which should not concern the non-expert reader. It should also be noted that in a real quantum computer the physical connection between the gates is a major engineering challenge, since it is one of the places where decoherence may actually occur.

There is also a universality theorem for sets of well known gates; such a universality theorem exists for instance, for the pair consisting of the single qubit phase gate U_θ mentioned above for some reasonable value of θ together with the 2 qubit CNOT gate W_CNOT). However the universality theorem is somewhat weaker in the case of quantum computation, namely that any reversible n qubit circuit can be approximated arbitrarily well by circuits assembled from these two elementary gates. Note that there are uncountably many possible single qubit phase gates, one for every possible angle θ, so uncountably many of these gates cannot be represented by any finite circuit constructed from {U_θ, W_CNOT)}.