As an example, say you ran a computation on a quantum computer. It results in a wavefunction:

$\alpha |1\rangle + \beta |2\rangle$

Now assume that the question is true if $\alpha^2<0.5-10^{-100}$ and false otherwise.

In order to determine the result of the calculation you would need to perform the computation $N$ times where N is very large.

Such a calculation would then take a small amount of energy to arrive at the answer in terms of a mixed state, but a huge amount of energy in order to actually see what the answer is to a high degree of certainty.

It seems like there would be a relationship between the complexity of the calculation and the energy needed to measure the result to an acceptable degree of certainty.

If this relationship was such that the energy required to do the calculation was more than the energy required to build a massive array of parallel computers, quantum computing would be not particularly useful or economic.

Thus, I was wondering if there is a theoretical or practical limit to the energy needed to run a quantum computer and how its related to the complexity of the programs you run on it?

  • $\begingroup$ How is energy relevant here? Is it clear that there should be a fundamental relation between computation time or the accuracy you mention and energy? $\endgroup$ – Norbert Schuch Jul 17 '18 at 18:40
  • $\begingroup$ Proper quantum computers are logically reversible and do not dissipate energy. Except that (1) John Donne pointed out the Margolus inequality makes their "speed" depend on an average energy, and (2) error correction is dissipative and sets some energy limit depending on the error rate and the error correction scheme. Also, normally information needs mass-energy to be encoded, and more for higher precision. If it is encoded in an amplitude there may be a fundamental limit on how much energy is needed to "read it out" in a different form. $\endgroup$ – Anders Sandberg Jul 17 '18 at 23:44
  • $\begingroup$ @Norbert well presumably if you need to measure something a lot of times it takes more energy. $\endgroup$ – zooby Jul 18 '18 at 2:44
  • $\begingroup$ Also, think of a quantum factorisation algorithm. If it needs more photons to read out the answer than the size of the number, it doesn't really scale that well. $\endgroup$ – zooby Jul 18 '18 at 2:46

An important measure of the processing rate of a quantum computer is the orthogonalisation time $t_\perp$, that is the time it takes for a state to evolve to an orthogonal one. A version of the usual uncertainty theorem states: $$t_\perp > \frac{\pi\hbar}{2\Delta E}$$ A perhaps more interesting result is the so-called Levitin-Margolus inequality, which states: $$t_\perp > \frac{\pi\hbar}{2(\langle E \rangle -E_0)}$$ According to Wikipedia, this limits the processing rate to about $6 \times 10^{33}$ operations per second per Joule of energy. You can find a proof and discussion in their original paper.

  • 1
    $\begingroup$ Are these CPU equivalent operations or quantum operations? $\endgroup$ – zooby Jul 18 '18 at 2:42
  • $\begingroup$ Computation is essentially 'local'. So it can only be achieved by local interactions, which means a quantum computation can only be implemented by a series of simple local operations. The number of basic operations is the complexity of the algorithm, which determines the efficiency of the computation. $\endgroup$ – XXDD Sep 28 '18 at 15:25

The computational complexity is essentially the geodesic distance between the initial and final states of a quantum computation algorithm, where the geodesic is achieved by an state evolution curve by a time variant Hamiltonian $H(t)$ in the Hilbert space. The geodesic length is then essentially the time-integration of the norm of $H(t)$. So complexity is related with energy and time. Or the complexity itself determines what you mean by 'efficiency'. For more information, please refer to Nielsen's work on quantum computation complexity and geometric picture of quantum mechanics, for example 'geometric formulation of quantum mechanics' by H. Heydari.


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.