Commuting quantum circuits with few outputs are unlikely to be classically simulatable
Commuting quantum circuits with few outputs are unlikely to be classically simulatable
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 probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there …