Quantum and Classical Complexity of Continuous Problems

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

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