Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
复制标题
DOI：
10.1103/physrevlett.117.080501
复制
发表时间：
2016-08-18
影响因子：
8.6
通讯作者：
Shepherd, Dan J.
中科院分区：
文献类型：
--
作者：
Bremner, Michael J.;Montanaro, Ashley;Shepherd, Dan J.
我们使用被称为IQP（瞬时量子多项式时间）的交换量子计算类来加强量子计算机难以经典模拟的猜想。我们表明，如果两个合理的平均情况下的硬度approximatures持有，那么IQP计算是很难模拟经典的恒定的附加误差。一个猜想涉及到估计伊辛模型的随机实例的复杂的温度配分函数的硬度;其他的关注近似随机低次多项式的零点的数量。我们观察到，这两种方法可以被证明是有效的，在最坏情况下的复杂性。我们通过推导基于自旋的玻色子采样问题的一般化，避免了所谓的永久反浓度猜想，从而达到这些目的。
We use the class of commuting quantum computations known as IQP (instantaneous quantum polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalizations of the boson sampling problem that avoid the so-called permanent anticoncentration conjecture.