Efficient classical simulation of random shallow 2D quantum circuits
- URL: http://arxiv.org/abs/2001.00021v2
- Date: Mon, 9 Mar 2020 17:20:17 GMT
- Title: Efficient classical simulation of random shallow 2D quantum circuits
- Authors: John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S.
L. Brandao, Aram W. Harrow
- Abstract summary: Random quantum circuits are commonly viewed as hard to simulate classically.
We show that approximate simulation of typical instances is almost as hard as exact simulation.
We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
- Score: 104.50546079040298
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random quantum circuits are commonly viewed as hard to simulate classically.
In some regimes this has been formally conjectured, and there had been no
evidence against the more general possibility that for circuits with uniformly
random gates, approximate simulation of typical instances is almost as hard as
exact simulation. We prove that this is not the case by exhibiting a shallow
circuit family with uniformly random gates that cannot be efficiently
classically simulated near-exactly under standard hardness assumptions, but can
be simulated approximately for all but a superpolynomially small fraction of
circuit instances in time linear in the number of qubits and gates. We
furthermore conjecture that sufficiently shallow random circuits are
efficiently simulable more generally. To this end, we propose and analyze two
simulation algorithms. Implementing one of our algorithms numerically, we give
strong evidence that it is efficient both asymptotically and, in some cases, in
practice. To argue analytically for efficiency, we reduce the simulation of 2D
shallow random circuits to the simulation of a form of 1D dynamics consisting
of alternating rounds of random local unitaries and weak measurements -- a type
of process that has generally been observed to undergo a phase transition from
an efficient-to-simulate regime to an inefficient-to-simulate regime as
measurement strength is varied. Using a mapping from quantum circuits to
statistical mechanical models, we give evidence that a similar computational
phase transition occurs for our algorithms as parameters of the circuit
architecture like the local Hilbert space dimension and circuit depth are
varied.
Related papers
- Pauli path simulations of noisy quantum circuits beyond average case [0.3277163122167433]
For random quantum circuits on $n$ qubits of depth, the task of sampling from the output state can be efficiently performed classically using a Pauli path method.
We derive sufficient conditions for simulatability in terms of noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate, the simulation becomes classically easy.
arXiv Detail & Related papers (2024-07-22T21:58:37Z) - Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum
Circuit Simulation [65.93830818469833]
tensor networks and decision diagrams have independently been developed with differing perspectives, terminologies, and backgrounds in mind.
We consider how these techniques approach classical quantum circuit simulation, and examine their (dis)similarities with regard to their most applicable abstraction level.
We provide guidelines for when to better use tensor networks and when to better use decision diagrams in classical quantum circuit simulation.
arXiv Detail & Related papers (2023-02-13T19:00:00Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients.
We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage.
Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
arXiv Detail & Related papers (2022-12-12T15:06:32Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Fast Classical Simulation of Hamiltonian Dynamics by Simultaneous
Diagonalization Using Clifford Transformation with Parallel Computation [0.8206877486958002]
We propose a technique to accelerate simulation of quantum dynamics via simultaneous diagonalization of mutually commuting Pauli groups.
Compared to an implementation using one of the fastest simulators of quantum computers, our method provides a few tens of times acceleration.
arXiv Detail & Related papers (2022-06-23T12:39:54Z) - 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) - Constant-Depth Circuits for Dynamic Simulations of Materials on Quantum
Computers [0.0]
We present a method for generating circuits that are constant in depth with increasing simulation time for a subset of one-dimensional materials Hamiltonians.
By removing the effective limit on the number of feasibly simulatable time-steps, the constant-depth circuits enable Trotter error to be made negligibly small.
This paves the way for simulations of long-time dynamics for scientifically and technologically relevant quantum materials.
arXiv Detail & Related papers (2021-03-12T17:47:02Z) - Classical simulation of bosonic linear-optical random circuits beyond
linear light cone [2.5496329090462626]
We examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits.
We show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources.
arXiv Detail & Related papers (2021-02-19T18:33:31Z) - Efficient calculation of gradients in classical simulations of
variational quantum algorithms [0.0]
We present a novel derivation of an emulation strategy to precisely calculate the gradient in O(P) time.
Our strategy is very simple, uses only 'apply gate', 'clone state' and 'inner product' primitives.
It is compatible with gate parallelisation schemes, and hardware accelerated and distributed simulators.
arXiv Detail & Related papers (2020-09-06T21:39:44Z) - 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.