I am excited to announce new work with Michał Studziński and Sergii Strelchuk! In our paper, we study the computational power of Exchange Quantum Polynomial Time (XQP) circuits, which consist of just two, extremely simple ingredients:

  1. State Preparation and Measurement (SPAM) in the computational basis.
  2. Application of the tunable, isotropic Heisenberg exchange Hamiltonian. This generates two-qubit gates of the form \(U(\theta) = \cos \theta \cdot \mathbf{1} + i \sin \theta \cdot \text{SWAP}\).

These circuits are inspired by Decoherence-Free Subspaces (DFSs), which enable universal quantum computation with the exchange interaction by encoding logical qubits into entangled states of physical qubits. Whilst DFS computations are powerful, they always requires access to singlet states, i.e. \(\frac{1}{\sqrt{2}}(\vert01\rangle-\vert10\rangle)\), which cannot be prepared out of a product state input with the exchange interaction alone. Removing this external singlet resource yields our XQP model.

Whilst XQP is not universal, we show that it lies in the intermediate complexity class between BPP and BQP, similarly to IQP and BosonSampling circuits. Remarkably, the classical simulation hardness of XQP persists even if we strip it to its bare minimum, by restricting each Heisenberg exchange unitary to a power of a \(\sqrt{\text{SWAP}}\) gate.

Circuits made up of \(\sqrt{\text{SWAP}}\) gates are pretty impressive – in addition to their classical simulation hardness, we prove they are semi-universal, with the ability to generate all \(SU(2)\)-invariant unitaries up to relative phases on irrep spaces.

You can read our preprint here: https://arxiv.org/abs/2603.28527.