<p>I tend to think of energy of the Hamiltonian as setting the time scale for what we count as 'steps' of the computation. An analogue in standard complexity would be on deciding what we count as a single operation. Technically we can count any $O(1)$ sub-routine as a single operation, but what we decide sets the exact linear factors we will see in our runtime. Same with the norm of the Hamiltonian in adiabatic computation (and the specific universal finite gate set in quantum (or classical) circuits -- or changing from bits to trits in register model). The above approach of course produces only constant factors that don't matter.</p>

CC BY-SA 2.5
2010-10-26T01:00:27.203Z
The comment about time dilation is incorrect. If you accelerate the computer and then decelerate it, it will have run slower not faster than the lab frame.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-26T01:12:41.530Z
Good point Joe: http://en.wikipedia.org/wiki/Twin_paradox

My bad on not paying attention, I really should send myself away and not the computer. Will remove that part of the answer for now.
Artem Kaznatcheev
CC BY-SA 2.5
2010-10-26T01:14:40.000Z
Yes, that way round works. Unfortunately you come back to find everyone you knew dead, and I suspect the problem you were trying to solve seems somehow less important ;-)
Joe Fitzsimons
CC BY-SA 2.5
2010-10-26T00:56:53.117Z
2010-10-26T01:14:18.940Z
2010-10-26T01:14:18.940Z
Artem Kaznatcheev
<p>Basically, the computation is reversible, so you are not actually using energy. However, the rate at which a computation progresses is generally proportional to the energy gap within the system. In the case of adiabatic quantum computation, the rate at which you can transition between ground states of the initial and final system is determined by the energy gap between the ground state and the low lying excited levels of the system. Thus the energy gap in the Hamiltonian (the total energy operator) is what determines the rate of computation, and so scaling up the energy levels involved allows the computation to be performed more quickly, even though the process does not actually consume the energy.</p>

<p>You might be interested in looking at the <a href="http://en.wikipedia.org/wiki/Margolus%E2%80%93Levitin_theorem">Margolus-Levitin</a> theorem, which gives limits for the rate of computation by imposing a lower bound on the time taken for a system to transition to an orthogonal state in terms of the energy gap present in the system. This applies more generally than simply to adiabatic quantum computing.</p>

<p>In general, you tend to get a linear trade-off between energy scale and time. One way to see where this comes from is simply to think about the case of a constant Hamiltonian. In that case, the time evolution operator is $e^{-iHt}$. Clearly multiplying $H$ by some constant $k$ and dividing $t$ by $k$ leads to the same operator, and hence the same evolution of the system. You can do this more generally, with a potentially time dependent Hamiltonian by looking at the Schroedinger equation: $i \hbar \frac{\partial}{\partial t} \mid \Psi \rangle = H \mid \Psi \rangle$. Replacing $H$ with $kH$ and $t$ with $\frac{t}{k}$ we obtain the same equation.</p>

CC BY-SA 2.5
2010-10-25T23:41:30.420Z
Thanks for the reference to the Margolus-Levitin theorem, but I fell that this still doesn't my question. I mean, in principle, you could build a system with arbitrary high energy separation and get arbitrary an low run time, but I suppose (I'm not a physicist) that doing so becomes technically more and more difficult, and eventually practically impossible to go beyond some energy separation level. Does that difficulty depend only on the specific implementation details or is there some fundamental limit that is independent of the implementation details?
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-10-26T00:09:55.053Z
Yes, there is a fundamental limit. Eventually you go beyond the energy density required to form a black hole, which then creates an event horizon, meaning you don't get the information back out (well without waiting for the black hole to evaporate). See for example http://arxiv.org/abs/quant-ph/9908043 by Seth Lloyd.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-25T22:04:17.940Z
2010-10-25T22:26:29.977Z
2010-10-25T22:26:29.977Z
Joe Fitzsimons
<p>I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic.</p>

<p>In <a href="http://arxiv.org/abs/quant-ph/0405098">Adiabatic Quantum Computation is Equivalent to Standard
Quantum Computation</a> the autors mention a tradeoff between runtime and energy:</p>

<p>"Observe that we have chosen our definition of running time to be $T · \max_s \lVert H(s)\rVert$ and not T.
Notice that if the Hamiltonians are multiplied by some factor, this divides the bound of Equation
2, and hence T, by the same factor. Hence, if the running time is defined to be T one would be able
to achieve arbitrarily small running times, by multiplying the Hamiltonians by large factors. Our
definition, on the other hand, is invariant under a multiplication of the Hamiltonian by an overall
factor, and so takes into account the known physical trade-off between time and energy.5</p>

<p>5This trade-off between time and the norm of the Hamiltonian (namely, the energy), is manifested in Schrödinger’s
equation whose solution does not change if time is divided by some factor and at the same time the Hamiltonian is
multiplied by the same factor."</p>

<p>But if I understand correctly, adiabatic quantum computation is completely reversible: by inverting the direction of time the system evolves back from the final state to the initial state.</p>

<p>Moreover, any adiabatic quantum computation process can be implemented (with arbitrary precision) in the conventional quantum circuit model, where all the gates are unitary and thus reversible.</p>

<p>According to Landauer's principle, reversible computation could be, in principle, executed without any energy consumption.</p>

<p>So my question is, what exactly the time-energy tradeoff in the choice of Hamiltonians for adiabatic quantum computation means?</p>

CC BY-SA 2.5
2010-10-25T21:54:11.790Z
Who said the energy was expended? The time-energy tradeoff applies for energy present in the system. In a noise-free world you would get that energy back when you're done with the computation, but you still would have to invest it in the computation.
Warren Schudy
<quantum-computing><physics>
Energy cost of adiabatic quantum computation
Antonio Valerio Miceli-Barone
# Energy cost of adiabatic quantum computation

(Asked by: username_0 on 2010-10-25)

I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic.

In [Adiabatic Quantum Computation is Equivalent to Standard
Quantum Computation](http://arxiv.org/abs/quant-ph/0405098) the autors mention a tradeoff between runtime and energy:

"Observe that we have chosen our definition of running time to be $T · \max\_s \lVert H(s)\rVert$ and not T.
Notice that if the Hamiltonians are multiplied by some factor, this divides the bound of Equation
2, and hence T, by the same factor. Hence, if the running time is defined to be T one would be able
to achieve arbitrarily small running times, by multiplying the Hamiltonians by large factors. Our
definition, on the other hand, is invariant under a multiplication of the Hamiltonian by an overall
factor, and so takes into account the known physical trade-off between time and energy.5

5This trade-off between time and the norm of the Hamiltonian (namely, the energy), is manifested in Schrödinger’s
equation whose solution does not change if time is divided by some factor and at the same time the Hamiltonian is
multiplied by the same factor."

But if I understand correctly, adiabatic quantum computation is completely reversible: by inverting the direction of time the system evolves back from the final state to the initial state.

Moreover, any adiabatic quantum computation process can be implemented (with arbitrary precision) in the conventional quantum circuit model, where all the gates are unitary and thus reversible.

According to Landauer's principle, reversible computation could be, in principle, executed without any energy consumption.

So my question is, what exactly the time-energy tradeoff in the choice of Hamiltonians for adiabatic quantum computation means?

**Tags:** quantum-computing, physics
> **Comments:**
> **username_1**: Who said the energy was expended? The time-energy tradeoff applies for energy present in the system. In a noise-free world you would get that energy back when you're done with the computation, but you still would have to invest it in the computation.  

---

## 2 answers

### Answer by username_3 on 2010-10-25. Score: 6 | Accepted answer

Basically, the computation is reversible, so you are not actually using energy. However, the rate at which a computation progresses is generally proportional to the energy gap within the system. In the case of adiabatic quantum computation, the rate at which you can transition between ground states of the initial and final system is determined by the energy gap between the ground state and the low lying excited levels of the system. Thus the energy gap in the Hamiltonian (the total energy operator) is what determines the rate of computation, and so scaling up the energy levels involved allows the computation to be performed more quickly, even though the process does not actually consume the energy.

You might be interested in looking at the [Margolus-Levitin](http://en.wikipedia.org/wiki/Margolus%E2%80%93Levitin_theorem) theorem, which gives limits for the rate of computation by imposing a lower bound on the time taken for a system to transition to an orthogonal state in terms of the energy gap present in the system. This applies more generally than simply to adiabatic quantum computing.

In general, you tend to get a linear trade-off between energy scale and time. One way to see where this comes from is simply to think about the case of a constant Hamiltonian. In that case, the time evolution operator is $e^{-iHt}$. Clearly multiplying $H$ by some constant $k$ and dividing $t$ by $k$ leads to the same operator, and hence the same evolution of the system. You can do this more generally, with a potentially time dependent Hamiltonian by looking at the Schroedinger equation: $i \hbar \frac{\partial}{\partial t} \mid \Psi \rangle = H \mid \Psi \rangle$. Replacing $H$ with $kH$ and $t$ with $\frac{t}{k}$ we obtain the same equation.

> **Comments:**
> **username_0**: Thanks for the reference to the Margolus-Levitin theorem, but I fell that this still doesn't my question. I mean, in principle, you could build a system with arbitrary high energy separation and get arbitrary an low run time, but I suppose (I'm not a physicist) that doing so becomes technically more and more difficult, and eventually practically impossible to go beyond some energy separation level. Does that difficulty depend only on the specific implementation details or is there some fundamental limit that is independent of the implementation details?  
> **username_3**: Yes, there is a fundamental limit. Eventually you go beyond the energy density required to form a black hole, which then creates an event horizon, meaning you don't get the information back out (well without waiting for the black hole to evaporate). See for example http://arxiv.org/abs/quant-ph/9908043 by Seth Lloyd.  

---

### Answer by username_2 on 2010-10-26. Score: 2

I tend to think of energy of the Hamiltonian as setting the time scale for what we count as 'steps' of the computation. An analogue in standard complexity would be on deciding what we count as a single operation. Technically we can count any $O(1)$ sub-routine as a single operation, but what we decide sets the exact linear factors we will see in our runtime. Same with the norm of the Hamiltonian in adiabatic computation (and the specific universal finite gate set in quantum (or classical) circuits -- or changing from bits to trits in register model). The above approach of course produces only constant factors that don't matter.

> **Comments:**
> **username_3**: The comment about time dilation is incorrect. If you accelerate the computer and then decelerate it, it will have run slower not faster than the lab frame.  
> **username_2**: Good point Joe: http://en.wikipedia.org/wiki/Twin_paradox  My bad on not paying attention, I really should send myself away and not the computer. Will remove that part of the answer for now.  
> **username_3**: Yes, that way round works. Unfortunately you come back to find everyone you knew dead, and I suspect the problem you were trying to solve seems somehow less important ;-)  

---

