The Quantum Cram\'er-Rao lower bound (Why quantum computers won't work I)

Abstract

Quantum information science currently poses a troubling contradiction. It can be summarized as: (1) To factor efficiently, quantum computers must perform exponentially precise energy estimation. (2) Exponentially precise energy estimation is impossible according to both the Heisenberg limit and the Cram\'er-Rao lower bound in quantum metrology. It is surprising that such a dramatic contradiction exists between two accepted predictions of quantum mechanics, and yet this contradiction it is not widely discussed. It is even more surprising when one notes it is not a minor discrepancy -- the two statements differ by an exponential margin. Not only that, whether (1) or (2) is correct is of fundamental importance to the realisation of an important class of quantum technologies. If (2) is correct, then quantum computers are much less powerful than expected. This work resolves the above contradiction by defining a computational model in which a wide range of computational problems are not solvable in polynomial time. We then show that this computational model applies to the majority of quantum algorithms, including Shor's algorithm.