Quantum and Classical Complexity of Multivariate Problems

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

Traub and Wozniakowski The goal of information-based complexity is to create atheory of computational complexity and optimal algorithms forproblems with partial, contaminated, and priced information, andto apply the results to solving specific problems in varieddisciplines. For brevity, information-based complexity will becalled IBC. The theory is developed over abstract spaces,typically Hilbert and Banach spaces, while the applications areto multivariate problems. Because the information is partial andcontaminated, only approximate solutions can be obtained. IBCstudies computational complexity and optimal algorithms forcomputing e-approximations in various settings. Because theworst case setting often leads to negative results such asunsolvability and intractability, settings with a weakerassurance such as average, probabilistic, and randomized settingsare also studied. A fairly new area of IBC research is quantumcomputing. The best known algorithms discovered to date, Shor andGrover, are for discrete problems. But many problems occurringin science and engineering are continuous. Examples includehigh-dimensional and path integration, high-dimensionalapproximation, and partial differential equations. To understandthe power of quantum computation for continuous problems one mustknow the computational complexity of these problems on aclassical computer in various settings. This is exactly what hasbeen studied in IBC. Questions to be answered include: For whatproblems is quantum computation (exponentially, polynomially)faster than classical computation? For what problems is thereprovably no speed-up of quantum over classical computation? For some 40 years, computing has been driven by Moore's law,which is the empirical observation that computing power doublesabout every 18 months. This has made it possible for people tohave computers in their homes as powerful as computers owned bycorporations just 20 years ago. It has made the internetpossible. Finally, powerful computers are indispensable to ournational security. Computer chips and wires are getting so smallthat there is a consensus among technologists that Moore's lawwill end in 10 to 15 years using current silicon technology.Because it is critical for our country to maintain the Moore'slaw trajectory, new ways to compute are being considered. One ofthe most promising ideas is to use the principles of quantummechanics to do quantum computing. The investigators and theircolleagues are studying the following question: If physicistsand chemists succeed in building quantum computers, for whichproblems are there big payoffs? That is, what are the killerapplications?