Abstract
This paper establishes a complete computational complexity classification for the task of sampling from the output distributions of two-qubit commuting Hamiltonians. We present a sharp dichotomy theorem: a commuting Hamiltonian is either classically simulable or, if it is capable of generating entanglement from computational basis states, it is classically intractable to sample from (assuming the non-collapse of the polynomial hierarchy). This work provides a rigorous theoretical foundation for identifying quantum advantage in intermediate quantum computing models.
Introduction
A primary objective in quantum information science is the demonstration of "quantum supremacy"—the execution of a computational task on a quantum device that is provably beyond the reach of classical supercomputers. While universal quantum computers represent the long-term goal, their implementation remains technically challenging. This has catalyzed research into "intermediate" models of quantum computation, such as Instantaneous Quantum Polynomial-time (IQP) circuits, which are easier to implement but may still offer a provable quantum advantage.
Commuting Hamiltonians are particularly significant in this context because they are often easier to implement fault-tolerantly than non-commuting systems. However, a comprehensive classification of their power was previously missing. This research addresses a fundamental question: for any fixed two-qubit commuting Hamiltonian $H$, what is its inherent computational power? Is there a spectrum of complexity, or a sharp transition between the trivial and the hard?
The Dichotomy Theorem
The central result of this work is a "dichotomy theorem" for two-qubit commuting Hamiltonians. The complexity of these systems is determined entirely by their ability to generate entanglement. For any fixed two-qubit commuting Hamiltonian $H$, the model follows one of two paths:
- Efficiently Classically Simulable: If $H$ cannot create entanglement from the computational basis, the resulting output distribution can be sampled efficiently by a classical computer.
- Hard to Sample Classically: If $H$ can create entanglement, no classical machine (BPP) can sample from the output distribution with multiplicative error, unless the Polynomial Hierarchy (PH) collapses to the third level—a scenario considered highly unlikely in computational complexity theory.
This finding suggests that entanglement serves as the sole arbiter of complexity in these systems; there is no intermediate "slightly hard" regime.
Methodological Framework
The authors utilize a multi-disciplinary approach combining quantum circuit theory, complexity theory, and Lie theory to map the landscape of these Hamiltonians.
Local Diagonalizability
The proof begins by demonstrating that any two-qubit commuting Hamiltonian can be "locally diagonalized." Specifically, it can be expressed as $H = (U \otimes U)D(U^\dagger \otimes U^\dagger)$ for some single-qubit unitary $U$ and a diagonal matrix $D$. This structural simplification allows for a more systematic analysis of the Hamiltonian's action.
Postselection Gadgets and Lie Theory
To establish hardness, the authors employ "postselection gadgets." In complexity theory, postselection allows one to "fix" the outcome of specific measurements. While not physically realizable on a standard quantum computer, it is a powerful theoretical tool for probing the limits of a model. The authors show that a two-qubit Hamiltonian can be used to perform single-qubit operations $L(t)$ via these gadgets.
The core of the proof involves showing that the set of available postselected operations is "dense" in the group $SL(2, \mathbb{C})$. By applying Lie algebra techniques, the researchers demonstrate that combining these gadgets allows for the approximation of any single-qubit operation with high precision. This "postselected universality" is the critical lever used to prove classical hardness.
Handling Non-Unitary Operations
Because the gadgets often result in non-unitary operations, the authors adapted the Solovay-Kitaev theorem—traditionally used for unitaries—to show that these non-unitary gates can still efficiently approximate any desired operation. This ensures that the complexity results are robust even when the operations are not perfectly unitary.
Key Insights
The Entanglement Threshold
The research identifies a clear "litmus test" for quantum advantage: the ability to entangle. As soon as a commuting Hamiltonian can entangle two qubits from a computational basis state, it reaches a level of complexity that is classically intractable. This provides experimentalists with a straightforward criterion for selecting candidate systems for quantum advantage demonstrations.
The Exceptional Case
The authors identify a specific case, $H = X(\theta) \otimes X(\theta)$, which does not fit the primary proof technique involving $SL(2, \mathbb{C})$ density. However, this case was previously shown to be hard by other researchers using different methods, such as embedding the calculation of matrix permanents into the output distribution. By incorporating this result, the classification is made complete.
Limitations and Future Directions
While this work provides a comprehensive classification for two-qubit interactions, several avenues for future research remain:
- Multi-Qubit Interactions: The current classification is restricted to two-qubit interactions. A full classification for $k$-local commuting Hamiltonians (where $k \ge 3$) remains an open challenge.
- Non-Commuting Systems: Classifying the power of non-commuting fixed Hamiltonians is significantly more complex, as these systems can often lead to full universal quantum computation (BQP) more directly.
- Error Models: The current hardness results hold for "multiplicative error." Proving hardness for "additive error," which is more physically realistic for experimental verification, typically requires stronger complexity-theoretic conjectures.
- Encoding: The study focuses on fixed Hamiltonians without complex encodings. Determining how universality might emerge under arbitrary encodings (e.g., using multiple physical qubits to represent one logical qubit) is a major remaining hurdle in the field.
Summary updated