Quantum Computation Using Limited Interactions Rivals Standard Models’ Power

A new model termed Exchange Quantum Polynomial Time (XQP) utilises the exchange interaction for quantum computation. Jędrzej Burkat and colleagues at University of Oxford show that XQP circuits, constructed from restricted operations, occupy a computational complexity between classically tractable and fully quantum algorithms. Simulating these circuits efficiently would have key implications for computational complexity. It could potentially collapse the polynomial hierarchy. The team also prove that even a limited subset of these circuits remains challenging to simulate, and reveal connections to established mathematical structures like the Gelfand-Tsetlin basis and statistical physics models, suggesting suitability for implementation on near-term quantum hardware.

XQP simulation unlocks efficient modelling of broader quantum computational complexity

Additive-error simulation of the Exchange Quantum Polynomial Time (XQP) model now enables efficient additive-error simulation of arbitrary BQP computations, a feat previously unattainable. It establishes XQP as a new computational model utilising only computational basis states and the isotropic Heisenberg exchange interaction, effectively bridging the gap between classical and quantum computation. Structurally, XQP captures decoherence-free subspace computation without requiring access to singlet states, simplifying potential hardware implementations. This is particularly significant as singlet states are notoriously difficult to create and maintain with high fidelity in physical quantum systems, often being highly susceptible to decoherence. The isotropic Heisenberg exchange interaction, a fundamental interaction in quantum mechanics, provides a natural and potentially robust mechanism for implementing the required qubit interactions.

Circuits comprised solely of √SWAP gates, defining a pulse angle of π/4, remain remarkably difficult to simulate even with these restrictions, challenging existing classical simulation techniques. These circuits have been proven to be semi-universal, capable of generating a wide range of quantum operations, and also create ‘t-designs’ which ensure a uniform distribution of quantum states, maximising the ability to create entanglement within the XQP framework. A ‘t-design’ of order t guarantees that any observable measured on the output state of the circuit can be estimated with an error scaling as 1/t. This property is crucial for ensuring the reliability and accuracy of quantum computations performed using XQP circuits. Structural links have also been established between the computational basis states used in XQP and the Gelfand-Tsetlin basis of the symmetric group, with XQP output probabilities expressible as solutions to established mathematical models like the six-vertex and Potts models. The six-vertex model, originally developed in statistical mechanics to describe the properties of ice, provides a surprising connection, suggesting that the behaviour of XQP circuits can be understood through the lens of classical physics.

Gelfand-Tsetlin Basis Mapping of XQP Circuit Complexity

The Gelfand-Tsetlin basis, originally developed for representing the symmetric group, was central to defining the computational power of this new model. Mapping computational basis states within XQP circuits to this basis revealed a structural connection allowing circuit output probabilities to be expressed as partition functions, used in statistical physics to describe the probability of a system being in a particular state. This mapping proved important, enabling the analysis of circuit complexity by relating it to well-understood mathematical objects, sidestepping the need for direct simulation. The Gelfand-Tsetlin basis provides a convenient and efficient way to represent the states of the system, reducing the computational cost of analysing the circuit’s behaviour. Partition functions, central to statistical physics, quantify the accessible states of a system at a given temperature and provide a powerful tool for understanding its macroscopic properties.

The model’s computational complexity places it between the complexity classes BPP and BQP, and efficient simulation would have significant implications for the computational hierarchy. Specifically, if an efficient multiplicative-error simulation of XQP were possible, it would imply that the polynomial hierarchy collapses to its third level (PH ⊆ P³), a result with profound consequences for the field of computational complexity. Circuits are restricted to polynomial length, utilising gates acting on pairs of qubits, while measurements are performed in the computational basis to determine output probabilities. The approach operates within decoherence-free subspaces, specifically utilising k=3 and k=4 encodings, without accessing singlet states. Decoherence-free subspaces are designed to protect quantum information from certain types of noise, enhancing the robustness of the computation. The k=3 and k=4 encodings refer to specific methods for encoding quantum information within these subspaces, providing redundancy to mitigate the effects of errors.

Trading computational power for hardware simplification in quantum computing

XQP, a new quantum computation model, has been defined, operating using limited interactions and initial states, offering a potential pathway towards practical quantum devices. This simplification introduces a tension, however, as it captures decoherence-free subspace computation without relying on complex singlet states but also necessitates restricting the types of quantum operations permissible within the model. This trade-off between operational flexibility and hardware simplification presents a fundamental challenge, as fully universal quantum computation remains the ultimate goal for many. Achieving universality often requires a wider range of quantum gates and more complex interactions, increasing the difficulty of building and controlling a quantum computer.

While restricting operations limits full universality, this work nonetheless establishes a key stepping stone for building practical quantum computers. XQP offers a pathway to explore decoherence-free subspace computation, protecting quantum information from environmental noise, and positions it as a valuable model for near-term hardware development and experimental validation of quantum advantage. Demonstrating its position between the capabilities of classical and fully quantum algorithms, specifically between complexity classes BPP and BQP, suggests a unique balance of power and accessibility. The sub-universal model achieves computation without complex singlet states, simplifying potential hardware designs, and operates using only computational basis states and the isotropic Heisenberg exchange interaction. This focus on simplified interactions and robust encoding schemes makes XQP a promising candidate for implementation on existing and near-future quantum platforms, potentially accelerating the development of practical quantum technologies. Further research will focus on characterising the precise limitations of XQP and exploring potential methods for extending its capabilities while maintaining its hardware advantages.

Researchers demonstrated that Exchange Quantum Polynomial Time (XQP) circuits represent a computational model positioned between classical and fully quantum algorithms. This model achieves computation using only specific interactions and initial states, offering a potential pathway towards simplified quantum hardware. XQP captures decoherence-free subspace computation without requiring complex singlet states, which is beneficial for building robust quantum devices. The authors intend to further characterise the limitations of XQP and explore ways to extend its capabilities while preserving its hardware advantages.