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

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{SWAP} gates remains hard to simulate to multiplicative error. We additionally prove that circuits generated by sqrt{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.