Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable

Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki +1

We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output…