论文标题
单Qubit Gate Teleportation提供量子优势
Single-qubit gate teleportation provides a quantum advantage
论文作者
论文摘要
可以说，栅极缩放电路是据信提供量子计算优势的最基本的计算示例之一：在开创性工作中[量子。 Comput。，4（2）：134--145]，Terhal和Divincenzo表明，在合理的复杂性理论假设下，这些电路通过有效的经典算法消除了模拟。在这里，我们考虑可能模拟[Phys。 Rev. A 106，062430（2022）]，这是该任务特别弱的形式，其目标是输出任何在电路输出分布中出现具有非零概率的字符串。我们表明，即使对于单Qubit Clifford-Gate-teportation Circuits，也无法通过带有有限的风扇进入大门的恒定深入的经典电路来解决此模拟问题。我们的结果是无条件的，是通过减少计算平等性的问题而获得的，这是经典电路复杂性的一个充分研究的问题。
Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work [Quantum Inf. Comput., 4(2):134--145], Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation [Phys. Rev. A 106, 062430 (2022)], a particularly weak form of this task where the goal is to output any string appearing with non-zero probability in the output distribution of the circuit. We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates. Our results are unconditional and are obtained by a reduction to the problem of computing the parity, a well-studied problem in classical circuit complexity.
