Quantum and Classical Complexity of Multivariate Problems

点击翻译按钮获取中文摘要

Information-based complexity (IBC) studies optimal algorithms andcomputational complexity for the continuous problems which arise inphysical science, economics, engineering, and mathematical finance.IBC has studied such continuous problems as path integration, partialdifferential equations, systems of ordinary differential equations,nonlinear equations, integral equations, fixed points, and integration.Usually these problems have to be solved numerically and thereforeapproximately to within error e. Often these problems involve a verylarge number of variables numbering in the hundreds or thousands. If aworst case assurance of an e-approximation is demanded, then thecomputational complexity depends exponentially on the number of variables;the problem suffers the "curse of dimensionality". The investigators andtheir colleagues attempt to vanquish the curse by settling for astochastic assurance (average, probabilistic, randomized) or by usingdomain knowledge about the application. The investigators are alsostudying the power of quantum computation for continuous problems. Tounderstand the power of quantum computation for continuous problems onemust know the computational complexity of these problems on a classicalcomputer in various settings. This is exactly what has been studied inIBC. Recently the investigators introduced a new quantum setting in whichrandomized queries are permitted. They have shown that for pathintegration there is an exponential improvement for the qubit complexitycompared to the standard quantum setting. This is important since thenumber of qubits is a critical resource for the foreseeable future. Amongthe questions the investigators and their colleagues stydying are:What are the query and qubit complexities for other continuous problems?Are there trade-offs between query and qubit complexities?For some forty years, computing has been driven by Moore's Law which isthe empirical observation that computing power doubles about every 18months. Powerful computers have been crucial for our economic strengthand our national security. They have made the internet possible. For anumber of reasons the consensus among experts is that Moore's Law usingcurrent silicon technology will end in some 10 to 15 years. These reasonsinclude the shrinkage of logic gates and wires to atomic size, the tre-mendous heat generated as chips get smaller and faster, and the cost offabrication facilities. Since it is so important to maintain theMoore's Law trajectory, new ways to compute are being considered. Oneof the most promising ideas is to use the principles of quantum mechanicsto do quantum computing. The investigators and their colleagues arestudying the following question: If physicists and chemists succeed inbuilding quantum computers, which continuous problems arising in scienceand engineering can be solved much faster on a quantum computer than on aclassical computer?