A polynomial-time classical algorithm for noisy quantum circuits
- URL: http://arxiv.org/abs/2407.12768v1
- Date: Wed, 17 Jul 2024 17:48:39 GMT
- Title: A polynomial-time classical algorithm for noisy quantum circuits
- Authors: Thomas Schuster, Chao Yin, Xun Gao, Norman Y. Yao,
- Abstract summary: We provide a-time classical algorithm for noisy quantum circuits.
Our approach is based upon the intuition that noise exponentially damps non-local correlations.
- Score: 1.2708457954150887
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g. the computational basis). Our approach is based upon the intuition that noise exponentially damps non-local correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by only keeping track of the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasi-polynomial time, so long as the distribution anti-concentrates. A number of practical implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: any quantum circuit for which error mitigation is efficient must be classically simulable.
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) - A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states.
It is executable on current (hybrid) quantum hardware and does not depend on quantum memory.
We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
arXiv Detail & Related papers (2024-05-29T14:40:24Z) - Classical simulations of noisy variational quantum circuits [0.0]
Noisely affects quantum computations so that they not only become less accurate but also easier to simulate classically as systems scale up.
We construct a classical simulation algorithm, LOWESA, for estimating expectation values of noisy parameterised quantum circuits.
arXiv Detail & Related papers (2023-06-08T17:52:30Z) - Scalable noisy quantum circuits for biased-noise qubits [41.78224056793453]
We consider biased-noise qubits affected only by bit-flip errors, which is motivated by existing systems of stabilized cat qubits.
For realistic noise models, phase-flip will not be negligible, but in the Pauli-Twirling approximation, we show that our benchmark could check the correctness of circuits containing up to $106$ gates.
arXiv Detail & Related papers (2023-05-03T11:27:50Z) - A quantum advantage over classical for local max cut [48.02822142773719]
Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs.
Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
arXiv Detail & Related papers (2023-04-17T16:42:05Z) - Approximation Algorithm for Noisy Quantum Circuit Simulation [3.55689240295244]
This paper introduces a novel approximation algorithm for simulating noisy quantum circuits.
Our method offers a speedup over the commonly-used approximation (sampling) algorithm -- quantum trajectories method.
arXiv Detail & Related papers (2022-11-30T14:20:22Z) - 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) - Limitations of variational quantum algorithms: a quantum optimal
transport approach [11.202435939275675]
We obtain extremely tight bounds for standard NISQ proposals in both the noisy and noiseless regimes.
The bounds limit the performance of both circuit model algorithms, such as QAOA, and also continuous-time algorithms, such as quantum annealing.
arXiv Detail & Related papers (2022-04-07T13:58:44Z) - Numerical Simulations of Noisy Quantum Circuits for Computational
Chemistry [51.827942608832025]
Near-term quantum computers can calculate the ground-state properties of small molecules.
We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
arXiv Detail & Related papers (2021-12-31T16:33:10Z) - Quantum Causal Unravelling [44.356294905844834]
We develop the first efficient method for unravelling the causal structure of the interactions in a multipartite quantum process.
Our algorithms can be used to identify processes that can be characterized efficiently with the technique of quantum process tomography.
arXiv Detail & Related papers (2021-09-27T16:28:06Z) - Efficient classical simulation and benchmarking of quantum processes in
the Weyl basis [0.0]
We develop a randomized benchmarking algorithm which uses Weyl unitaries to efficiently identify and learn a mixture of error models.
We apply our methods to ansatz circuits that appear in the Variational Quantum Eigensolver.
arXiv Detail & Related papers (2020-08-27T16:46:12Z)
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.