Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates
Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates
复制标题
DOI：
10.26421/qic14.13-14-7
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Y. Takahashi;Takeshi Yamazaki;Kazuyuki Tanaka
中科院分区：
文献类型：
--
作者：
Y. Takahashi;Takeshi Yamazaki;Kazuyuki Tanaka
我们研究了只有一个单量子比特测量的常数深度多项式大小的量子电路的经典可模拟性，其中电路由至多两个量子比特上的通用门和无限数量的量子比特上的附加门组成。首先，我们考虑无界Toffoli门作为额外的门，并处理弱模拟，即，对输出概率分布进行采样。我们证明了存在一个只有一个无界Toffoli门的恒定深度量子电路，除非BQP ≠ PostBPP ≠ AM，否则它不是弱可模拟的。然后，我们考虑无界扇出门作为额外的门，并处理强模拟，即，计算输出概率。我们证明了存在一个只有两个无界扇出门的恒定深度量子电路，除非P = PP，否则它不是强可模拟的。这些结果与这样的事实相反，即任何在无限数量的量子比特上没有附加门的恒定深度量子电路都是强和弱可模拟的。
We study the classical simulatability of constant-depth polynomial-size quantum circuits followed by only one single-qubit measurement, where the circuits consist of universal gates on at most two qubits and additional gates on an unbounded number of qubits. First, we consider unbounded Toffoli gates as additional gates and deal with the weak simulation, i.e., sampling the output probability distribution. We show that there exists a constant-depth quantum circuit with only one unbounded Toffoli gate that is not weakly simulatable, unless BQP ⊆ PostBPP ∩ AM. Then, we consider unbounded fan-out gates as additional gates and deal with the strong simulation, i.e., computing the output probability. We show that there exists a constant-depth quantum circuit with only two unbounded fan-out gates that is not strongly simulatable, unless P = PP. These results are in contrast to the fact that any constant-depth quantum circuit without additional gates on an unbounded number of qubits is strongly and weakly simulatable.