Explicit Lower Bounds on Strong Quantum Simulation
Explicit Lower Bounds on Strong Quantum Simulation
复制标题
DOI：
10.1109/tit.2020.3004427
复制
发表时间：
2020-09-01
影响因子：
2.5
通讯作者：
Szegedy, Mario
中科院分区：
文献类型：
--
作者：
Huang, Cupjin;Newman, Michael;Szegedy, Mario
我们考虑的问题，经典的强（振幅）模拟的n-量子比特量子电路，并确定一个子类的模拟器，我们称之为单调。这个子类几乎包含了所有重要的模拟技术。我们证明了一个无条件的（即不依赖于任何复杂性理论的假设）和明确的（n - 2）（2（n-3）- 1）在这个子类内的模拟器的运行时间的下限。假设强指数时间假设（SETH），我们进一步指出，一个通用的模拟器计算任何振幅的精度为2（-n）/2必须采取至少2（n-o（n））的时间。然后，我们比较强大的模拟器，现有的SAT求解器，并确定的时间复杂度低于一个强大的模拟器将提高国家的最先进的一般SAT解决。最后，我们研究了具有t个T门的Clifford+T量子电路。使用稀疏化引理，我们确定了时间复杂度下限为2（2.2451x10-8）t，低于该下限，强大的模拟器将改善最先进的3-SAT求解。这也产生了一个条件指数下界的增长的稳定器秩的魔术状态。
We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2(n-3) - 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2(-n) /2 must take at least 2(n-o(n)) time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 2(2.2451x10-8)t below which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.