Project Description

To date there have been only two major algorithms for quantum computers which are significantly better than for classical computers: Shor's factorization and Grover's data search. These algorithms are for discrete problems. But many applications in science and engineering have continuous mathematical models. Examples of such models are high dimensional integration, path integration, partial differential equations, and continuous optimization. Such problems are usually solved numerically; they can only be solved to within an uncertainty e. These problems are typically intractable on classical computers if one wants a worst-case deterministic assurance. That is, the classical computational complexity of these problems is usually exponential in 1/e or in d, the number of variables. In the latter case, the problem is said to suffer from the "curse of dimensionality". For some continuous problems, the curse can be vanquished by weakening the worst-case deterministic assurance to a stochastic assurance such as the randomized setting of which Monte Carlo is the prime example.

We will seek new algorithms for quantum computers for important continuous applications. There is a belief that there are a number of killer applications which will enjoy exponential speed-ups over classical computation while requiring only a small or modest number of qubits or qunats. Preliminary investigations suggest that path integrals and high-dimensional finite integrals can be big winners on quantum computers.

During the early algorithm development an abstraction of quantum computations with only a few rather simple and reasonable assumptions will be used. For example, we will assume that some operations such as adding n numbers can be done faster on a quantum computer and explore how these operations may be used to solve continuous problems. Therefore, the theoretical results will be independent of the quantum technology on which they are implemented. Because of the state of quantum technology for the foreseeable future, the development of quantum algorithms which require only a modest number of qubits or qunats will be crucial.

Initially the algorithms will be implemented on quantum computer simulators. Then they will be implemented on NMR quantum computers in D. Cory's laboratory at MIT. Leading experimentors will also be consulted on the development of continuous multi-variable algorithms that are implementable on existing, or soon to exist, quantum computers.

We will also study the quantum complexity of continuous problems. The quantum complexity of important problems will be compared to their classical complexity. In particular,the characterization of problems for which quantum computation offers a significant speed-up over classical computation will be sought.

The work described above will be done jointly by the continuous algorithm and complexity group at Columbia and the quantum computation groups at MIT.

Last modified:July 05, 2011