Quantum and Classical Complexity of Continuous Problems

连续问题的量子和经典复杂性研究人员正在研究以下一般性问题：如果物理学家和化学家成功地建立了量子计算机，那么在量子计算机上解决科学和工程中的哪些连续问题可以比在经典计算机上快得多？连续问题的例子有路径积分、薛定谔方程、高维近似、连续优化和积分方程式。要获得连续问题的量子计算能力，必须知道这些问题在经典计算机上的计算复杂性。这正是调查人员在信息复杂性领域几十年来一直研究的问题。由于信息论的争论，许多连续问题的经典复杂性已为人所知。这可能与整数分解等离散问题形成对比，在这些问题中，人们不得不满足关于复杂性层次的猜测。研究人员将研究的问题如下：1.在可预见的未来，量子比特的数量将是关键的计算资源。研究人员已经证明，修改量子算法的标准定义以允许随机查询会导致路径集成的量子比特复杂性指数级提高。研究人员建议利用随机化查询设置的力量。例如，其他重要问题的查询复杂度是否有指数级的提高？2.物理和化学中的一个基本问题是计算系统的基态能量。基态能量由与时间无关的薛定谔方程的最小本征值给出。如果系统中的粒子数为p，则变量数为d=3p。在最糟糕的经典情况下，我们研究的问题遭受了维度的诅咒。这一诅咒在量子环境中被打破了。研究人员想要确定随机的经典设置是否受到维度诅咒的影响。如果是这样的话，量子计算机在这个问题上可以享受指数级的加速。这将标志着一个重要问题得到证实的指数量子加速的第一个例子。3.薛定谔方程是量子物理和量子化学的基础。对于具有大量变量的量子系统来说，求解这个方程对于许多应用来说都会有巨大的回报。研究人员建议研究算法，并在经典计算机和量子环境下开始研究薛定谔方程在最坏情况和随机设置下的计算复杂性

QUANTUM AND CLASSICAL COMPLEXITY OF CONTINUOUS PROBLEMSABSTRACT 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, andintegral 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. Theinvestigators 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