In the early days of quantum mechanics, the time energy uncertainty principle, E t ~ was misinterpreted as a lower bound for the duration ( t) required for measuring the energy of a state with accuracy E. Though many systems obey this lower bound, Y. Aharonov and Bohm (1961) were the rst to give a counter example using a measurement Hamiltonian, which is infeasible: they can reach an exponentially small accuracy E in time t = 1 by increasing the norm of their Hamiltonian by a factor inverse to the accuracy, namely by investing an exponential amount of energy. In this work we claim that Shor’s algorithm is the rst example for measuring an energy with accuracy of n bits (i.e. exponentially good accuracy), in complexity that is polynomial in n. This is due to an eect which we dene of acceleration of Hamiltonians - the ability to simulate an evolution of a system under Hamiltonian for time t using signicantly less than t computational steps. This raises the question: What other interesting Hamiltonians can be accelerated?
In the early days of quantum mechanics, the time energy uncertainty principle, E t ~ was misinterpreted as a lower bound for the duration ( t) required for measuring the energy of a state with accuracy E. Though many systems obey this lower bound, Y. Aharonov and Bohm (1961) were the rst to give a counter example using a measurement Hamiltonian, which is infeasible: they can reach an exponentially small accuracy E in time t = 1 by increasing the norm of their Hamiltonian by a factor inverse to the accuracy, namely by investing an exponential amount of energy. In this work we claim that Shor’s algorithm is the rst example for measuring an energy with accuracy of n bits (i.e. exponentially good accuracy), in complexity that is polynomial in n. This is due to an eect which we dene of acceleration of Hamiltonians - the ability to simulate an evolution of a system under Hamiltonian for time t using signicantly less than t computational steps. This raises the question: What other interesting Hamiltonians can be accelerated?
The time-energy uncertainty relation (TEUR) [Formula: see text] holds if the Hamiltonian is completely unknown, but can be violated otherwise; here we initiate a rigorous study describing when and to what extent such violations can occur. To this end, we propose a computational version of the TEUR (cTEUR), in which Δt is replaced by the computational complexity of simulating the measurement. cTEUR violations are proved to occur if and only if the Hamiltonian can be fast forwarded (FF), namely, simulated for time t with complexity significantly smaller than t. Shor's algorithm provides an example of exponential cTEUR violations; we show that so do commuting local Hamiltonians and quadratic fermion Hamiltonians. A general FF method is ruled out, but finding further examples, as well as experimental demonstrations, are left for future work. We discuss possible connections to sensing and quantum gravity. This work initiates a rigorous theory of efficiency versus accuracy in energy measurements using computational complexity language.
Abstract The time-energy uncertainty relation (TEUR) ΔtΔE≥21 Δ t Δ E ≥ 1 2 holds if the Hamiltonian is completely unknown, but can be violated otherwise; here we initiate a rigorous study describing when and to what extent such violations can occur. To this end, we propose a computational version of the TEUR (cTEUR), in which Δt is replaced by the computational complexity of simulating the measurement. cTEUR violations are proved to occur if and only if the Hamiltonian can be fast forwarded (FF), namely, simulated for time t with complexity significantly smaller than t. Shor’s algorithm provides an example of exponential cTEUR violations; we show that so do commuting local Hamiltonians and quadratic fermion Hamiltonians. A general FF method is ruled out, but finding further examples, as well as experimental demonstrations, are left for future work. We discuss possible connections to sensing and quantum gravity. This work initiates a rigorous theory of efficiency versus accuracy in energy measurements using computational complexity language.
Previously, Bennet and Feynman asked if Heisenberg's uncertainty principle puts a limitation on a quantum computer (Quantum Mechanical Computers, Richard P. Feynman, Foundations of Physics, Vol. 16, No. 6, p597-531, 1986). Feynman's answer was negative. In this paper, we will revisit the same question for the discrete time Fourier transform uncertainty principle. We will show that the discrete time Fourier transform uncertainty principle plays a fundamental role in showing that Shor's type of quantum algorithms has efficient running time and conclude that the discrete time uncertainty principle is an aid in our current formulation and understanding of Shor's type of quantum algorithms. It turns out that for these algorithms, the probability of measuring an element in some set T (at the end of the algorithm) can be written in terms of the time-limiting and band-limiting operators from finite Fourier analysis. Associated with these operators is the finite Fourier transform uncertainty principle. The uncertainty principle provides a lower bound for the above probability. We will derive lower bounds for these types of probabilities in general. We will call these lower bounds quantum algorithm uncertainty principles or QAUP. QAUP are important because they give us some sense of the probability of measuring something desirable. We will use these lower bounds to derive Shor's factoring and discrete log algorithms.
Suppose that the Hamiltonian acting on a quantum system is unknown and one wants to determine which is the Hamiltonian. We show that, in general, this requires a time $\ensuremath{\Delta}t$ that obeys the uncertainty relation $\ensuremath{\Delta}t\ensuremath{\Delta}H\ensuremath{\gtrsim}1,$ where $\ensuremath{\Delta}H$ is a measure of how accurately the unknown Hamiltonian must be estimated. We apply this result to the problem of measuring the energy of an unknown quantum state. It has been previously shown that if the Hamiltonian is known, then the energy can, in principle, be measured with arbitrarily large precision in an arbitrarily short time. On the other hand, we show that if the Hamiltonian is not known then an energy measurement necessarily takes a minimum time $\ensuremath{\Delta}t$ which obeys the uncertainty relation $\ensuremath{\Delta}t\ensuremath{\Delta}E\ensuremath{\gtrsim}1,$ where $\ensuremath{\Delta}E$ is the precision of the energy measurement. Several examples are studied to address the question of whether it is possible to saturate these uncertainty relations. Their interpretation is discussed in detail.
Our understanding of complex mechanical processes is by our inability to solve the equations that govern them except for simple cases. Numerical simulation of systems appears to be our best option to understand, design and improve systems. It turns out, however, that computational problems in mechanics are notoriously difficult to treat numerically. The computational time that is required often scales exponentially with the size of the problem.
One of the most radical approaches for treating problems was proposed by Feytiman in 1982 [46]: he suggested that mechanics itself showed a promising way to simulate physics. This idea, the so called computer, showed its potential convincingly in one important regime with the development of Shor's integer factorization algorithm which improves exponentially on the best known classical algorithm.
In this thesis we explore six different computational problems from mechanics, study their computational complexity and try to find ways to remedy them. In the first problem we investigate the reasons behind the improved performance of Shor's and similar algorithms. We show that the key part in Shor's algorithm, the phase estimation algorithm, achieves its good performance through the use of power queries and we give lower bounds for all phase estimation algorithms that use power queries that match the known upper bounds. Our research indicates that problems that allow the use of power queries will achieve similar exponential improvements over classical algorithms. We then apply our lower bound technique for power queries to the Sturm-Liouville eigenvalue problem and show matching lower bounds to the upper bounds of Papageorgiou and Wozniakowski [85]. It seems to be very difficult, though, to find nontrivial instances of the Sturm-Lionville problem for which power queries can be simulated efficiently.
A computer differs from a classical computer that uses randomness, because it allows negative probabilities that can cancel each other (destructive interference). Ideally we would like to transfer classical randomized algorithms to the computer and get speed improvements. One of the simplest classical randomized algorithm is the random walk and we study the behavior of the continuous-time random walk. We analyze this random walk in one dimension and give analytical formulas for its behavior that demonstrate its interference properties. Is interference or cancellation really the most important advantage that a computer has over a classical computer? To answer that question we study the class StociMA of stochastic quantum algorithms that only use classical gates, but are given a witness, i.e. an arbitrary state that can guide the algorithm in computing the correct answer, but should not be able to fool it. We show that there exists a complete problem for this class, which we call the stoquastic local Hamiltonian problem. In this problem we try to compute the lowest eigenvalue of a Hamiltonian with interactions that span only a fixed number of particles and all contribute negatively. With the help of this problem we prove that MA ⊆ StocIMA ⊆ SBP ∪ QMA. This shows that interference is one of the most important parts of computation.
The simulation of the evolution of a general system in time requires a computational time that is exponential in the dimension of the system. But maybe the problem that we ask for is too general and we can simulate special systems in polynomial time. In particular it would be interesting to study systems of limited energy, i.e. for which the state at starting time consists mainly out of components with small energy. We model this in the theory of weighted reproducing kernel Hilbert spaces with two different sets of weights: product weights and finite-order weights. We will show that the information cost of computing the evolution for starting states from these spaces is tractable, i.e. the cost does not grow exponentially with the dimension of the problem.
Finally we study a computational problem from lattice chromodynamics (QCD). In most popular algorithms that treat problems in QCD the (gauged) Dirac matrix has to be inverted numerous times. Since this matrix is large, sparse, and ill-conditioned, iterative approaches have to be used. Unfortunately a direct application of methods like conjugate gradient (CC) or minimal residual algorithms seem to give poor performance in practice. We study a newly proposed multigrid method, adaptive smoothed aggregation [29], that has promise to overcome these difficulties We show that while classical CG's convergence becomes worse as the matrix becomes almost singular, adaptive smoothed aggregation will still perform well.
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ér-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.