Polynomial-Time Classical Simulation of Noisy Circuits with Naturally Fault-Tolerant Gates

• URL: http://arxiv.org/abs/2411.02535v2
• Date: Tue, 10 Dec 2024 20:51:36 GMT
• Title: Polynomial-Time Classical Simulation of Noisy Circuits with Naturally Fault-Tolerant Gates
• Authors: Jon Nelson, Joel Rajakumar, Dominik Hangleiter, Michael J. Gullans,
• Abstract summary: We show that there is no quantum advantage at large depths with realistically noisy Clifford circuits. The key insight behind the algorithm is that interspersed noise causes a decay of long-range entanglement. To prove our results, we merge techniques from percolation theory with tools from Pauli path analysis.
• Score: 0.22499166814992438
• License:
• Abstract: We construct a polynomial-time classical algorithm that samples from the output distribution of low-depth noisy Clifford circuits with any product-state inputs and final single-qubit measurements in any basis. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results generalize a simulation algorithm for IQP circuits [Rajakumar et. al, SODA'25] to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, our results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class. This allows us to place tight limitations on the robustness of these circuits to noise. In particular, we show that there is no quantum advantage at large depths with realistically noisy Clifford circuits, even with perfect magic state inputs, or IQP circuits with CNOT gates, even with arbitrary diagonal non-Clifford gates. The key insight behind the algorithm is that interspersed noise causes a decay of long-range entanglement, and at depths beyond a critical threshold, the noise builds up to an extent that most correlations can be classically simulated. To prove our results, we merge techniques from percolation theory with tools from Pauli path analysis.

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)
• 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)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  We numerically simulate and characterize the operation of various quantum processors. We identify and assess quantum complexity by comparing the performance of each device against benchmark lines. We find that the majorization-based benchmark holds as long as the circuits' output states have, on average, high purity.
  arXiv  Detail & Related papers  (2023-04-10T23:01:10Z)
• 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)
• Circuit connectivity boosts by quantum-classical-quantum interfaces [0.4194295877935867]
  High-connectivity circuits are a major roadblock for current quantum hardware. We propose a hybrid classical-quantum algorithm to simulate such circuits without swap-gate ladders. We numerically show the efficacy of our method for a Bell-state circuit for two increasingly distant qubits.
  arXiv  Detail & Related papers  (2022-03-09T19:00:02Z)
• Empirical Evaluation of Circuit Approximations on Noisy Quantum Devices [0.0]
  Noisy Intermediate-Scale Quantum (NISQ) devices fail to produce outputs with sufficient fidelity for deep circuits with many gates today. This work develops a methodology to generate shorter circuits with fewer multi-qubit gates whose unitary transformations approximate the original reference one.
  arXiv  Detail & Related papers  (2021-07-14T13:44:54Z)
• The principle of majorization: application to random quantum circuits [68.8204255655161]
  Three classes of circuits were considered: (i) universal, (ii) classically simulatable, and (iii) neither universal nor classically simulatable. We verified that all the families of circuits satisfy on average the principle of majorization. Clear differences appear in the fluctuations of the Lorenz curves associated to states.
  arXiv  Detail & Related papers  (2021-02-19T16:07:09Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  We show a strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. A key component of this reduction is showing average-case hardness for the classical simulation tasks. We show that is true even for quantum tasks which are $oplus$L-hard to simulate.
  arXiv  Detail & Related papers  (2021-02-13T00:54:45Z)
• On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
  We show that commonly held intuitions when designing quantum circuits can be misleading. We show that reducing the T-count can increase the total depth. We illustrate our method on addition and multiplication circuits using ripple-carry.
  arXiv  Detail & Related papers  (2021-01-12T21:36:16Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
  arXiv  Detail & Related papers  (2020-07-29T05:26:19Z)
• Efficient simulatability of continuous-variable circuits with large Wigner negativity [62.997667081978825]
  Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures. We identify vast families of circuits that display large, possibly unbounded, Wigner negativity, and yet are classically efficiently simulatable. We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.
  arXiv  Detail & Related papers  (2020-05-25T11:03:42Z)

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.