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:2603.28527

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

Jędrzej Burkat, Sergii Strelchuk, Michał Studziński

quant-phSubmitted Mar 30, 2026• Announced Mar 31, 2026• 0 citations
v1 · Mar 30, 2026v2 · Oct 2, 2026
arXivHTMLPDF

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 $\sqrt{\mathrm{SWAP}}$ gates remains hard to simulate to multiplicative error. We additionally prove that circuits generated by $\sqrt{\mathrm{SWAP}}$ gates are semi-universal, generate $t$-designs for the uniform distribution over $SU(2)$-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.

Comments
25 pages, 5 figures

Related papers

Computational complexity and simulability of non-Hermitian quantum dynamics

Brian Barch, Daniel A. Lidar

Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: If coherent nonunitary evolution with renormalization could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP ( U ) as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on O ( 1 ) qubits that is not proportional to a unitary, with the state renormalized after each use of U . We prove that this model is powerful enough to decide every language in PostBQP (equivalently PP ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate U , NHBQP ( U ) = PostBQP = PP . PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a compensating cost limiting its efficiency. Additionally, we study simulation complexity of restricted classes of nonunitary systems by purifying them to postselected unitary evolution in a form preserving system locality. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability Ω ( 2 − poly ( n ) ) . Thus, adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.

arXiv:2506.03435•Physical Review Research•Jun 24, 2026•0 citations

Energetic suppression of decoherence in exchange-only quantum computation

Yaakov S. Weinstein, C. Stephen Hellberg

Universal quantum computation requiring only the Heisenberg exchange interaction and suppressing decoherence via an energy gap is presented. The combination of an always-on exchange interaction between the three physical qubits comprising the encoded qubit and a global magnetic field generates an energy gap between the subspace of interest and all other states. This energy gap suppresses decoherence. Always-on exchange couplings greatly simplify hardware specifications and the implementation of inter-logical-qubit gates. A controlled phase gate can be implemented using only three Heisenberg exchange operations all of which can be performed simultaneously.

arXiv:quant-ph/0408037•Physical Review A•Aug 17, 2005•30 citations

Symmetry Protected Quantum Computation

Michael Hartley Freedman, Matthew B. Hastings, Modjtaba Shokrian Zini

We consider a model of quantum computation using qubits where it is possible to measure whether a given pair are in a singlet (total spin 0 ) or triplet (total spin 1 ) state. The physical motivation is that we can do these measurements in a way that is protected against revealing other information so long as all terms in the Hamiltonian are SU(2) -invariant. We conjecture that this model is equivalent to BQP. Towards this goal, we show: (1) this model is capable of universal quantum computation with polylogarithmic overhead if it is supplemented by single qubit X and Z gates. (2) Without any additional gates, it is at least as powerful as the weak model of "permutational quantum computation" of Jordan [14, 18]. (3) With postselection, the model is equivalent to PostBQP.

arXiv:2105.04649•Quantum•Sep 28, 2021•9 citations

Quantum Information Processing using the Power-of-SWAP

Mrittunjoy Guha Majumdar

This project is a comprehensive investigation into the application of the exchange interaction, particularly with the realization of the SWAP^1/n quantum operator, in quantum information processing. We study the generation, characterization and application of entanglement in such systems. Given the non-commutativity of neighbouring SWAP^1/n gates, the mathematical study of combinations of these gates is an interesting avenue of research that we have explored, though due to the exponential scaling of the complexity of the problem with the number of qubits in the system, numerical techniques, though good for few-qubit systems, are found to be inefficient for this research problem when we look at systems with higher number of qubits. Since the group of SWAP^1/n operators is found to be isomorphic to the symmetric group Sn, we employ group-theoretic methods to find the relevant invariant subspaces and associated vector-states. Some interesting patterns of states are found including onedimensional invariant subspaces spanned by W-states and the Hamming-weight preserving symmetry of the vectors spanning the various invariant subspaces. We also devise new ways of characterizing entanglement and approach the separability problem by looking at permutation symmetries of subsystems of quantum states. This idea is found to form a bridge with the entanglement characterization tool of Peres-Horodecki’s Partial Positive Transpose (PPT), for mixed quantum states. We also look at quantum information taskoriented ‘distance’ measures of entanglement, besides devising a new entanglement witness in the ‘engle’. In terms of applications, we define five different formalisms for quantum computing: the circuit-based model, the encoded qubit model, the cluster-state model, functional quantum computation and the qudit-based model. Later in the thesis, we explore the idea of quantum computing based on decoherence-free subspaces. We also investigate ways of applying the SWAP^1/n in entanglement swapping for quantum repeaters, quantum communication protocols and quantum memory.

•Jul 27, 2018•0 citations

Universal Quantum Computation with Spin- 1 / 2 Pairs and Heisenberg Exchange

Jeremy Levy

An efficient and intuitive framework for universal quantum computation is presented that uses pairs of spin-1/2 particles to form logical qubits and a single physical interaction, Heisenberg exchange, to produce all gate operations. Only two Heisenberg gate operations are required to produce a controlled pi-phase shift, compared to nineteen for exchange-only proposals employing three spins. Evolved from well-studied decoherence-free subspaces, this architecture inherits immunity from collective decoherence mechanisms. The simplicity and adaptability of this approach should make it attractive for spin-based quantum computing architectures.

arXiv:quant-ph/0101057•Physical Review Letters•Sep 17, 2002•407 citations

Encoded Universality from a Single Physical Interaction

Julia Kempe, Dave Bacon, David Peter Divincenzo +1 more

We present a theoretical analysis of the paradigm of encoded universality, using a Lie algebraic analysis to derive specific conditions under which physical interactions can provide universality. We discuss the significance of the tensor product structure in the quantum circuit model and use this to define the conjoining of encoded qudits. The construction of encoded gates between conjoined qudits is discussed in detail. We illustrate the general procedures with several examples from exchange-only quantum computation. In particular, we extend our earlier results showing universality with the isotropic exchange interaction to the derivation of encoded universality with the anisotropic exchange interaction, i.e., to the XY model. In this case the minimal encoding for universality is into qutrits rather than into qubits as was the case for isotropic (Heisenberg) exchange. We also address issues of fault-tolerance, leakage and correction of encoded qudits.

arXiv:quant-ph/0112013•Dec 3, 2001•0 citations
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 SWAP\sqrt{\mathrm{SWAP}}SWAP​ gates remains hard to simulate to multiplicative error. We additionally prove that circuits generated by SWAP\sqrt{\mathrm{SWAP}}SWAP​ gates are semi-universal, generate ttt-designs for the uniform distribution over SU(2)SU(2)SU(2)-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.
Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: If coherent nonunitary evolution with renormalization could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP ( U ) as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on O ( 1 ) qubits that is not proportional to a unitary, with the state renormalized after each use of U . We prove that this model is powerful enough to decide every language in PostBQP (equivalently PP ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate U , NHBQP ( U ) = PostBQP = PP . PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a compensating cost limiting its efficiency. Additionally, we study simulation complexity of restricted classes of nonunitary systems by purifying them to postselected unitary evolution in a form preserving system locality. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability Ω ( 2 − poly ( n ) ) . Thus, adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.
Universal quantum computation requiring only the Heisenberg exchange interaction and suppressing decoherence via an energy gap is presented. The combination of an always-on exchange interaction between the three physical qubits comprising the encoded qubit and a global magnetic field generates an energy gap between the subspace of interest and all other states. This energy gap suppresses decoherence. Always-on exchange couplings greatly simplify hardware specifications and the implementation of inter-logical-qubit gates. A controlled phase gate can be implemented using only three Heisenberg exchange operations all of which can be performed simultaneously.
We consider a model of quantum computation using qubits where it is possible to measure whether a given pair are in a singlet (total spin 0 ) or triplet (total spin 1 ) state. The physical motivation is that we can do these measurements in a way that is protected against revealing other information so long as all terms in the Hamiltonian are SU(2) -invariant. We conjecture that this model is equivalent to BQP. Towards this goal, we show: (1) this model is capable of universal quantum computation with polylogarithmic overhead if it is supplemented by single qubit X and Z gates. (2) Without any additional gates, it is at least as powerful as the weak model of "permutational quantum computation" of Jordan [14, 18]. (3) With postselection, the model is equivalent to PostBQP.
This project is a comprehensive investigation into the application of the exchange interaction, particularly with the realization of the SWAP^1/n quantum operator, in quantum information processing. We study the generation, characterization and application of entanglement in such systems. Given the non-commutativity of neighbouring SWAP^1/n gates, the mathematical study of combinations of these gates is an interesting avenue of research that we have explored, though due to the exponential scaling of the complexity of the problem with the number of qubits in the system, numerical techniques, though good for few-qubit systems, are found to be inefficient for this research problem when we look at systems with higher number of qubits. Since the group of SWAP^1/n operators is found to be isomorphic to the symmetric group Sn, we employ group-theoretic methods to find the relevant invariant subspaces and associated vector-states. Some interesting patterns of states are found including onedimensional invariant subspaces spanned by W-states and the Hamming-weight preserving symmetry of the vectors spanning the various invariant subspaces. We also devise new ways of characterizing entanglement and approach the separability problem by looking at permutation symmetries of subsystems of quantum states. This idea is found to form a bridge with the entanglement characterization tool of Peres-Horodecki’s Partial Positive Transpose (PPT), for mixed quantum states. We also look at quantum information taskoriented ‘distance’ measures of entanglement, besides devising a new entanglement witness in the ‘engle’. In terms of applications, we define five different formalisms for quantum computing: the circuit-based model, the encoded qubit model, the cluster-state model, functional quantum computation and the qudit-based model. Later in the thesis, we explore the idea of quantum computing based on decoherence-free subspaces. We also investigate ways of applying the SWAP^1/n in entanglement swapping for quantum repeaters, quantum communication protocols and quantum memory.
An efficient and intuitive framework for universal quantum computation is presented that uses pairs of spin-1/2 particles to form logical qubits and a single physical interaction, Heisenberg exchange, to produce all gate operations. Only two Heisenberg gate operations are required to produce a controlled pi-phase shift, compared to nineteen for exchange-only proposals employing three spins. Evolved from well-studied decoherence-free subspaces, this architecture inherits immunity from collective decoherence mechanisms. The simplicity and adaptability of this approach should make it attractive for spin-based quantum computing architectures.
We present a theoretical analysis of the paradigm of encoded universality, using a Lie algebraic analysis to derive specific conditions under which physical interactions can provide universality. We discuss the significance of the tensor product structure in the quantum circuit model and use this to define the conjoining of encoded qudits. The construction of encoded gates between conjoined qudits is discussed in detail. We illustrate the general procedures with several examples from exchange-only quantum computation. In particular, we extend our earlier results showing universality with the isotropic exchange interaction to the derivation of encoded universality with the anisotropic exchange interaction, i.e., to the XY model. In this case the minimal encoding for universality is into qutrits rather than into qubits as was the case for isotropic (Heisenberg) exchange. We also address issues of fault-tolerance, leakage and correction of encoded qudits.