Efficient classical simulation of noisy random quantum circuits in one dimension

• URL: http://arxiv.org/abs/2003.13163v3
• Date: Tue, 8 Sep 2020 02:44:04 GMT
• Title: Efficient classical simulation of noisy random quantum circuits in one dimension
• Authors: Kyungjoo Noh, Liang Jiang, Bill Fefferman
• Abstract summary: We study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation.
• Score: 4.154652903729955
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.

Related papers

• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem [0.0]
  We show that adiabatic evolution can be performed with a fixed, finite Trotter step. We give numerical evidence using matrix-product-state simulations that it can optimally solve the Max-Cut problem. Extrapolating our numerical results, we estimate the resources needed for a quantum computer to compete with classical exact or approximate solvers.
  arXiv  Detail & Related papers  (2024-04-24T17:29:03Z)
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts [0.0]
  We give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states. We show that the stability properties of a large class of classical dynamics allow their fast-forwarding. We find that the history state can always be output with complexity $O(T1/2)$ for any stable linear system.
  arXiv  Detail & Related papers  (2023-09-14T17:25:43Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• Overcoming exponential scaling with system size in Trotter-Suzuki implementations of constrained Hamiltonians: 2+1 U(1) lattice gauge theories [1.5675763601034223]
  For many quantum systems of interest, the classical computational cost of simulating their time evolution scales exponentially in the system size. quantum computers have been shown to allow for simulations of some of these systems using resources that scale exponentially with the system size. This work identifies a term in the Hamiltonian of a class of constrained systems that naively requires quantum resources that scale exponentially in the system size.
  arXiv  Detail & Related papers  (2022-08-05T18:00:52Z)
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions [8.501065978448919]
  noisy quantum devices without error correction can provide quantum advantage over classical computers. In this work, the random quantum circuits are simulated with depolarizing noise on experiment relevant two-dimensional architecture.
  arXiv  Detail & Related papers  (2022-05-27T14:22:28Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits [58.720142291102135]
  We simulate a noisy quantum Fourier transform processor with up to 21 qubits. We take into account microscopic dissipative processes rather than relying on digital error models. We show that depending on the dissipative mechanisms at play, the choice of input state has a strong impact on the performance of the quantum algorithm.
  arXiv  Detail & Related papers  (2021-02-08T14:55:44Z)
• Classical simulation of lossy boson sampling using matrix product operators [3.696640001804864]
  We numerically investigate the computational power of NISQ devices focusing on boson sampling. We show by simulating lossy boson sampling using an MPO that as an input photon number grows, its computational cost, or MPO EE, behaves differently depending on a loss-scaling.
  arXiv  Detail & Related papers  (2021-01-27T07:29:03Z)
• Fast and differentiable simulation of driven quantum systems [58.720142291102135]
  We introduce a semi-analytic method based on the Dyson expansion that allows us to time-evolve driven quantum systems much faster than standard numerical methods. We show results of the optimization of a two-qubit gate using transmon qubits in the circuit QED architecture.
  arXiv  Detail & Related papers  (2020-12-16T21:43:38Z)
• Simulating nonnative cubic interactions on noisy quantum machines [65.38483184536494]
  We show that quantum processors can be programmed to efficiently simulate dynamics that are not native to the hardware. On noisy devices without error correction, we show that simulation results are significantly improved when the quantum program is compiled using modular gates.
  arXiv  Detail & Related papers  (2020-04-15T05:16:24Z)

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.