Reversible Computations

The requirements for reversible gates have been shown above. Without such gates the quantum system would radiate heat and the quantum interference which is essential for the correct operation of the system would stop working. However it is not enough to simply have reversible gates - the entire computation must be reversible. What's more, we cannot copy or destroy values within the system without it decohering. The classical instructions X:=Y and X:=0 lose information as the original value of X is obliterated by the instruction. Thus they are not reversible, and so could never be used in a quantum computation algorithm. Instead we need to replace those instructions with variations such as X:=X + Y (where we know that the original value of X was 0) and X = X - Z (where we have computed that the value of X is Z).

Thankfully it has been shown [Lecerf 1963, Bennet 1973] that any deterministic computation can be made reversible.

QUANTUM GATE ARRAYS

Gate arrays are acyclic circuits. If we are allowed a small probability of error, quantum gate arrays and quantum Turing machines can compute the same functions in polynomial time [Yao 1993].

It's far easier design a reversible circuit if it is gate array and so this tend to be the form of quantum circuit used most frequently in the literature.