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)[1]. 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.

Quantum chaos is quantum

Alioscia Hamma
2021

Abstract

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)[1]. 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.
File in questo prodotto:
File Dimensione Formato  
q-2021-05-04-453.pdf

accesso aperto

Licenza: Non specificato
Dimensione 800.85 kB
Formato Adobe PDF
800.85 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11588/892760
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 6
social impact