22
$\begingroup$

In order to check my understanding, I would like to share some thoughts about energy requirements of computation. This is a follow up to my previous question and might be related to Vinay's question about conservation laws.

It occourred to me that, from a thermodynamical point of view, running a computation can be considered, to some extent, analogue to moving a weight along an horizontal line: The only energy loss is due to frictional forces, which can be, in principle, made arbitrarly small.

In an ideal setting without dissipative forces (the mechanical analogue of a reversible computer), no energy expenditure is required at all. You still have to supply energy in order to accelerate the weight, but you can recover it all when decelerating it. The running time can be made arbitrarly small by investing enough energy (more precisely, if relativity is taken into account, running time is bounded from below by $d/c$, where $d$ is the distance).

Similarly, a reversible computer requires no energy expenditure but an energy investment that is recovered at the end of the computation, and running time can be made arbitrarly small by investing enough energy, up to relatvistic limits (as described in http://arxiv.org/abs/quant-ph/9908043 by Seth Lloyd).

There is, however, and energy cost associated with the construction of the computer. In general, this will depend on the implementation details, but I conjecture that we can state a lower bound for it:

Assume that our computer has three (classical or quantum) registers: Input, Output and Ancilla.
The Input and Output registers can be read and written to by the user, while the Ancilla register is inaccessible.
At the begining of each computation, the Ancilla register starts in a fixed (e.g. all zeros) state, and by the end of the computation it will have returned to the same fixed state. Thus, barring external noise, the Ancilla state needs to be initialized only once, when the computer is built.

Therefore, applying Landauer's principle, I conjecture that building a reversible computer with $n$ bits (or qubits) of Ancilla requires at least $n k_B T \ln2$ Joules of energy, where $k_B$ is the Boltzmann's constant and $T$ is the temperature of the environment where the system is being built.

Questions:

  1. Are the above considerations correct?

  2. What happens if a reversible computer is built in an evironment at temperature $T$ and then it is moved in an environment at temperature $T' < T$ ? I suppose that a truly reversible computer can't really be cooled. In principle, it should not even have a properly defined temperature, if I understand correctly.

  3. What happens if we consider an irreversible computer? An irreversible computer can perform the same computations using in general less ancilla bits, moreover, since it thermally interacts with its environment, we could arrange so that the initial Ancilla state is part of the ground state, hence we can initialize it by simply allowing it to cool, without supplying any energy. Of course, being irreversible, we have to pay an energy cost for each computation.

  4. (related to Kurt's answer to Vinay's question)
    In the mechanical analogy, I considered only movement along an horizontal line. If the weight was also lifted in the vertical direction, an additional energy expenditure would have been required (or energy would have been recovered if the weight was lowered). Is there a computational analogue of this vertical movement, and is there a quantity that gets consumed or produced by this process?

UPDATE:

It occurred to me that the energy cost required to build the computer, can be recovered, in principle completely (I think), when you dismantle the computer.

So, for each computation, you could build a special-purpose reversible computer that has just as many ancilla bit as required, add additional energy to set it in motion, wait for the computation to complete, and then dismantle the computer recovering all the invested energy. Thus you could define the energy investment of the computation as: $n_s k_B T \ln2 + n_t s$ where $n_s$ is the actual space complexity (number of ancilla bits), $n_t$ is the actual time complexity (number of time steps) and $s$ is the energy vs speed tradeoff term per time step, assuming a constant total runtime.

Any thoughts?

$\endgroup$
4
$\begingroup$

I think perhaps you may be over-reaching. As you point out your self, the construction of the computer itself could be made reversible, and so the energy investment in construction won't yield an interesting lower bound. Considering the ancillary register is an interesting idea, but I don't think it is quite as straight forward as you make it sound.

In particular, it is not necessary to initialise ever bit or qubit in the ancillary register. We can use a fault-tolerant construction to ensure that the probability of obtaining an incorrect result is bounded. Von Neumann provided such a construction for classical computing using majority gates which has a threshold of $\frac{5}{6}$ for the probability of obtaining the correct output from a gate, and in quantum computing this is a very active research area, where the best error thresholds are on the order of a few percent. This gives a threshold in terms of the polarization of the system (assuming the gates themselves are noiseless). However, if the decoding circuit is noisless, then the classical threshold moves to $\frac{1}{2}$, which seems to indicate that a large noisy ancillary system can be exploited by using the input/output system for decoding, independant of the polarization of the system.

In fact, there is a model of computation where the system is composed of a single quantum bit (qubit) together with an ancilla system which is not polarized (i.e. in a uniformly random state, which can be seen as the infinite temperature thermal state). Note that you can prepare such a state at finite temperature. This is known as the one clean qubit model. What's interesting is that this model is far from trivial, being believed to be sufficient to solve some classically intractable problems, while not being as powerful as a universal quantum computer. An example of this is this paper (arXiv:0707.2831) by Peter Shor and Stephen Jordan, showing that estimating Jones polynomials is complete for the model.

With this in mind, in general the ancilla system does not seem to need to be initialised to provide a computational advantage, which seems to undermine the key assumption you make. As such, I believe your conjecture is false.

$\endgroup$
  • $\begingroup$ Thanks for the answer. However, I don't quite understand how you can use fault-tolerant constructions to perform computation from uninitialized ancillas. Can you expand or provide some references, please? If I understand correctly, the majority gate is irreversible, and all the quantum fault-tolerant construction I've seen (but I'm not really an expert) require intermediate measurements, or some other kind of irreversible operations. If you simulate these operations with a reversible circuit you'll need further ancillas initialized to a known state. $\endgroup$ – Antonio Valerio Miceli-Barone Jun 4 '11 at 14:49
  • $\begingroup$ Thanks for the reference to the one clean qubit model. It seems to me that rather than the total number of qubits of the ancilla register, the entropy of its initial state is important. $\endgroup$ – Antonio Valerio Miceli-Barone Jun 4 '11 at 15:01
  • $\begingroup$ @Antonio: You can make any gate reversible by having it act on an ancilla, so it XORs the ancilla with the output of the function. You do -not- need these ancillae to be perfrectly polarized, as imperfect polarization is indistinguishable from measurement noise, against which most schemes are protected. As an aside, measurements are not a prerequisite for quantum fault-tolerance. $\endgroup$ – Joe Fitzsimons Jun 4 '11 at 21:34
  • $\begingroup$ As regards entropy as a measure, I don't see how this would work. In the one clean qubit model you are very close to maximal entropy, where as in the regular circuit model you have zero entropy. $\endgroup$ – Joe Fitzsimons Jun 4 '11 at 21:36
  • $\begingroup$ Do you have any reference to a reversible fault-tolerant scheme? $\endgroup$ – Antonio Valerio Miceli-Barone Jun 5 '11 at 10:03

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.