Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

See "On Non Efficiency of Quantum Computer", by Robert Alicki. In this paper, the author argues using Heisenberg's energy-time uncertainty principle, that quantum computing is no more efficient than classical computing. This paper convinced me, but I'm just an amateur and also biased toward toward this view. I'm curious why the experts still believe that quantum computing is more efficient than classical computing, given the argument made in this paper in 2000.

share|cite|improve this question
I haven't tried to understand the whole paper, but a comment: this was posted in 2008 and has not been published in a peer-reviewed journal since. That should tell you something about either its correctness or relevance. – user2963 Sep 6 '12 at 16:14
If you look at the arxiv time stamp, it was posted in 2000. All of the citations are before 2000. I'm not sure why it says 2008 in the paper. – Craig Feinstein Sep 6 '12 at 16:43
google scholar tells two articles citing the work:… – Yrogirg Sep 9 '12 at 14:12
"the author argues ... that quantum computing is no more efficient than classical computing" - using a definition of efficiency which is a product of time taken and energy consumed. Even if he's completely right (which I doubt), a quantum computer can still be faster, this just comes at a cost in energy. – Mitchell Porter Sep 9 '12 at 14:49
@Craig: There's a latex command that prints out today's date. The arXiv doesn't always store the postscript; sometimes it figures it would be more efficient to store the latex source code and recompile it when the paper is downloaded. For the arXiv, that latex command really should be redefined to print out the date that the source code was uploaded, but nobody seems to have bothered. – Peter Shor Sep 9 '12 at 21:01
up vote 4 down vote accepted

The short answer is no.

Regarding the paper, I can't understand the logic. As far as I can tell, the author writes down some version of the time-energy uncertainty relation, then says "Hence, it is quite natural to investigate X" where X has little or nothing to do with the time-energy uncertainty relation.

The language and formulation of the paper are also not clear, for example the fundamental inequality Eq. 3 is not even precisely formulated. In my opinion, you should not take the paper seriously. You said in your question that the author convinced you of their premise, but I'm not even sure what the premise is. If you could state precisely what you're convinced of, I could try to address it more directly.

Here is a physical counter-example showing that quantum computation need not take excessive (exponential) physical resources. One proposal for quantum computation involves adiabatically moving topological excitations around each other in a two dimensional piece of quantum matter. This is called topological quantum computation. We already have experimental examples, such as fractional quantum Hall fluids, which support these kind of topological excitations. By slowly braiding these excitations around each other in a suitable piece of quantum matter we can produce any unitary transformation we want and hence do computation. However, this braiding does not take exponential time, nor does it require exponentially large energy (in fact if the braiding is down adiabatically and interactions are short ranged, the energy of the piece of quantum matter may not even change during the computation!)

Hope this helps.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.