The Power of Power-of-SWAP: Postselected Quantum Computation with the Exchange Interaction
Jędrzej Burkat, Sergii Strelchuk, Michał Studziński
Abstract
We introduce Exchange Quantum Polynomial Time (XQP) circuits, which comprise quantum computation using only computational basis SPAM and the isotropic Heisenberg exchange interaction. Structurally, this sub-universal model captures decoherence-free subspace computation without access to singlet states. We show that XQP occupies an intermediate position between BPP and BQP, as its efficient multiplicative-error simulation would collapse the polynomial hierarchy to its third level. We further provide evidence that additive-error simulation of XQP would enable efficient additive-error simulation of arbitrary BQP computations. Remarkably, the restricted family of XQP circuits consisting solely of gates remains hard to simulate to multiplicative error. We additionally prove that circuits generated by gates are semi-universal, generate -designs for the uniform distribution over -invariant unitaries, and maximise the entangling power within XQP. Finally, we derive structural results linking computational basis states in XQP to the Gelfand-Tsetlin basis of the symmetric group, and expressing XQP output probabilities as partition functions of the six-vertex and Potts models. Our findings indicate that XQP circuits are naturally suited to near-term hardware and provide a promising platform for experimental demonstrations of quantum computational advantage.
AI Impact Assessments
(3 models)Scientific Impact Assessment: "The Power of Power-of-SWAP: Postselected Quantum Computation with the Exchange Interaction"
1. Core Contribution
This paper introduces Exchange Quantum Polynomial Time (XQP), a restricted model of quantum computation that uses only computational basis state preparation/measurement (SPAM) and the isotropic Heisenberg exchange interaction. The key insight is that removing access to singlet states from decoherence-free subspace (DFS) computation yields a sub-universal yet classically hard-to-simulate intermediate complexity class. The central technical tool is an elegant postselected phase gadget G(θ) that implements a single-qubit phase gate e^{iθZ} using only exchange gates and computational basis postselection on two ancillae. This gadget enables the main results: (1) PostXQP(π/4) = PostBQP, implying multiplicative-error simulation would collapse PH to its third level; (2) evidence that additive-error simulation would enable efficient simulation of arbitrary BQP computations; (3) semi-universality of √SWAP-generated circuits; and (4) structural connections to the six-vertex and Potts models of statistical mechanics.
2. Methodological Rigor
The paper is technically thorough. The proof of PostXQP(π/4) = PostBQP (Theorem 1) is cleanly constructed through explicit logical gate synthesis using √SWAP and postselected S gates, with a complete universal gate set {X_L, Z_L, H_L, S_L, CZ_L, CS_L} constructed in the encoded space. The semi-universality proof (Theorem 3) carefully builds from the n=3 and n=4 cases using Young's orthogonal form, verifying density in SU(3) numerically (with supplementary Mathematica notebooks). The separation result XQP(π/4) ⊊ XQP (Theorem 4) uses an elegant determinant ratio argument that is phase-convention invariant. Theorem 5, showing that XQP amplitude estimation suffices for arbitrary BQP amplitude estimation, combines three technical lemmas involving Schur-Weyl duality, Clebsch-Gordan decompositions, and Young-Jucys-Murphy elements in a sophisticated way.
The additive-error hardness evidence (Theorem 2) is somewhat weaker than one might desire—it shows that simulating XQP(π/4N) to additive error enables simulating BQP on O(n/N) qubits, but doesn't fully establish #P-hardness of approximating XQP output probabilities. The authors honestly acknowledge this gap and frame it as the principal open problem.
3. Potential Impact
Near-term quantum advantage: The paper's most immediately impactful contribution may be practical. XQP(π/4) circuits require only √SWAP gates and computational basis SPAM—arguably the simplest non-trivial quantum computational model proposed as a candidate for quantum advantage demonstrations. The Heisenberg exchange interaction is native to spin-qubit platforms (quantum dots, donor qubits in silicon), where √SWAP has already been experimentally demonstrated. This makes XQP(π/4) a compelling target for near-term experiments, potentially lowering the bar for quantum supremacy demonstrations compared to random circuit sampling or boson sampling.
Complexity theory: XQP joins IQP, BosonSampling, DQC1, and QBall in the landscape of intermediate quantum complexity classes. The connections established—particularly the partial resolution of QBall's computational power on specific input states (from [47])—enrich the broader understanding of quantum computational advantage.
Statistical mechanics connections: The mapping of XQP amplitudes to six-vertex model partition functions, and the precise identification of S gates as the boundary between XQP and Potts model simulation capability, provides new structural insight into the computational complexity landscape of classical lattice models.
Representation theory insights: The detailed characterization of computational basis states in the Gelfand-Tsetlin basis (Section VIII) and the proof that exchange-based computation always requires external resources to prepare DFS logical states contribute useful technical tools for the community working on symmetric quantum circuits.
4. Timeliness & Relevance
The paper is highly timely. Silicon spin qubit platforms are rapidly maturing, with recent demonstrations of exchange-only qubits operating in parallel (Nature, 2025). Simultaneously, the theory of symmetric quantum circuits and SU(2)-invariant random circuits has seen significant recent progress. This work bridges both threads, providing complexity-theoretic motivation for exchange-based experiments while connecting to cutting-edge results on symmetric t-designs.
The paper also arrives amid growing interest in identifying the simplest possible quantum advantage experiments, as the field moves beyond proof-of-principle demonstrations toward scalable, verifiable quantum computational supremacy.
5. Strengths & Limitations
Strengths:
Limitations:
Overall, this is a substantial contribution that defines a natural, physically motivated complexity class and establishes its key properties through technically sophisticated arguments spanning multiple areas of mathematics and physics.
Generated Mar 31, 2026
Comparison History (55)
Paper 1 is more likely to have higher scientific impact: it introduces a new computational model (XQP) tied to realistic exchange-interaction hardware, provides multiple complexity-theoretic hardness results, and connects to t-designs, entangling power, and mappings to classical statistical models—broadening relevance across quantum computing, complexity theory, and many-body/stat-mech. Its methodological depth and timeliness for near-term “quantum advantage” demonstrations increase potential uptake. Paper 2 is intriguing experimentally and clarifies ghost-imaging physics, but its applications and cross-field reach are narrower and may be seen as a specialized optics result.
Paper 1 likely has higher scientific impact due to stronger novelty and breadth: it defines a new sub-universal computation model (XQP) tied to a physically natural interaction, establishes complexity-theoretic hardness connections (PH collapse implications, links to BQP simulation), and provides multiple deep structural results (t-designs, semi-universality, entangling optimality, mappings to six-vertex/Potts models). These span quantum computing theory, complexity, group representation, and statistical mechanics, and are timely for near-term quantum advantage. Paper 2 is valuable for sensing, but is more incremental within an existing paradigm and narrower in cross-field reach.
Paper 1 has higher potential impact: it introduces a new, hardware-motivated computational model (XQP) with strong complexity-theoretic evidence of classical hardness (PH collapse implications), connects restricted gate sets (√SWAP) to semi-universality and t-designs, and builds bridges to statistical mechanics (six-vertex/Potts partition functions) and representation theory. This breadth plus relevance to near-term quantum advantage experiments suggests wide cross-field influence. Paper 2 is timely and rigorous, but its central phenomenon is model-specific and concludes the enhancement likely vanishes in the thermodynamic limit, narrowing long-term impact.
Paper 1 offers deep theoretical insights by defining a new sub-universal quantum complexity class (XQP), establishing rigorous hardness-of-simulation bounds, and connecting it to statistical mechanics. These foundational results in quantum complexity theory and near-term quantum advantage typically have a broader and longer-lasting scientific impact across multiple subfields compared to the specific quantum networking protocol proposed in Paper 2.
Paper 1 introduces a fundamentally new computational model (XQP) with deep theoretical contributions: complexity-theoretic hardness results, connections to statistical mechanics partition functions, generation of t-designs, and links to representation theory of the symmetric group. It establishes a new intermediate complexity class with implications for quantum advantage demonstrations on near-term hardware. Paper 2 presents a useful but more incremental improvement to quantum state tomography using fan-out couplings. While experimentally validated, it addresses a narrower problem. Paper 1's breadth across complexity theory, algebra, and physics, combined with its novelty and timeliness for near-term quantum computing, gives it higher potential impact.
Paper 2 introduces a new sub-universal model (XQP) tied to a physically native interaction (Heisenberg exchange) and develops multiple strong complexity-theoretic and structural results (PH-collapse evidence for multiplicative-error simulation, links to BQP simulation, hardness persisting for sqrt(SWAP)-only circuits, semi-universality, t-designs, mappings to vertex/Potts models). This combination is novel, methodologically rigorous, timely for near-term advantage, and has broad impact across quantum complexity, many-body physics, and experiment. Paper 1 is useful for simulation/state-prep but appears more incremental and application-focused.
Paper 2 is likely to have higher impact: it introduces a new sub-universal computation model (XQP) tied to a physically native interaction (Heisenberg exchange), establishes strong complexity-theoretic evidence for classical hardness (PH collapse under efficient multiplicative-error simulation), and connects to broad areas (random circuits/t-designs, symmetric-group structure, and mappings to six-vertex/Potts models). These results are timely for near-term quantum advantage demonstrations and span quantum complexity, condensed matter/stat mech, and hardware-relevant gate sets. Paper 1 is rigorous and useful for strong-coupling open-system dynamics, but is a more incremental methodological extension within a narrower community.
Paper 1 introduces a novel computational model (XQP) with rich structural results connecting quantum complexity, statistical mechanics, representation theory, and near-term hardware. It provides multiple hardness results, establishes connections to t-designs and partition functions, and has direct experimental relevance for quantum advantage demonstrations. Paper 2 makes solid contributions classifying bosonic Hamiltonian simulation complexity, but is more incremental—unifying known results and identifying a complexity transition. Paper 1's breadth of impact across multiple fields, novelty of the XQP model, and practical relevance give it higher potential impact.
Paper 2 likely has higher impact: it defines a new restricted model (XQP) with strong complexity-theoretic evidence of quantum advantage, connects it to a single physically natural interaction (exchange/√SWAP) relevant to multiple hardware platforms, and establishes broad links to t-designs, entangling power, representation theory, and classical statistical mechanics (six-vertex/Potts). This breadth and foundational nature make it more cross-disciplinary and timely for near-term “advantage” experiments. Paper 1 is methodologically strong and practically useful for state preparation, but its impact is narrower to adiabatic/variational control methods.
Paper 2 makes fundamental contributions to quantum computational complexity theory by defining a new computational model (XQP), proving hardness results tied to polynomial hierarchy collapse, establishing connections to statistical mechanics partition functions, and demonstrating practical relevance to near-term hardware. These results have broad theoretical implications across complexity theory, quantum information, and mathematical physics. Paper 1, while technically interesting, is primarily an engineering framework combining known techniques (multigrid, CNNs, quantum circuits) validated only on simulators, with practical impact contingent on fault-tolerant quantum computers that don't yet exist.