⚛️ quantum physics

Classical simulation of coherent crosstalk in surface codes

This paper presents a polynomial-time classical algorithm for simulating surface codes under coherent nearest-neighbor $ZZ$ crosstalk, while demonstrating that the simultaneous presence of single-qubit coherent noise and crosstalk renders efficient classical simulation impossible unless the polynomial hierarchy collapses.

Original authors: Andrew S. Darmawan, Yelyzaveta Kolesnyk, Robert Koenig

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew S. Darmawan, Yelyzaveta Kolesnyk, Robert Koenig

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve problems that would take ordinary machines thousands of years, but they are incredibly fragile. To make them work, scientists must protect the delicate information they hold from the constant jostling of the environment. One of the most promising ways to do this is by using "surface codes," a method that spreads a single piece of information across a grid of many physical particles. If one particle gets corrupted, the system can detect the error by checking how the particles interact with their neighbors and then fix it. This process relies on a delicate balance: the system must be robust enough to handle noise, yet simple enough that we can predict how it will behave. For years, researchers have understood how these codes handle random, unpredictable errors, but a more subtle and dangerous type of noise has remained a mystery. This is "coherent crosstalk," where neighboring particles influence each other in a synchronized, wave-like manner rather than just flipping randomly. Because these waves can interfere with one another, they create complex patterns that are notoriously difficult to predict, leaving scientists unsure if their error-correction systems can truly withstand them.

A team of researchers has now cracked this problem, providing a way to simulate how these synchronized errors behave on a large scale. They developed a new computer algorithm that can quickly calculate the likely outcomes of these errors for surface codes containing thousands of particles. Their work reveals a surprising duality in the nature of quantum noise. When the noise consists only of these synchronized interactions between neighbors, the problem is solvable; the researchers found a clever way to break the complex grid down into two simpler, independent puzzles that can be solved instantly. However, the situation changes drastically if even a tiny amount of a different kind of noise is added. If the system is subjected to both the synchronized neighbor interactions and small, individual rotations of the particles, the problem becomes computationally intractable for any efficient classical computer, unless the fundamental rules of computer science are completely rewritten.

The researchers focused on a specific type of quantum error where neighboring particles interact through a force that causes them to rotate in unison. In the real world, this happens when superconducting qubits, the building blocks of many quantum computers, are placed close together and their magnetic fields leak into one another. To understand if the surface code could survive this, the team needed to simulate the system's response. Previous attempts to model this were limited to very small grids or relied on approximations that might miss critical details. The new algorithm, however, can handle grids with a distance of 37, which corresponds to 1,369 physical particles. It does this by realizing that the complex web of interactions on a rotated grid can be mapped onto two separate, simpler grids. Instead of trying to solve the massive, tangled problem all at once, the algorithm splits the task into two smaller, independent problems involving single-particle errors. It then combines the results to give an exact picture of what happens to the whole system. This approach allows them to generate thousands of simulated error scenarios in just a few milliseconds, a feat that was previously impossible for such large systems.

Using this powerful tool, the team tested how well a standard error-correction method, known as minimum-weight perfect matching, performs against these synchronized errors. They compared the real, wave-like noise against a simplified model where the interactions were treated as random, independent mistakes. The results were stark. When the noise was coherent and synchronized, the error-correction system failed much more often than the simplified model predicted. At a specific level of noise strength, the system suffered a logical error rate nearly fifty times higher than when the same noise was treated as random. This suggests that the wave-like nature of the interference makes the errors much harder to catch and fix. By running simulations on grids of increasing size, the researchers estimated the point at which the system would stop working entirely. They found that the threshold for coherent noise is significantly lower than for random noise, meaning the system can tolerate much less of this synchronized interference before it breaks down.

The study also uncovered a profound theoretical limit. While the researchers could efficiently simulate the synchronized neighbor errors, they proved that adding even a small amount of individual particle rotation to the mix changes the game entirely. In this combined scenario, the pattern of errors becomes so complex that it is linked to a class of problems that are believed to be unsolvable by any efficient classical computer, unless the polynomial hierarchy collapses. The researchers showed that if a fast algorithm existed to predict the outcomes of this combined noise, it would imply a collapse of the mathematical hierarchy that underpins modern computing theory. This means that for the most general case of quantum noise, we may never be able to perfectly predict the behavior of these large systems using standard computers. The only way to know what happens is to build the actual quantum machine and observe it.

The implications of these findings are twofold. First, they provide a practical tool for engineers building quantum computers. The new algorithm allows them to test their designs against realistic, wave-like noise without needing to build the hardware first, revealing that current error-correction strategies may need to be more robust than previously thought. Second, the work highlights a fundamental boundary in our ability to understand quantum systems. It shows that while some types of quantum noise can be tamed and predicted, the moment we introduce a mix of different noise types, the complexity explodes beyond our reach. The researchers emphasize that their results are based on simulations and theoretical proofs, not on physical experiments, but they offer a clear warning: the wave-like interference of errors is a potent threat that cannot be ignored, and the tools we use to fight it must be as sophisticated as the noise itself.

Technical Summary: Classical Simulation of Coherent Crosstalk in Surface Codes

Problem Statement
Surface codes are a leading candidate for robust quantum memory, yet their resilience to coherent noise remains an open question. While stochastic Pauli noise is well-understood and efficiently simulable via the Gottesman-Knill theorem, coherent errors—specifically nearest-neighbor $ZZ$ crosstalk arising from residual interactions in superconducting qubits—pose a significant challenge. Unlike probabilistic noise, coherent noise introduces interference effects that can drastically alter logical error rates.

Prior to this work, efficient exact classical simulation algorithms existed for coherent single-qubit $Z$ -rotations on surface codes. However, no such algorithm was available for nearest-neighbor coherent crosstalk at distances large enough to study threshold scaling. Existing methods for crosstalk were limited to small codes ( $d \leq 3$ ), relied on uncontrolled approximations, or incurred exponential sampling costs. Furthermore, the computational complexity of simulating the combination of single-qubit rotations and crosstalk was unknown.

Methodology
The authors address two distinct regimes of coherent noise on rotated surface codes of odd distance $d$ :

Pure Coherent Crosstalk: Noise described by the unitary $U_{nn}(\theta) = \prod_{e \in E} e^{i\theta_e Z_q Z_{q'}}$ .
Combined Coherent Noise: Noise described by $U_{comb}(\phi, \theta) = U_{sq}(\phi) U_{nn}(\theta)$ , involving both single-qubit $Z$ -rotations and crosstalk.

For the first regime, the authors exploit a structural property of rotated surface codes. They demonstrate that the set of $X$ -stabilizers can be partitioned into two disjoint sets, $A$ and $B$ , such that any nearest-neighbor $ZZ$ -error affects stabilizers entirely within one set. This allows the syndrome distribution of the crosstalk noise on the original rotated code to be factorized exactly into the product of syndrome distributions of two independent auxiliary standard (unrotated) surface codes of distance $D = (d+1)/2$ . The crosstalk angles on the original lattice map to effective single-qubit $Z$ -rotation angles on these auxiliary codes.

For the second regime, the authors analyze the syndrome distribution as the output of an Instantaneous Quantum Polynomial-time (IQP) circuit. They show that the interaction graph of the combined noise corresponds to a "king lattice" (a grid where sites are connected to horizontal, vertical, and diagonal neighbors). This graph is non-planar.

Key Contributions

Polynomial-Time Simulation Algorithm for Crosstalk:
The authors present Algorithm 1, a classical algorithm that samples from the syndrome distribution of a rotated surface code under coherent nearest-neighbor crosstalk in $O(d^6)$ arithmetic operations.
- Mechanism: The algorithm reduces the problem to sampling from two independent standard surface codes with single-qubit coherent noise, utilizing existing efficient samplers based on fermionic linear optics (FLO) [18, 19].
- Exactness: The algorithm provides an exact sample (with $\epsilon=0$ multiplicative error) assuming exact arithmetic, or an arbitrarily close approximation with polynomial bit cost for arbitrary real angles.
- Recovery: For odd-distance rotated codes, the authors prove that the logical action after error correction is deterministic (either identity or logical $Z$ ) based solely on the parity of the correction weight, independent of the encoded state.
Hardness of Sampling for Combined Noise:
The authors establish a complexity-theoretic obstruction to efficiently sampling the syndrome distribution when both single-qubit rotations and crosstalk are present.
- Result: Unless the polynomial hierarchy collapses to its third level, no classical algorithm can sample from the syndrome distribution of the combined noise model with a constant multiplicative error guarantee.
- Proof: This is proven by mapping the syndrome distribution to the output of a universal IQP circuit on a king lattice. The construction uses postselection gadgets to demonstrate universality, implying that efficient sampling would allow the simulation of postselected quantum computation.

Numerical Results
Using the proposed algorithm, the authors performed numerical simulations on rotated surface codes with distances $d \in \{13, 21, 29, 37\}$ (up to 1,369 physical qubits) to assess the performance of the Minimum-Weight Perfect Matching (MWPM) decoder.

Comparison: They compared uniform coherent crosstalk against a "Pauli twirl" model, where each interaction is replaced by a probabilistic $ZZ$ error.
Findings: The residual logical error under coherent crosstalk is substantially larger than under the Pauli twirl at the same interaction strength. For example, at $d=37$ and $\theta/\pi = 0.040$ , the logical error metric was approximately 49 times larger for coherent noise than for the twirled model.
Threshold Extrapolation: Joint finite-size scaling fits yielded a threshold extrapolation of $\theta_c/\pi \approx 0.0342$ for coherent crosstalk, compared to $\theta_c/\pi \approx 0.0493$ for the Pauli twirl. The authors note that while the relative ordering is stable, the absolute threshold values are model-dependent due to poor goodness-of-fit in the scaling ansatz.
Performance: The algorithm successfully generated samples for $d=37$ in approximately 5 ms per syndrome.

Significance and Claims
The paper claims to provide the first efficient exact classical simulation algorithm for nearest-neighbor coherent crosstalk on rotated surface codes at distances sufficient for threshold analysis. This capability enables the study of how coherent interference affects logical error rates and decoder performance, revealing that standard decoders (like MWPM) are significantly less effective against coherent crosstalk than against its incoherent Pauli approximation.

Furthermore, the work delineates a sharp boundary in computational complexity: while crosstalk alone is efficiently simulable, the addition of single-qubit rotations renders the sampling problem computationally hard (under standard complexity assumptions). This highlights that the noise model affects not only the physical performance of the code but also the feasibility of classically assessing that performance.

The authors remain modest regarding the extrapolated thresholds, explicitly stating they are "model-dependent extrapolations" rather than controlled asymptotic limits, and acknowledge that the current reduction relies on ideal syndrome measurements, leaving measurement errors as an open practical problem.

Technical Summary: Classical Simulation of Coherent Crosstalk in Surface Codes

More like this