Pauli path simulations of noisy quantum circuits beyond average case
- URL: http://arxiv.org/abs/2407.16068v1
- Date: Mon, 22 Jul 2024 21:58:37 GMT
- Title: Pauli path simulations of noisy quantum circuits beyond average case
- Authors: Guillermo González-García, J. Ignacio Cirac, Rahul Trivedi,
- Abstract summary: 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.
- Score: 0.3277163122167433
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For random quantum circuits on $n$ qubits of depth $\Theta(\log n)$ with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method [Aharonov et al. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023] . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates $\unicode{x2013}$ going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.
Related papers
- A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
We provide a-time classical algorithm for noisy quantum circuits.
Our approach is based upon the intuition that noise exponentially damps non-local correlations.
For constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.
arXiv Detail & Related papers (2024-07-17T17:48:39Z) - Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth [0.5188841610098435]
We show that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer.
We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit.
arXiv Detail & Related papers (2024-03-21T17:55:26Z) - 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) - 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) - 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) - Simulating the Mott transition on a noisy digital quantum computer via
Cartan-based fast-forwarding circuits [62.73367618671969]
Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model.
Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models.
This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
arXiv Detail & Related papers (2021-12-10T17:32:15Z) - Accurate methods for the analysis of strong-drive effects in parametric
gates [94.70553167084388]
We show how to efficiently extract gate parameters using exact numerics and a perturbative analytical approach.
We identify optimal regimes of operation for different types of gates including $i$SWAP, controlled-Z, and CNOT.
arXiv Detail & Related papers (2021-07-06T02:02:54Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated.
Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform.
In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
arXiv Detail & Related papers (2020-11-24T18:44:57Z) - 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) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
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.
arXiv Detail & Related papers (2019-12-31T19:00:00Z)
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.