null
(Ed.)
It is well known that a quantum circuit on N qubits composed of Clifford gates with the addition of k non Clifford gates can be simulated on a classical computer by an algorithm scaling as poly ( N ) exp ( k ) \cite{bravyi2016improved}. We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that k = Θ ( N ) . This result implies the impossibility of simulating quantum chaos on a classical computer.
more »
« less