Search

We introduce the concept of strong quantum speedup. We prove that approximating the ground state energy of an instance of the time-independent Schr\"odinger equation, with $d$ degrees of freedom, $d$ large, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance., Comment: 5 pages, to appear in Phys. Rev. A

Estimating the ground state energy of a multiparticle system with relative error $\e$ using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables $d$ that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error $\e$ using a number of qubits $C^\prime d\log \e^{-1}$ with total cost (number of queries plus other quantum operations) $Cd\e^{-(3+\delta)}$, where $\delta>0$ is arbitrarily small and $C$ and $C^\prime$ are independent of $d$ and $\e$., Comment: 19 pages. This vesrion will appear in Mathemetics of Computation

This paper was presented on the occasion of an honorary doctoral degree for Henryk Wozniakowski at Friedrich Schiller University in Jena, Germany on June 6, 2008. Information-based complexity (IBC) is the study of algorithms and computational complexity of continuous problems. Examples of such problems include partial differential equations (in particular, the Schrodinger equation) very high dimensional integration, approximation, continuous optimization, and path integration. Because the computer has only partial information about the continuous mathematical problem adversary arguments at the information level often lead to tight complexity bounds. This may be contrasted with discrete problems where only conjectures that the complexity hierarchy does not collapse are available. This paper discusses precursors to IBC. It reports on the beginning of optimal iteration theory in the early 60s which was published in Traub's 1964 monograph. In the 70s Traub and Wozniakowski began to formulate the foundations of IBC leading to their 1980 monograph. The paper continues with the development of IBC to the present., Comment: To appear in "Essays on the Complexity of Continuous Problems: A Festschrift for Henryk Wozniakowski" by E. Novak, I. Sloan, J.F. Traub, H. Wozniakowski