Quantum Chaos is Quantum

• URL: http://arxiv.org/abs/2102.08406v3
• Date: Mon, 3 May 2021 16:39:05 GMT
• Title: Quantum Chaos is Quantum
• Authors: Lorenzo Leone, Salvatore F. E. Oliviero, You Zhou and Alioscia Hamma
• Abstract summary: We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that $k=O(N)$. This result implies the impossibility of simulating quantum chaos on a classical computer.
• Score: 1.2008527035019914
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\text{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=O(N)$. This result implies the impossibility of simulating quantum chaos on a classical computer.

Related papers

• How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing [0.2184775414778289]
  We show that advantages in space complexity are possible for quantum algorithms over their classical counterparts in the streaming model. We give a simple quantum sketch that encompasses all these results, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box.
  arXiv  Detail & Related papers  (2024-10-24T17:11:37Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Q$^2$Chemistry: A quantum computation platform for quantum chemistry [7.362240457595957]
  We present Q$2$Chemistry, for developing quantum algorithms and quantum inspired classical algorithms in the field of quantum chemistry. Q$2$Chemistry generates quantum circuits according to a specific quantum algorithm already implemented in the package or newly developed by the users. The generated circuits can be dispatched to either a physical quantum computer, if available, or to the internal virtual quantum computer realized by simulating quantum circuit on classical supercomputers.
  arXiv  Detail & Related papers  (2022-08-23T13:50:46Z)
• Automatic quantum circuit encoding of a given arbitrary quantum state [0.0]
  We propose a quantum-classical hybrid algorithm to encode a given arbitrarily quantum state onto an optimal quantum circuit. The proposed algorithm employs as an objective function the absolute value of fidelity $F = langle 0 vert hatmathcalCdagger vert Psi rangle$. We experimentally demonstrate that a quantum circuit generated by the AQCE algorithm can indeed represent the original quantum state reasonably on a noisy real quantum device.
  arXiv  Detail & Related papers  (2021-12-29T12:33:41Z)
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers [38.860468003121404]
  We study an open quantum system simulation on quantum hardware, which demonstrates robustness to hardware errors even with deep circuits containing up to two thousand entangling gates. We simulate two systems of electrons coupled to an infinite thermal bath: 1) a system of dissipative free electrons in a driving electric field; and 2) the thermalization of two interacting electrons in a single orbital in a magnetic field -- the Hubbard atom. Our results demonstrate that algorithms for simulating open quantum systems are able to far outperform similarly complex non-dissipative algorithms on noisy hardware.
  arXiv  Detail & Related papers  (2021-08-02T21:36:37Z)
• Sample Complexity of Learning Quantum Circuits [4.329298109272386]
  We prove that physical quantum circuits are PAC learnable on a quantum computer via empirical risk minimization. Our results provide a valuable guide for quantum machine learning in both theory and experiment.
  arXiv  Detail & Related papers  (2021-07-19T18:00:04Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• What limits the simulation of quantum computers? [5.22339562024796]
  We demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.
  arXiv  Detail & Related papers  (2020-02-18T17:00:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.