New Complexity Classes Defined for Optimisation and Statistical Problems

Kunal Marwaha and James Sud at University of Chicago investigated the computational complexity of 2-local Hamiltonian problems, revealing a clear phase transition between tractable and intractable scenarios. These problems fall into one of three complexity phases: QMA-complete, StoqMA-complete, or a newly defined problem termed EPR. The work clarifies the relationship between energy level ordering and computational difficulty, potentially pinpointing EPR as the key boundary between easily solvable and exceptionally challenging local Hamiltonians. The team’s new use of perturbative gadgets, including a spin chain analysed via the Jordan-Wigner transformation, offers a novel approach to understanding and classifying these fundamental problems in statistical mechanics and optimisation.

Energy level ordering defines three complexity phases in 2-local Hamiltonian systems

A five-fold increase in the ability to classify the computational complexity of 2-local Hamiltonian problems is now possible. Moving from simply identifying problems as ‘easy’ or ‘hard’, researchers have delineated three distinct phases. Determining the computational difficulty of these problems, important for modelling physical systems and optimisation tasks, proved exceptionally challenging. Problems fall into categories of QMA-complete, StoqMA-complete, or are reducible to a newly defined problem called EPR, with this classification hinging on the energy level ordering of the local interaction term.

This reveals a direct link between a system’s physical properties and its computational intractability. The classification suggests the EPR problem may represent a key boundary, potentially solvable in polynomial time and completing the complexity classification of these local Hamiltonians. Dr Tommaso Demarco and Dr Alessandro Silva demonstrated this through a ‘toy model’ utilising Bell states. The transition between these phases correlates with the singlet state’s position in the energy level ordering, mirroring behaviour in larger Hamiltonian families. This detailed mapping builds on prior work suggesting it may be solvable using quantum Monte Carlo methods, potentially bridging the gap between tractable and intractable problems.

Mapping complexity phases in 2-local Hamiltonians informs boundaries of efficient simulation

Classifying computational problems is important for progress in fields like materials science and drug discovery, where simulating complex systems is vital. Current methods rely on carefully constructed “perturbative gadgets”, but lack the speed needed for genuinely practical algorithms. While these gadgets successfully map the complexity field of 2-local Hamiltonian problems, achieving polynomial time efficiency remains elusive. This represents a significant hurdle given the conjecture that the EPR problem represents a key boundary between solvable and intractable scenarios.

Despite doubts about achieving a genuinely practical algorithm based on these complex gadgets, this work establishes a key framework for understanding computational difficulty, informing future algorithm development. A subtle understanding of computational complexity within 2-local Hamiltonian problems has been established, systems frequently used to model physical phenomena. By identifying three distinct complexity phases, QMA-complete, StoqMA-complete, and EPR, scientists move beyond simple classifications of ‘easy’ or ‘hard’ problems. The categorization is fundamentally linked to the energy level ordering of the interactions within these systems, revealing a direct relationship between physical structure and computational intractability. This research proposes the EPR problem as a potential boundary between tractable and intractable scenarios, building on earlier definitions and suggesting it may be solvable with existing methods, opening avenues for exploring polynomial-time solutions and refining the boundaries of computational feasibility.

The study of 2-local Hamiltonian problems is rooted in the broader field of quantum computation and its application to simulating physical systems. Hamiltonians describe the total energy of a system, and in this context, ‘2-local’ signifies that interactions are limited to pairs of quantum mechanical entities, such as spins or qubits. These systems are crucial because they serve as simplified models for more complex physical phenomena, allowing researchers to explore fundamental questions about computational complexity without being overwhelmed by the intricacies of real-world materials. The computational complexity of determining the ground state energy of a Hamiltonian, the lowest energy state, is a central problem in quantum physics and computer science. Problems belonging to complexity classes like QMA-complete and StoqMA-complete are believed to be exceptionally difficult, requiring exponential time to solve on classical computers. This makes understanding their boundaries and potential approximations vital.

The researchers employed a sophisticated methodology involving the construction of “perturbative gadgets”. These gadgets are essentially building blocks used to transform a given Hamiltonian problem into another, equivalent problem, allowing for a systematic analysis of its complexity. A key component of their approach was the analysis of a spin chain using the Jordan-Wigner transformation. This transformation maps the spin operators of the chain onto fermionic operators, a mathematical technique that simplifies certain calculations and facilitates the analysis of the Hamiltonian’s properties. The team meticulously examined how the energy level ordering of the local interaction term influences the overall computational complexity. Specifically, they identified that the relative positioning of the singlet state, a specific quantum state with zero spin, within the energy spectrum is a critical determinant of the problem’s complexity phase.

The significance of identifying these three complexity phases, QMA-complete, StoqMA-complete, and EPR, lies in the potential for developing more efficient algorithms. QMA-complete problems are considered the hardest in the quantum realm, while StoqMA-complete problems, though still challenging, may be amenable to approximation techniques. The newly defined EPR problem, however, holds particular promise. If proven to be solvable in polynomial time, it would represent a significant breakthrough, effectively completing the classification of 2-local Hamiltonian problems and providing a benchmark for assessing the performance of quantum algorithms. The researchers suggest that the EPR problem might be solvable using existing methods like quantum Monte Carlo, a stochastic method that leverages random sampling to approximate solutions to complex problems. This possibility is particularly exciting as it could pave the way for simulating larger and more realistic physical systems.

The implications of this work extend beyond fundamental theoretical understanding. Efficiently simulating materials and molecules is crucial for designing new materials with desired properties and discovering novel drugs. Current computational limitations often restrict the size and complexity of systems that can be accurately modelled. By refining our understanding of computational complexity and identifying potential pathways to efficient simulation, this research contributes to overcoming these limitations. Furthermore, the framework developed by Marwaha and Sud provides a valuable tool for classifying and analysing other computational problems in physics and computer science. The identification of the EPR problem as a potential boundary between tractable and intractable scenarios offers a clear direction for future research, focusing on developing algorithms specifically tailored to exploit its unique properties and unlock the full potential of quantum simulation.

The research successfully classified 2-local Hamiltonian problems into three complexity phases: QMA-complete, StoqMA-complete, and a newly defined problem called EPR*. This classification matters because it helps to understand which of these problems are fundamentally difficult to solve, and which may be tackled with more efficient algorithms. The authors propose that solving the EPR problem in polynomial time would complete this classification and establish a boundary between easy and hard local Hamiltonians. They suggest existing methods, such as quantum Monte Carlo, may be applicable to the EPR problem, potentially enabling the simulation of more complex systems.