11
$\begingroup$

I understand that a reversible computer does not dissipate heat through the Landauer's principle whilst running - the memory state at all times is a bijective function of the state at any other time.

However, I have been thinking about what happens when a reversible computer initializes. Consider the state of the physical system that the memory is built from just before power up and initialization. By dint of the reversibility of underlying microscopic physical laws, this state stay encoded in the overall system's state when it is effectively "wiped out" as the computer initialized and replaces it with a state representing the initialized memory (set to, say, all noughts).

So it seems to me that if $M$ bits is the maximum memory a reversible algorithm will need to call on throughout its working, by the reasoning of Landauer's principle, ultimately we shall need do work $M\, k\,T\,\log 2$ to "throw the excess entropy out of the initialized system".

Question 1: Is my reasoning so far right? If not, please say why.

Now, specializing to quantum computers, this seems to imply some enormous initialization energy figures. Suppose we have a system with $N$ qubits, so the quantum state space has $2^N$ basis states. Suppose further that, for the sake of argument, the physics and engineering of the system is such that the system state throughout the running of the system only assumes "digitized" superpositions, $i.e.$ sums of the form:

$$\frac{1}{\sqrt{\cal N}}\sum_{j\in 1\cdots 2^N} x_j \,\left|\left.p_{1,j},p_{2,j},\cdots\right>\right.$$

where $x_j, \;p_{k,j}\in{0,1}$ and ${\cal N}$ the appropriate normalization. To encode the beginning state that is wiped out at power up and initialization, it seems to me that the Landauer-principle-behested work needed is $2^N \,k\,T\,\log 2$. This figure reaches 6 000kg of energy (about humanity's yearly energy consumption) at around 140 qubits, assuming we build our computer in deep space to take advantage of, say, 10K system working temperature.

Question 2: Given that we could build a quantum computer with 140 qubits in "digital" superpositons as above, do we indeed need such initialization energies?

One can see where arguments like this might go. For example, Paul Davies thinks that similar complexity calculations limit the lower size of future quantum computers because their complexity (information content) will have to respect the Bekestein Bound. P.C.W. Davies, "The implications of a holographic universe for quantum information science and the nature of physical law", Fluctuation and Noise Lett 7, no. 04, 2007 (see also http://arxiv.org/abs/quantph/0703041)

Davies points out that it is the Kolmogorov complexity that will be relevant, and so takes this as an indication that only certain "small" subspaces of the full quantum space spanned by a high number of qubits will be accessible by real quantum computers. Likewise, in my example, I assumed this kind of limitation to be the "digitization" of the superposition weights, but I assumed that all of the qubits could be superposed independently. Maybe there would be needfully be correlations between the superpositions co-efficients in real quantum computers.

I think we would hit the Landauer constraint as I reason likewise, but at a considerably lower number of qubits.

Last Question: Am I applying Landauer's principle to the quantum computer in the right way? Why do my arguments fail if they do?*

$\endgroup$
  • 1
    $\begingroup$ Interestingly, I found a paper ("unfortunately" in French), here, which states , that in the case of a hybrid optomechanic system (See fig $2$ page $7$, fig $5$ page $10$), the work necessary to initialize a qbit is proportionnal to the Rabi frequency, which plays the role of a temperature (formula $23$ page $12$) $\endgroup$ – Trimok Nov 2 '13 at 10:04
  • $\begingroup$ @Trimok Ca marche bien pour moi! How very interesting indeed, thanks heaps. $\endgroup$ – Selene Routley Nov 2 '13 at 11:57
  • 4
    $\begingroup$ Yes, no, and no. Initializing one qubit dissipates $kT$ of energy, and thus, initializing N qubits dissipates an energy of $NkT$. (Note that if the energy would not scale linearly with the number of qubits, this would likely give rise to all kind of contradictions!) This is closely related to the question whether $N$ qubits "contain" $N$ bits or $2^N$ bits of information (and typically $N$ is the more appropriate answer) -- e.g., arxiv.org/abs/quant-ph/0507242 contains some arguments about that. $\endgroup$ – Norbert Schuch Nov 2 '13 at 12:55
  • 2
    $\begingroup$ There is an answer at physicsoverflow.org/10366 $\endgroup$ – Arnold Neumaier Jul 17 '15 at 7:55
  • 1
    $\begingroup$ @ArnoldNeumaier Thanks Arnold. I think Ron is right - I need to think on it a bit. $\endgroup$ – Selene Routley Jul 17 '15 at 8:04
2
$\begingroup$

No, the reasoning is wrong. When you need a N-qubit state, no difference entangled or not, you just initialize N qubits and then apply a unitary transformation (reversible). So, entropy produced during the initialization is proportional to the amount of information, without exponents.

For explanation of the “how many states do N qubits have” perennial question (and refuting respective misconceptions) refer to How many states can a n qubit quantum computer store? , although there are several places on the site where different users wrote nearly the same thing about superpositions/linear combinations.

$\endgroup$
  • $\begingroup$ What about reasoning above question 1? Why is that wrong? Is the energy not $M\,k\,T\,\log 2$? Also, could you please explain "you just initialize N qubits and then apply a unitary transformation (reversible). So, entropy produced during the initialization is proportional to the amount of information, without exponents." a bit more. I mean, the amount of information, if you like, is what I need. Are you saying that the initialisation work needed is simply $N\,k\,T\,\log 2$ for qubits as well? $\endgroup$ – Selene Routley Oct 3 '14 at 14:33
  • $\begingroup$ If one qubit costs some constant amount of entropy (of whichever value), then the entropy output is proportional to the n-r of qubits ∼ amount of information. The “physics and engineering… is such that the system state throughout the running of the system only assumes "digitized" superpositions bla-blah-blh” reasoning is based on arbitrary assumptions having nothing to do with quantum computing, and doesn’t prove anything. A system of N qubits admits $2^N$ states exactly, although these $2^N$ states can exist in coherent superposition. Any set of more than $2^N$ states is linearly dependent. $\endgroup$ – Incnis Mrsi Oct 16 '14 at 13:27
0
$\begingroup$

WetSavannaAnimal: I understand that a reversible computer does not dissipate heat through the Landauer's principle whilst running - the memory state at all times is a bijective function of the state at any other time.

That is not what Landauer said in his almost 60 year old paper: "Irreversibility and heat generation in the computing process", R. Landauer, IBM Journal of Research and Development, Volume 5 Issue 3, July 1961, Pages 183-191:

"Our main argument will be a refinement of the following line of thought. A simple binary device consists of a particle in a bistable potential well shown in Fig. 1. Let us arbitrarily label the particle in the left-hand well as the ZERO state. When the particle is in the right-hand well, the device is in the ONE state. Now consider the operation RESTORE TO ONE, which leaves the particle in the ONE state, regardless of its initial location. If we are told that the particle is in the ONE state, then it is easy to leave it in the ONE state, without spending energy. If on the other hand we are told that the particle is in the ZERO state, we can apply a force to it, which will push it over the barrier, and then, when it has passed the maximum, we can apply a retarding force, so that when the particle arrives at ONE, it will have no excess kinetic energy, and we will not have expended any energy in the whole process, since we extracted energy from the particle in its downhill motion. Thus at first sight it seems possible to RESTORE TO ONE without any expenditure of energy. Note, however, that in order to avoid energy expenditure we have used two different routines, depending on the initial state of the device. This is not how a computer operates. In most instances a computer pushes information around in a manner that is independent of the exact data which are being handled, and is only a function of the physical circuit connections.

Can we then construct a single time-varying force, $F(t)$, which when applied to the conservative system of Fig. 1 will cause the particle to end up in the ONE state, if it was initially in either the ONE state or the ZERO state? Since the system is conservative, its whole history can be reversed in time, and we will still have a system satisfying the laws of motion. In the time-reversed system we then have the possibility that for a single initial condition (position in the ONE state, zero velocity) we can end up in at least two places: the ZERO state or the ONE state. This, however, is impossible. The laws of mechanics are completely deterministic and a trajectory is determined by an initial position and velocity. (An initially unstable position can, in a sense, constitute an exception. We can roll away from the unstable point in one of at least two directions. Our initial point ONE is, however, a point of stable equilibrium.) Reverting to the original direction of time development, we see then that it is not possible to invent a single $F(t)$ which causes the particle to arrive at ONE regardless of its initial state.

If, however, we permit the potential well to be lossy, this becomes easy. A very strong positive initial force applied slowly enough so that the damping prevents oscillations will push the particle to the right, past ONE, regardless of the particle's initial state. Then if the force is taken away slowly enough, so that the damping has a chance to prevent appreciable oscillations, the particle is bound to arrive at ONE.

Figure 1
Figure 1 Bistable potential well. $x$ is a generalized coordinate representing quantity which is switched.

Notice the similarity to a particle in a box.

Here are a couple of distant analogies which store two states and do not consider "erasure":

  • Regenerative Braking

    • Electric cars, trains, elevators, etc. have two states, changing to the other state recovers much of the energy. Depending on which state is loaded more energy could be generated than is expended, for example taking empty trains uphill to an ore mine.

    This is so efficient that custom trains have been manufactured solely to carry cement blocks uphill as a means to store power which is regeneratively recovered on the return trip.

    ARES Shuttle

  • Flywheel Energy Storage

    "The energy efficiency (ratio of energy out per energy in) of flywheels, also known as round-trip efficiency, can be as high as 90%.".

Interesting, but far too distant an analogy, are the Atmos clock or the Beverly clock which has never been wound since it was built 155 years ago. If a computer could run on changes of atmospheric pressure and temperature it would certainly be efficient.

WetSavannaAnimal: Consider the state of the physical system that the memory is built from just before power up and initialization. By dint of the reversibility of underlying microscopic physical laws, this state stays encoded in the overall system's state when it is effectively "wiped out" as the computer initialized and replaces it with a state representing the initialized memory (set to, say, all noughts).

If any information could be extracted from the memory chips after you buy them, prior to the first time you power them up, what use would the sequence of digits written by the manufacturer's test equipment be to you; the record of the first (not by a longshot) state?

See also: "Can RAM retain data after removal?" on Security.SE.

Often computer memory is not initialized to zero.

Usually one would say "this is the start" (the initial state) and proceed forward from that point. Essentially you are asking "what happened prior the 'Big Bang', long before the atoms were incorporated into the computer I purchased".

WetSavannaAnimal: So it seems to me that if $M$ bits is the maximum memory a reversible algorithm will need to call on throughout its working, by the reasoning of Landauer's principle, ultimately we shall need to work $M k_T log2$ to "throw the excess entropy out of the initialized system".

That's the unobtainable theoretical minimum. See Koomey's Law:

"Latest studies indicate that Koomey's Law (the number of computations per joule of energy dissipated) has slowed to doubling every 2.6 years$^{[12]}$.

By the second law of thermodynamics and Landauer's principle, irreversible computing cannot continue to be made more energy efficient forever. As of 2011, computers have a computing efficiency of about 0.00001%.$^{[13]}$ Assuming that the energy efficiency of computing will continue to double every 1.57 years, the Landauer bound will be reached in 2048. Thus, after about 2048, Koomey's law can no longer hold.

Landauer's principle, however, is not applicable to reversible computing. This and other 'beyond CMOS' future computing technologies as-yet undeveloped would represent entirely new efficiencies, beyond Koomey's Law.".

See also: "The physics of forgetting: Landauer's erasure principle and information theory" (Mar 19 2001), by M.B. Plenio and V. Vitelli, page 20:

"From the last section we remember that the amount of classical information invested in the creation of the state $\hat{\rho}$ was never smaller than the von Neumann entropy $S(\hat{\rho})$ a value which can always be achieved. This left open the question how much classical information is actually still accessible after the creation of $\hat{\rho}$. Having seen above, that the entropy of erasure of a quantum state $\hat{\rho}$ can be as small as the von Neumann entropy we conclude from Landauer’s principle, that the accessible information in the state $\hat{\rho}$ cannot be larger than its von Neumann entropy. Therefore it becomes clear that the only possible quantity to describe the classical information content of a mixed state that has been prepared from an ensemble of pure states is given by the von Neumann entropy.".

Note that gdb and the rr project permit reverse execution of a program. This has no relation to Landauer's principle. One thing that was discovered is that since the program was not written with the intention of executing in reverse that some operations do not behave as expected.

WetSavannaAnimal: Question 1: Is my reasoning so far right? If not, please say why.

Done, but: "... To encode the beginning state that is wiped out at power up and initialization, it seems to me ...". The "zero" is not "0".

WetSavannaAnimal: Question 2: Given that we could build a quantum computer with 140 qubits in "digital" superpositons as above, do we indeed need such initialization energies?

The von Neumann entropy produced by a heat bath such that the thermal equilibrium state of the system is $\hat{\rho}$, i.e. $min \left\{ \Delta S_{tot} \right \} = S(\hat{\rho}) = -Tr \left \{ \hat{\rho} \, log \, \hat{\rho} \right \}$ which equals the von Neumann entropy of $\hat{\rho}$. That equation restates Landauer’s principle for quantum systems in which classical information is encoded.

See also:

"Viewpoint: Landauer Principle Stands up to Quantum Test" (May 21, 2018) in APS Physics 11, 49, by Massimiliano Esposito:

"... the quantum Landauer principle assumes that the qubit is initially uncorrelated with the equilibrated reservoir. This assumption is valid in the method Feng’s team used to prepare the qubit $^{[4]}$ or when the interaction between the qubit and the reservoir is weak. However, formulating second laws for correlated initial conditions is harder and remains an active field of research.

[4] L. L. Yan, T. P. Xiong, K. Rehan, F. Zhou, D. F. Liang, L. Chen, J. Q. Zhang, W. L. Yang, Z. H. Ma, and M. Feng, “Single-Atom Demonstration of the Quantum Landauer Principle", Phys. Rev. Lett. 120, 210601 (2018).

Bloch Sphere

WetSavannaAnimal: Last Question: Am I applying Landauer's principle to the quantum computer in the right way? Why do my arguments fail if they do?

I think I covered everything above, but implementing most logic gates requires more than one qubit as does creating a reversible logic.

See: "Reducing Quantum Cost in Reversible Toffoli Circuits" (Oct 20 2011), by Marek Szyprowski and Pawel Kerntopf:

"Recently, reversible circuit synthesis has been intensively studied. One of the problems that has not been solved for a long time was exact minimization of gate count (GC) in 4-bit circuits. Finally, last year a tool of practical usage for finding optimal gate count Toffoli networks for any 4-variable function was developed. However, not much work has been done yet on exact minimization of quantum cost (QC) in 4-bit circuits. This paper presents an application of the above mentioned tool to reducing QC of 4-bit reversible circuits. It is shown that for benchmarks and for designs taken from recent publications it is possible to obtain savings in QC of up to 74% comparing with previously known circuits.".

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.