<p>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. </p>

<p>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.</p>

<p>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 (<a href="http://arxiv.org/abs/0707.2831v3" rel="nofollow">arXiv:0707.2831</a>) by Peter Shor and Stephen Jordan, showing that estimating Jones polynomials is complete for the model.</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-04T14:49:37.613Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-06-04T15:01:25.320Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-06-04T21:34:24.237Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2011-06-04T21:36:20.433Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2011-06-05T10:03:47.500Z
Do you have any reference to a reversible fault-tolerant scheme?
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-06-05T10:07:27.400Z
Regarding entropy, I mean the amount of entropy you have to remove from the ancilla register in order to initialize it, starting from a maximally mixed state. In the one clean qubit model it would be zero (in the definition I used the clean qubit would be the output register, so I'm not counting it in the ancilla register).
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-06-03T17:55:06.003Z
2011-06-03T17:55:06.003Z
Joe Fitzsimons
<p>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 <a href="https://cstheory.stackexchange.com/questions/2464/energy-cost-of-adiabatic-quantum-computation">question</a> and might be related to Vinay's <a href="https://cstheory.stackexchange.com/questions/3062/are-there-conservation-laws-in-complexity-theory">question about conservation laws</a>.</p>

<p>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. </p>

<p>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).</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/9908043" rel="nofollow noreferrer">http://arxiv.org/abs/quant-ph/9908043</a> by Seth Lloyd).</p>

<p>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:</p>

<p>Assume that our computer has three (classical or quantum) registers: <strong>Input</strong>, <strong>Output</strong> and <strong>Ancilla</strong>.<br>
The <strong>Input</strong> and <strong>Output</strong> registers can be read and written to by the user, while the <strong>Ancilla</strong> register is inaccessible.<br>
At the begining of each computation, the <strong>Ancilla</strong> 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 <strong>Ancilla</strong> state needs to be initialized only once, when the computer is built.</p>

<p>Therefore, applying <em>Landauer's principle</em>, I conjecture that building a reversible computer with $n$ bits (or qubits) of <strong>Ancilla</strong> 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.</p>

<p>Questions:</p>

<ol>
<li><p>Are the above considerations correct?</p></li>
<li><p>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' &lt; 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.</p></li>
<li><p>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 <strong>Ancilla</strong> 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.</p></li>
<li><p>(related to Kurt's answer to Vinay's question)<br>
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?</p></li>
</ol>

<p>UPDATE:</p>

<p>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.</p>

<p>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 <em>energy investment</em> 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.</p>

<p>Any thoughts?</p>

CC BY-SA 3.0
2011-04-12T13:30:45.307Z
You could look at Paul Vitányi's paper [Time, space, and energy in reversible computing](http://dx.doi.org/10.1145/1062261.1062335).
funkstar
CC BY-SA 2.5
2010-11-19T01:29:53.383Z
possibly related: 1. [how much computational power fits into a cubic centimeter](http://cstheory.stackexchange.com/questions/2758/how-much-computational-power-fits-into-a-cubic-centimeter) 2. [DNA algorithms and NP completeness](http://cstheory.stackexchange.com/questions/2703/dna-algorithms-and-np-completeness)
Kaveh
<cc.complexity-theory><big-picture><physics>
Energy considerations on computation
Antonio Valerio Miceli-Barone
# Energy considerations on computation

(Asked by: username_0 on 2010-11-19)

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](https://cstheory.stackexchange.com/questions/2464/energy-cost-of-adiabatic-quantum-computation) and might be related to Vinay's [question about conservation laws](https://cstheory.stackexchange.com/questions/3062/are-there-conservation-laws-in-complexity-theory).

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?

**Tags:** cc.complexity-theory, big-picture, physics
> **Comments:**
> **username_2**: possibly related: 1. [how much computational power fits into a cubic centimeter](http://cstheory.stackexchange.com/questions/2758/how-much-computational-power-fits-into-a-cubic-centimeter) 2. [DNA algorithms and NP completeness](http://cstheory.stackexchange.com/questions/2703/dna-algorithms-and-np-completeness)  
> **username_1**: You could look at Paul Vitányi's paper [Time, space, and energy in reversible computing](http://dx.doi.org/10.1145/1062261.1062335).  

---

## 1 answers

### Answer by username_3 on 2011-06-03. Score: 4 | Accepted answer

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](http://arxiv.org/abs/0707.2831v3)) 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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: @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.  
> **username_3**: 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.  
> **username_0**: Do you have any reference to a reversible fault-tolerant scheme?  
> **username_0**: Regarding entropy, I mean the amount of entropy you have to remove from the ancilla register in order to initialize it, starting from a maximally mixed state. In the one clean qubit model it would be zero (in the definition I used the clean qubit would be the output register, so I'm not counting it in the ancilla register).  

---

