Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

• URL: http://arxiv.org/abs/2403.14607v2
• Date: Sat, 05 Oct 2024 01:38:55 GMT
• Title: Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
• Authors: Joel Rajakumar, James D. Watson, Yi-Kai Liu,
• Abstract summary: 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.
• Score: 0.5188841610098435
• License:
• Abstract: Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical $O(1)$ threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit's architecture, on anti-concentration properties, nor do we require $\Omega(\log(n))$ circuit depth. 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. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought.

Related papers

• Polynomial-Time Classical Simulation of Noisy Circuits with Naturally Fault-Tolerant Gates [0.22499166814992438]
  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.
  arXiv  Detail & Related papers  (2024-11-04T19:11:58Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Robust sparse IQP sampling in constant depth [3.670008893193884]
  NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation. We propose a scheme to achieve a provable superpolynomial quantum advantage that is robust to noise with minimal error correction requirements.
  arXiv  Detail & Related papers  (2023-07-20T09:41:08Z)
• Quantum Imitation Learning [74.15588381240795]
  We propose quantum imitation learning (QIL) with a hope to utilize quantum advantage to speed up IL. We develop two QIL algorithms, quantum behavioural cloning (Q-BC) and quantum generative adversarial imitation learning (Q-GAIL) Experiment results demonstrate that both Q-BC and Q-GAIL can achieve comparable performance compared to classical counterparts.
  arXiv  Detail & Related papers  (2023-04-04T12:47:35Z)
• Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer [1.2019888796331233]
  We introduce a new circuit called AQCEL, which aims to remove redundant controlled operations from controlled gates. As a benchmark, the AQCEL is deployed on a quantum algorithm designed to model final state radiation in high energy physics. We have demonstrated that the AQCEL-optimized circuit can produce equivalent final states with much smaller number of gates.
  arXiv  Detail & Related papers  (2022-09-06T09:19:07Z)
• Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most. We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
  arXiv  Detail & Related papers  (2022-04-12T19:39:31Z)
• An Optimized Quantum Implementation of ISD on Scalable Quantum Resources [2.274915755738124]
  We show that Prange's ISD algorithm can be implemented rather efficiently on a quantum computer. We leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs.
  arXiv  Detail & Related papers  (2021-12-12T06:01:10Z)
• 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)
• On the learnability of quantum neural networks [132.1981461292324]
  We consider the learnability of the quantum neural network (QNN) built on the variational hybrid quantum-classical scheme. We show that if a concept can be efficiently learned by QNN, then it can also be effectively learned by QNN even with gate noise.
  arXiv  Detail & Related papers  (2020-07-24T06:34:34Z)
• Forging quantum data: classically defeating an IQP-based quantum test [0.0]
  We describe a classical algorithm that can convince the verifier that the (classical) prover is quantum. We show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits.
  arXiv  Detail & Related papers  (2019-12-11T19: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.