Quantum Chaos is Quantum
Lorenzo Leone, Salvatore F. E. Oliviero, You Zhou, Alioscia Hamma
Abstract
It is well known that a quantum circuit on<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math>qubits composed of Clifford gates with the addition of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>non Clifford gates can be simulated on a classical computer by an algorithm scaling as<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>poly</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>N</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mi>exp</mml:mi><mml:mo></mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>\cite{bravyi2016improved}. We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mi mathvariant="normal">Θ</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>N</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>. This result implies the impossibility of simulating quantum chaos on a classical computer.