Does Heisenberg's energy-time uncertainty principle imply that quantum computing is no more efficient than classical computing? See http://arxiv.org/abs/quant-ph/0006080v1 "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.
 A: 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.
