The Power of Power-of-SWAP: Postselected Quantum Computation with the Exchange Interaction

arXiv:2603.28527 · quant-ph · Submitted 2026-03-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "The Power of Power-of-SWAP".

Kai: Exchange Quantum Polynomial Time (XQP) circuits, which utilize only computational basis SPAM and the isotropic Heisenberg exchange interaction, represent an intermediate complexity class between BPP and BQP.

Mira: First, who's behind it and why it matters.

Paper summary: Kai: So, summarizing what we've heard so far about "The Power of Power-of-SWAP: Postselected Quantum Computation with the Exchange Interaction," the core thesis is that XQP circuits are defined by using only computational basis SPAM and relying on the tunable isotropic Heisenberg exchange interaction to perform computation within decoherence-free subspaces.

Mira: The paper makes a couple of major claims here. First, they establish that postselected XQP(pi/four) circuits are universal for quantum computation, achieved by showing how any postselected BQP computation can be implemented using only the U(n pi/four) = (sqrt SWAP) n gate and the S gate derived from G(three pi/four) <ref:2603.28527#pg2>.

Lev: That claim about universality is substantial; it suggests that this restricted set of XQP circuits, those involving just sqrt SWAP gates, can actually achieve what we consider universal quantum computation when postselected.

Kai: Then they look at simulation hardness. They demonstrate that the efficient weak simulation of XQP circuits to multiplicative precision would cause the polynomial hierarchy to collapse to its third level, implying PH equals cubed, provided this doesn't hold true <ref:2603.28527#pg0>.

Mira: And they also offer a counterpoint regarding sampling; Theorem two states that sampling from XQP circuits to additive precision is unlikely because simulating that efficiently would enable efficient weak simulation of arbitrary BQP computations to additive error <ref:2603.28527#pg0,simulation of arbitrary BQP computations>.

Lev: So, we have these claims about universality and hardness, and they seem tightly linked through the simulation complexity results. This really frames XQP as a specific complexity class with distinct computational boundaries.

Kai: It's interesting because it moves the discussion beyond just whether a model is quantum or classical; it places XQP firmly in this intermediate territory between BPP and BQP.

Mira: And structurally, they tie the computation to the Gelfand–Tsetlin basis of the symmetric group and express probabilities as partition functions of six-vertex and Potts models, which adds this rich mathematical structure to their argument.

Lev: The connection to the six-vertex model is intriguing because it suggests that we aren't just dealing with abstract gates; there's a physical statistical system underlying the computation that we can analyze through known methods in condensed matter physics.

Conclusion: Kai: Looking at the title, "The Power of Power-of-SWAP: Postselected Quantum Computation with the Exchange Interaction," it really captures the essence of what they are investigating—how using just certain exchange interactions and postselection can define a specific type of quantum computation.

Mira: I think what this work contributes most is solidifying XQP's position in complexity theory by showing its relationship to simulation hardness across different error types. It moves the conversation from simply asking if a model is quantum to understanding exactly *how* it simulates other models.

Lev: For practical terms, the implication of Theorem three which shows that sqrt SWAP-generated circuits are semi-universal on any circuit size because they generate a group containing SV(n), means that for building systems based on these specific exchange gates, you could potentially achieve high levels of connectivity without needing an exponentially growing number of different gate types <ref:2603.28527#pg0>.

Kai: That's a practical point—if we can rely on those sqrt SWAP operations being semi-universal, it simplifies the hardware design aspect immensely for certain computational tasks.

Mira: And the overall implication is that the restriction to excluding singlet states gives us a clearer picture of what kind of quantum advantage you get when you only use this specific interaction. It shows that XQP has distinct properties compared to full BQP computation.

Lev: If these simulation hardness results hold up, it suggests we might have concrete complexity barriers we can study when designing fault-tolerant systems based on these exchange gates.

Kai: So, in simple terms, the paper lays out a very specific computational niche defined by the Heisenberg exchange interaction and postselection rules. It tells us exactly where this computation sits relative to what BPP and BQP can achieve in terms of simulation power.

Cavendish Laboratory, Department of Physics, University of Cambridge · Department of Computer Science, University of Oxford · International Centre for Theory of Quantum Technologies, University of Gdańsk

quant-ph

Submitted: 2026-03-30

Updated: 2026-10-02

Comments: 16+15 pages, 5 figures; v2 proves the universality of $\sqrt{SWAP}$

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: Exchange Quantum Polynomial Time (XQP) circuits, which utilize only computational basis SPAM and the isotropic Heisenberg exchange interaction, represent an intermediate complexity class between BPP

Key concepts

Isotropic Heisenberg Exchange Interaction
This interaction describes how qubits interact based on their spin, modeled by the Hamiltonian H = Xi Jij S⃗i · S⃗j. It is used to define the evolution of quantum circuits, where gates are defined by pulse angles that determine the SWAP operation and phase shifts.
Decoherence-Free Subspaces (DFS)
The computation relies on evolving qubits within specific subspaces that are protected from noise, using the exchange interaction. This allows for computation without needing access to singlet states, which are often required in standard quantum gates.
PostXQP(pi/4)
This refers to circuits computed by postselecting XQP circuits with a specific pulse angle of pi/4. The paper proves these postselected circuits are universal for quantum computation, meaning they can simulate any other quantum computation.
Polynomial Hierarchy (PH)
The polynomial hierarchy is a structure in complexity theory that classifies problems based on the number of alternating quantifiers needed to solve them. The work suggests that simulating XQP efficiently might reduce this hierarchy to its third level.

Terminology

Summary

Exchange Quantum Polynomial Time (XQP) circuits, which utilize only computational basis SPAM and the isotropic Heisenberg exchange interaction, represent an intermediate complexity class between BPP and BQP. This work introduces XQP as a sub-universal model by restricting universal computation to exclude access to singlet states, demonstrating that its efficient multiplicative-error simulation collapses the polynomial hierarchy to its third level, suggesting it occupies a unique position in quantum complexity theory.

Defining the Model and Interaction

The paper formalizes computation based on decoherence-free subspaces (DFS) using the tunable isotropic Heisenberg exchange interaction, where qubits are treated as spin-1/2 particles. The Hamiltonian is given by H = Xi Jij S⃗i · S⃗j, which can be rewritten in terms of the SWAP operation Eij: H = 1/2 Xi Jij Eij - 1/4 (Xi Ji). The evolution is described by exchange gates U(θ) = cos θ · 1 + i sin θ · SWAP, where the pulse angle θ is determined by the exchange coupling and duration. This model captures decoherence-free subspace computation without access to singlet states.

Key Results on Complexity and Simulation

The research establishes several critical complexity results regarding XQP circuits:

  1. PostXQP(π/4) = PostXQP = PostBQP (Theorem 1), proving that postselected XQP(π/4) circuits are universal for quantum computation. This is achieved by showing that any postselected BQP computation can be implemented on a postselected XQP(π/4) circuit using only the U(nπ/4) = (√SWAP)n gate and the S gate derived from G(3π/4).

  2. The efficient weak simulation of XQP circuits to multiplicative precision would collapse the polynomial hierarchy to its third level (Corollary 1), implying PH = ∆3, assuming it does not hold.

  3. Sampling from XQP circuits to additive precision is unlikely (Theorem 2), as simulating this efficiently would allow for efficient weak simulation of arbitrary BQP computations to additive error.

Structural Properties and Semi-Universality

The paper investigates the structural properties of XQP circuits by relating computational basis states to the Gelfand–Tsetlin basis of the symmetric group, and expressing output probabilities as partition functions of six-vertex and Potts models.

)& Theorem 3 proves that √SWAP-generated circuits are semi-universal [28] on any circuit size, meaning they generate a group which contains SV(n), the group of all SU(2)-invariant unitaries on n qubits. This implies that XQP(π/4) circuits are semi-universal for any number of qubits n. 3

)& Theorem 4 shows that XQP(π/4) forms a strict subset of XQP, meaning that under computational basis SPAM, sequences of √SWAP cannot approximate arbitrary exchange gates. This is demonstrated by analyzing the determinant ratio ∆J,K(U), which shows that XQP(π/4) circuits cannot approximate relative phases between isotypic components. 3

Entangling Power and Statistical Mechanics Connection

The paper quantifies the entangling capability of the exchange gates U(θ). Lemma 4 shows that the entangling power is ep0(U(θ)) = 1 - cos(4θ)/12 = sin 2(2θ)/6, with ep0√SWAP = 1/6. The XQP circuits are related to the six-vertex model, where their amplitudes can be represented as partition functions of a complex six-vertex model with external boundary conditions. Remark 6 concludes that without access to S gates (singlet state preparation and measurement), XQP circuits are not able to encode the partition function of the Potts model.

Hardness of Classical Simulation

The study explores the hardness of classical simulation up to additive error. Theorem 5 shows that if one can classically efficiently calculate quantities related to an XQP circuit U on 4n qubits, one can efficiently calculate quantities related to any BQP circuit U' on n qubits, proving that XQP circuits are hard to simulate to additive precision. This provides evidence against efficient weak classical simulation of XQP(π/4N) circuits.

Open Problems

The paper concludes by listing several open problems, including whether XQP(π/4) circuits can be efficiently classically sampled up to constant error in total variation distance, and the exact scaling of the degree t for which random XQP(π/4) circuits generate t-designs. The latter is currently unknown regarding its scaling with circuit size.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this paper, The Power of Power-of-SWAP: Postselected Quantum Computation with the Exchange Interaction. The core contribution is establishing that restricted quantum computation models (specifically XQP(π/4)) occupy an intermediate complexity class between BPP (classical polynomial time) and BQP (quantum polynomial time), suggesting that simulating them classically to multiplicative error is hard, while simulating them to additive error might be efficient.

Here are the specific improvements and capabilities for AI systems derived from this research:

The primary improvement lies in leveraging the structural properties of XQP circuits—which rely only on computational basis SPAM and a restricted set of exchange gates (specifically powers of the square root SWAP)—for more efficient, near-term quantum computation compared to full universal gate sets.

  1. Improvement in Near-Term Quantum Simulation:

  2. Improvement in Complexity Classification for Quantum Algorithms:

  3. New Sampling/Estimation Capabilities for Restricted Models:

  4. Enhanced Hardware Design and Error Mitigation Strategies:

Specific capabilities the improved AI system can achieve:

  1. A quantum simulation engine capable of efficiently simulating XQP circuits (postselected or non-postselected) on near-term hardware, where the gate set is restricted to computational basis SPAM and power-of-SWAP gates.

  2. An algorithm for postselecting BQP computations by mapping them onto XQP(π/4) circuits, allowing for a potentially more tractable classical simulation pathway (PostBPP = PP).

  3. A method to efficiently sample from the output distributions of XQP circuits to an additive precision error bound, offering a theoretical path toward proving the hardness of simulating arbitrary BQP computations classically.

  4. Hardware-aware quantum circuit design that exploits the isomorphism between XQP circuits and specific six-vertex/Potts models, allowing for the encoding and computation of lattice statistical mechanics partition functions within quantum measurement amplitudes (for specific boundary conditions).

Sources

Related papers