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