It has long been known that to minimise the heat emitted by a deterministic computer during it's operation it is necessary to make the computation act in a logically reversible manner\cite{Lan61}. Such logically reversible operations require a number of auxiliary bits to be stored, maintaining a history of the computation, and which allows the initial state to be reconstructed by running the computation in reverse. These auxiliary bits are wasteful of resources and may require a dissipation of energy for them to be reused. A simple procedure due to Bennett\cite{Ben73} allows these auxiliary bits to be "tidied", without dissipating energy, on a classical computer. All reversible classical computations can be made tidy in this way. However, this procedure depends upon a classical operation ("cloning") that cannot be generalised to quantum computers\cite{WZ82}. Quantum computations must be logically reversible, and therefore produce auxiliary qbits during their operation. We show that there are classes of quantum computation for which Bennett's procedure cannot be implemented. For some of these computations there may exist another method for which the computation may be "tidied". However, we also show there are quantum computations for which there is no possible method for tidying the auxiliary qbits. Not all reversible quantum computations can be made "tidy". This represents a fundamental additional energy burden to quantum computations. This paper extends results in \cite{Mar01}.
It has long been known that to minimise the heat emitted by a deterministic computer during it's operation it is necessary to make the computation act in a logically reversible manner\cite{Lan61}. Such logically reversible operations require a number of auxiliary bits to be stored, maintaining a history of the computation, and which allows the initial state to be reconstructed by running the computation in reverse. These auxiliary bits are wasteful of resources and may require a dissipation of energy for them to be reused. A simple procedure due to Bennett\cite{Ben73} allows these auxiliary bits to be "tidied", without dissipating energy, on a classical computer. All reversible classical computations can be made tidy in this way. However, this procedure depends upon a classical operation ("cloning") that cannot be generalised to quantum computers\cite{WZ82}. Quantum computations must be logically reversible, and therefore produce auxiliary qbits during their operation. We show that there are classes of quantum computation for which Bennett's procedure cannot be implemented. For some of these computations there may exist another method for which the computation may be "tidied". However, we also show there are quantum computations for which there is no possible method for tidying the auxiliary qbits. Not all reversible quantum computations can be made "tidy". This represents a fundamental additional energy burden to quantum computations. This paper extends results in \cite{Mar01}.
The general computational process A suitably programmed quantum computer should act on a number x to produce another number f(x) for some specified function f . Appropriately interpreted, with an accuracy that increases with increasing k , we can treat such numbers as non-negative integers less than 2 k . Each integer is represented in the quantum computer by the corresponding computational-basis state of k Qbits. If we specify the numbers x as n -bit integers and the numbers f(x) as m -bit integers, then we shall need at least n + m Qbits: a set of n -Qbits, called the input register , to represent x , and another set of m -Qbits, called the output register , to represent f(x) . Qbits being a scarce commodity, you might wonder why we need separate registers for input and output. One important reason is that if f(x) assigns the same value to different values of x , as many interesting functions do, then the computation cannot be inverted if its only effect is to transform the contents of a single register from x to f(x) . Having separate registers for input and output is standard practice in the classical theory of reversible computation. Since quantum computers must operate reversibly to perform their magic (except for measurement gates), they are generally designed to operate with both input and output registers. We shall find that this dual-register architecture can also be usefully exploited by a quantum computer in some strikingly nonclassical ways.
Except for the NOT gate, all the other familiar classical gates are irreversible in the sense that we cannot uniquely reconstruct the input states from the output states. For example, OR, AND, NAND, NOR, etc. are irreversible. They all map a two-bit input state into a single bit output state. Thus one bit is erased during operation of each of these gates, and according to Landauer’s principle that requires dissipation of a minimum amount of energy. Now a simple question arises in our curious mind: Is it possible to avoid this loss of energy? The answer is yes. If we don’t erase any bit then we can circumvent this energy loss. Thus we need to map n bit input states to n bit output states. In addition, if a one-toone correspondence exists between the input states and the output states then only we will be able to uniquely reconstruct the input states from the output states. In such a case the gate is called reversible. For example, if we have f(00) = 00, f(01) = 10, f(10) = 01, f(11) = 11 then f represents a reversible gate. Quantum evolution operators are unitary so for every operator U we have an inverse operator U−1 = U†. Therefore, quantum evolution operators are the natural choice for the construction of energy efficient reversible gates. However, it is not the only choice. We can have classical reversible gates, too. Usually by reversible gates we refer to classical reversible gates, and quantum gates are specifically referred to as quantum gates. Reversible gates and quantum gates are similar but there exists a fundamental difference that reversible gates cannot accept superposition states (e.g. α|0〉 + β|1〉) as input states, whereas quantum gates can. Thus all quantum gates are essentially reversible but the converse is not true.
Reversible logic was originally proposed as a way to build classical computers with very low energy requirements. Its greatest impact so far has in fact been on the field of quantum computing, where it is used pervasively -- but for an entirely different purpose. Quantum interference effects offer the potential for speeding up certain classical calculations. But if state information is expelled from a quantum computer into the unmodeled environment -- as happens whenever an irreversible operation is performed -- then it becomes impossible to predict or control when interference will occur. Reversibility is necessary because it allows bits to be erased by uncomputing them rather than simply expelling them, preserving control over interference effects.
The relation between entropy and information has great significance for computation. Based on the strict reversibility of the laws of microphysics, Landauer (1961), Bennett (1973), Priese (1976), Fredkin and Toffoli (1982), Feynman (1985) and others envisioned a reversible computer that cannot allow any ambiguity in backward steps of a calculation. It is this backward capacity that makes reversible computing radically different from ordinary, irreversible computing. The proposal aims at a higher kind of computer that would give the actual output of a computation together with the original input, with the absence of a minimum energy requirement. Hence, information retrievability and energy efficiency due to diminished heat dissipation are the exquisite tasks of quantum computer technology.
An explicit algorithm for performing Schumacher's noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary strings. The algorithm, which adheres to the rules of reversible programming, is expressed in a high-level pseudocode language. It is implemented using O(n3) two- and three-bit primitive reversible operations, where n is the length of the qubit strings to be compressed. Also, the algorithm makes use of O(n) auxiliary qubits. Space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to O(\ensuremath{\surd}n) while maintaining a running time of O(n3) (albeit with a larger constant). This latter algorithm is of interest because it has a slightly smaller time-space product, which is considered to be the relevant figure of merit for efficiency in some physical models. \textcopyright{} 1996 The American Physical Society.
One of the most important features of the quantum computing circuits that distinguishes them from the traditional computational models is their full, physical and logical, reversibility at all stages of the calculations. This makes the large-scale architecture of potential quantum and classical reversible computers quite similar. The goal of this work is to analyze this similarity in the case of reversible superconducting logic circuits based on the recently suggested elementary gate, the nSQUID. Specifically, we present the results of numerical simulations and some limited measurements of a reversible 8-bit circular shift register fabricated at HYPRES, Inc., and working in the classical mode. The measured energy dissipation per bit operation per nSQUID is still about 20 times higher than the thermodynamic reversibility threshold of kBTIn 2 at T ap 4 K. We also discuss qualitatively operation of the reversible circuits of galvan- ically-coupled nSQUIDs in the quantum mode which provides the basis for implementation of "flying" superconducting qubits. Such qubits have several attractive features for Josephson-junction quantum logic devices beyond the single- or two-qubit circuits.