Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40279

Classical simulation of coherent crosstalk in surface codes

Andrew S. Darmawan, Yelyzaveta Kolesnyk, Robert Koenig

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We give a polynomial-time classical algorithm which samples from the syndrome distribution of a surface code state corrupted by coherent nearest-neighbor $ZZ$ crosstalk. Our algorithm complements the known efficient simulation algorithms for coherent single-qubit errors in the surface code. When both single-qubit coherent noise and coherent crosstalk are present, we find a complexity-theoretic obstruction to efficient simulation: unless the polynomial hierarchy collapses, there is no efficient classical algorithm for sampling from the syndrome distribution, even up to a constant multiplicative error. This is obtained by connecting the syndrome distribution under coherent noise to the output distribution of certain IQP circuits associated with a non-planar graph.

Related papers

Non-Clifford Crosstalk Noise in Surface Codes Using Hybrid Stabilizer-Tensor Network Methods

Ben Harper, Azar C. Nakhl, Martin Sevior +1 more

Scalable realisation of quantum computing is reliant on the development of fault tolerant devices. Analysis of quantum error correction protocols typically considers incoherent noise models or noise-free syndrome measurements. While this is simple to simulate classically and straightforward to compute analytically, these simplifications are unable to capture the full dynamics of a noisy quantum system. In this work we use advanced hybrid stabilizer-tensor network simulation techniques to simulate coherent quantum crosstalk noise during syndrome extraction on a surface code. We show that the inclusion of coherence increases logical error rates and lowers the code threshold. In addition, we show that the specific distribution of the noise can quantitatively change logical error rates. The methods in this work allow simulation of quantum error correction with noise models previously inaccessible to classical simulation, providing new insights on the effect of crosstalk noise on quantum error correction codes.

quant-pharXiv:2605.29514•May 29, 2026•0 citations

Sampling-based quasiprobability simulation for fault-tolerant quantum error correction on the surface codes under coherent noise

Shigeo Hakkaku, Kosuke Mitarai, Keisuke Fujii

We propose a sampling-based simulation for fault-tolerant quantum error correction under coherent noise. A mixture of incoherent and coherent noise, possibly due to over-rotation, is decomposed into Clifford channels with a quasiprobability distribution. Then, an unbiased estimator of the logical error probability is constructed by sampling Clifford channels with an appropriate postprocessing. We characterize the sampling cost via the channel robustness and find that the proposed sampling-based method is feasible even for planar surface codes with relatively large code distances intractable for full state-vector simulations. As a demonstration, we simulate repetitive faulty syndrome measurements on the planar surface code of distance 5 with 81 qubits. We find that the coherent error increases the logical error rate. This is a practical application of the quasiprobability simulation for a meaningful task and would be useful to explore experimental quantum error correction on the near-term quantum devices.

arXiv:2105.04478•Physical Review Research•Nov 19, 2021•8 citations

Threshold error rates for the toric and surface codes

D. S. Wang, Austin G. Fowler, Ashley M. Stephens +1 more

The surface code scheme for quantum computation features a 2d array of nearest-neighbor coupled qubits yet claims a threshold error rate approaching 1% (NJoP 9:199, 2007). This result was obtained for the toric code, from which the surface code is derived, and surpasses all other known codes restricted to 2d nearest-neighbor architectures by several orders of magnitude. We describe in detail an error correction procedure for the toric and surface codes, which is based on polynomial-time graph matching techniques and is efficiently implementable as the classical feed-forward processing step in a real quantum computer. By direct simulation of this error correction scheme, we determine the threshold error rates for the two codes (differing only in their boundary conditions) for both ideal and non-ideal syndrome extraction scenarios. We verify that the toric code has an asymptotic threshold of p = 15.5% under ideal syndrome extraction, and p = 7.8 10^-3 for the non-ideal case, in agreement with prior work. Simulations of the surface code indicate that the threshold is close to that of the toric code.

arXiv:0905.0531•May 5, 2009•17 citations

How to Simulate Quantum Measurement without Computing Marginals

Sergey B. Bravyi, David Gosset, Yinchen Liu

We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state in the standard basis, that is, sampling a bit string from the probability distribution determined by the Born rule. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. Two classes of quantum states are considered: output states of polynomial-size quantum circuits, and ground states of local Hamiltonians with an inverse polynomial spectral gap. We show that our algorithms can significantly accelerate quantum circuit simulations based on tensor network contraction or low-rank stabilizer decompositions. As another striking consequence we obtain the first efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph and any schedule of measurements.

arXiv:2112.08499•Physical Review Letters•Jun 1, 2022•24 citations

Efficient simulation of noisy IQP circuits with amplitude-damping noise

Shravan Shravan, Mohsin Raza, Ariel Shlosberg

Efficient classical simulation of noisy intermediate-scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise or involve sufficient randomness. However, there are limited results for circuits undergoing non-unital noise in the absence of randomness. In this work, we present a polynomial-time classical algorithm to sample from the output distributions of amplitude-damped instantaneous quantum polynomial (IQP) circuits. Our algorithm works for circuits generated by arbitrary $l$-local diagonal gates with depth $d = Ω(\log(n))$, undergoing constant amplitude-damping noise.

quant-pharXiv:2604.05036•Apr 8, 2026•0 citations

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Michael J. Bremner, Richard Jozsa, Dan J. Shepherd

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.

arXiv:1005.1407•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 11, 2010•308 citations
We give a polynomial-time classical algorithm which samples from the syndrome distribution of a surface code state corrupted by coherent nearest-neighbor ZZZZZZ crosstalk. Our algorithm complements the known efficient simulation algorithms for coherent single-qubit errors in the surface code. When both single-qubit coherent noise and coherent crosstalk are present, we find a complexity-theoretic obstruction to efficient simulation: unless the polynomial hierarchy collapses, there is no efficient classical algorithm for sampling from the syndrome distribution, even up to a constant multiplicative error. This is obtained by connecting the syndrome distribution under coherent noise to the output distribution of certain IQP circuits associated with a non-planar graph.
Scalable realisation of quantum computing is reliant on the development of fault tolerant devices. Analysis of quantum error correction protocols typically considers incoherent noise models or noise-free syndrome measurements. While this is simple to simulate classically and straightforward to compute analytically, these simplifications are unable to capture the full dynamics of a noisy quantum system. In this work we use advanced hybrid stabilizer-tensor network simulation techniques to simulate coherent quantum crosstalk noise during syndrome extraction on a surface code. We show that the inclusion of coherence increases logical error rates and lowers the code threshold. In addition, we show that the specific distribution of the noise can quantitatively change logical error rates. The methods in this work allow simulation of quantum error correction with noise models previously inaccessible to classical simulation, providing new insights on the effect of crosstalk noise on quantum error correction codes.
We propose a sampling-based simulation for fault-tolerant quantum error correction under coherent noise. A mixture of incoherent and coherent noise, possibly due to over-rotation, is decomposed into Clifford channels with a quasiprobability distribution. Then, an unbiased estimator of the logical error probability is constructed by sampling Clifford channels with an appropriate postprocessing. We characterize the sampling cost via the channel robustness and find that the proposed sampling-based method is feasible even for planar surface codes with relatively large code distances intractable for full state-vector simulations. As a demonstration, we simulate repetitive faulty syndrome measurements on the planar surface code of distance 5 with 81 qubits. We find that the coherent error increases the logical error rate. This is a practical application of the quasiprobability simulation for a meaningful task and would be useful to explore experimental quantum error correction on the near-term quantum devices.
The surface code scheme for quantum computation features a 2d array of nearest-neighbor coupled qubits yet claims a threshold error rate approaching 1% (NJoP 9:199, 2007). This result was obtained for the toric code, from which the surface code is derived, and surpasses all other known codes restricted to 2d nearest-neighbor architectures by several orders of magnitude. We describe in detail an error correction procedure for the toric and surface codes, which is based on polynomial-time graph matching techniques and is efficiently implementable as the classical feed-forward processing step in a real quantum computer. By direct simulation of this error correction scheme, we determine the threshold error rates for the two codes (differing only in their boundary conditions) for both ideal and non-ideal syndrome extraction scenarios. We verify that the toric code has an asymptotic threshold of p = 15.5% under ideal syndrome extraction, and p = 7.8 10^-3 for the non-ideal case, in agreement with prior work. Simulations of the surface code indicate that the threshold is close to that of the toric code.
We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state in the standard basis, that is, sampling a bit string from the probability distribution determined by the Born rule. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. Two classes of quantum states are considered: output states of polynomial-size quantum circuits, and ground states of local Hamiltonians with an inverse polynomial spectral gap. We show that our algorithms can significantly accelerate quantum circuit simulations based on tensor network contraction or low-rank stabilizer decompositions. As another striking consequence we obtain the first efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph and any schedule of measurements.
Efficient classical simulation of noisy intermediate-scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise or involve sufficient randomness. However, there are limited results for circuits undergoing non-unital noise in the absence of randomness. In this work, we present a polynomial-time classical algorithm to sample from the output distributions of amplitude-damped instantaneous quantum polynomial (IQP) circuits. Our algorithm works for circuits generated by arbitrary lll-local diagonal gates with depth d=Ω(log⁡(n))d = Ω(\log(n))d=Ω(log(n)), undergoing constant amplitude-damping noise.
We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.