Quantum and Classical Complexity of Continuous Problems

Columbia University, New York NY

Investigators

Abstract

QUANTUM AND CLASSICAL COMPLEXITY OF CONTINUOUS PROBLEMS ABSTRACT The investigators are studying the following general question: If physicists and chemists succeed in building quantum computers, which continuous problems arising in science and engineering can be solved much faster on a quantum computer than on a classical computer? Examples of continuous problems are path integration, the Schrödinger equation, high-dimensional approximation, continuous optimization, and integral equations. To obtain the power of quantum computation for continuous problems one must know the computational complexity of these problems on a classical computer. This is exactly what the investigators have studied for decades in the field of information-based complexity. The classical complexity of many continuous problems is known due to information theoretic arguments. This may be contrasted with discrete problems such as integer factorization where one has to settle for conjectures about the complexity hierarchy. Among the issues the investigators will study are the following: 1. For the foreseeable future the number of qubits will be a crucial computational resource. The investigators have shown that modifying the standard definition of quantum algorithms to permit randomized queries leads to an exponential improvement in the qubit complexity of path integration. The investigators propose to exploit the power of the randomized query setting. For example, are there exponential improvements in the query complexity for other important problems? 2. A basic problem in physics and chemistry is to compute the ground state energy of a system. The ground state energy is given by the smallest eigenvalue of the time-independent Schrödinger equation. If the number of particles in the system is p, the number of variables is d = 3p. In the worst case classical setting, the problem we study suffers the curse of dimensionality. The curse is broken in the quantum setting. The investigators want to determine if the randomized classical setting suffers the curse of dimensionality. If it does, a quantum computer enjoys exponential speedup for this problem. This would mark the first example of proven exponential quantum speedup for an important problem. 3. The Schrödinger equation is fundamental to quantum physics and quantum chemistry. Solving this equation for quantum systems with a large number of variables would have a huge payoff for many applications. The investigators propose to study algorithms and initiate the study of the computational complexity of the Schrödinger equation in the worst case and randomized settings on a classical computer and in the quantum setting