Quantum Algorithms for Continuous Problems and Their Applications
Anargyros Papageorgiou, Joseph F. Traub · Advances in chemical physics · 2014
This chapter summarizes the model of computation that is used for classical algorithms solving continuous problems. It talks about the quantum model of computation. In the study of the classical complexity of continuous problems, the real number model with oracles is often used. The information operations are represented as black-box or oracle calls. This model of computation is an abstraction of fixed precision floating point arithmetic used in science and engineering. It has also been used in the study of the complexity of algebraic problems such as matrix multiplication. Inputs to quantum algorithms are often given using quantum queries. Classical algorithms for integration have been extensively studied in the literature and optimal algorithms are known for numerous classes of functions. Quantum algorithms for integration have been used to derive optimal quantum algorithms for other continuous problems, such as path integration, certain approximation problems, and the solution of ordinary differential equations.