6
$\begingroup$

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 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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Warren Schudy Oct 25 '10 at 21:54
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Antonio Valerio Miceli-Barone Oct 25 '10 at 23:41
  • 1
    $\begingroup$ 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 arxiv.org/abs/quant-ph/9908043 by Seth Lloyd. $\endgroup$ – Joe Fitzsimons Oct 26 '10 at 0:09
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Oct 26 '10 at 1:00
  • $\begingroup$ Good point Joe: 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. $\endgroup$ – Artem Kaznatcheev Oct 26 '10 at 1:12
  • 2
    $\begingroup$ 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 ;-) $\endgroup$ – Joe Fitzsimons Oct 26 '10 at 1:14

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.