Exponential Speedup Achieved for Maximum Independent Set on Hard Instances

Scientists are tackling the notoriously difficult problem of finding the maximum independent set within complex networks, a challenge central to optimisation across numerous fields. Vicky Choi from Gladiolus Veritatis Consulting Co, alongside co-authors, demonstrate a novel adiabatic quantum algorithm capable of exponentially outperforming both classical and existing quantum solvers on specifically structured, yet classically hard, instances of this problem. Their research identifies a key mechanism , utilising a non-stoquastic approach to unlock a wider solution space , and importantly, suggests why a comparable classical algorithm is unlikely to emerge. This breakthrough not only offers a potential pathway to faster solutions for critical optimisation tasks, but also provides scalable models for verifying this quantum advantage on near-term quantum computers.

Their research identifies a key mechanism, utilising a non-stoquastic approach to unlock a wider solution space, and importantly, suggests why a comparable classical algorithm is unlikely to emerge. This breakthrough not only offers a potential pathway to faster solutions for critical optimisation tasks, but also provides scalable models for verifying this Quantum advantage on near-term quantum computers.

Dic-Dac-Doa algorithm solves hard MIS problems efficiently

Scientists have demonstrated a significant breakthrough in quantum computation by achieving exponential speedup for solving classically hard problems. This work directly addresses two critical stages in quantum advantage research: identifying concrete problem instances that are expected to exhibit quantum speedup and connecting these instances to real-world applications. The researchers focused on GIC graphs, a family of maximum independent set (MIS) instances exhibiting intrinsic computational hardness, and developed the Dic-Dac-Doa approach, initially proposed in 2021, to specifically address these challenges. This method departs from traditional adiabatic quantum computing analyses, which typically rely on spectral-gap considerations.

Instead, the team evaluates algorithmic efficiency by identifying anti-crossings in the energy landscape and inferring their behaviour directly from the crossing properties of bare energy levels, without constructing a full two-level Hamiltonian. Dic-Dac-Doa enhances standard transverse-field quantum annealing by incorporating a specially designed non-stoquastic XX-driver term, which is intended to overcome the small-gap anti-crossings that hinder performance on GIC graphs. Numerical results obtained using state-of-the-art classical solvers confirm the classical hardness of these structured instances, indicating that solving the MIS problem on them would require exponential time unless P equals NP. Furthermore, the study establishes that the ability to exploit a larger sign-structured subspace, made possible by moving beyond stoquasticity, is fundamental to the observed quantum speedup.

This mechanism differs fundamentally from the conventional understanding of quantum speedup based on quantum tunnelling. Instead, it highlights the importance of wavefunction amplitudes that can take both positive and negative values, unlike classical probabilities. The team constructed GIC graphs that encode a planted maximum independent set alongside competing maximal independent sets, organised into clique-based blocks. Each dMIC block, which serves as a fundamental building block of a GIC graph, consists of k independent cliques with sizes denoted by nᵢ, where 1 ≤ i ≤ k. The degeneracy within a dMIC is given by the product of the clique sizes, expressed as ∏ᵢ₌₁ᵏ nᵢ.

A GIC instance comprises at least three such dMIC blocks, which are initially connected via complete bipartite graphs and then selectively modified to embed a unique planted global MIS spanning multiple blocks. Measurements confirm that GIC instances can be constructed in polynomial time despite their classical hardness, as solving the MIS problem on these instances would require exponential time unless P = NP. The study shows that each dMIC induces a set of degenerate local minima in the MIS-Ising energy landscape, forming wide energy basins; these local minima and dMICs are used interchangeably when context allows. The researchers encoded the MIS problem into the ground state of an MIS-Ising Hamiltonian, enabling a direct correspondence between maximal independent sets and local minima of equal energy, specifically −m, where m denotes the size of the independent set.

The results demonstrate that introducing a non-stoquastic XX driver expands the admissible Hilbert subspace by accessing opposite-sign sectors, thereby enabling sign-generating quantum interference. This interference produces negative amplitudes that allow the system to evolve smoothly along paths that bypass the limitations of quantum tunnelling. This represents a fundamentally different mechanism for quantum speedup in Hamiltonian-based optimisation. Finally, the authors propose scalable, reduced models derived from the algorithm’s structure, offering a concrete opportunity to experimentally verify this speedup mechanism on currently available universal quantum computers.

Polynomial Speedup via Non-Stochastic Optimisation is now demonstrated

Furthermore, the authors developed scalable, small-scale models derived from structural reduction, offering a means to verify the advantage mechanism using existing universal computers. Future work could focus on exploring the applicability of this non-stoquastic approach to other computationally challenging combinatorial optimization problems, and investigating the potential for extending the structural reduction techniques to create more comprehensive models. This work establishes a distinctive mechanism for achieving quantum speedup and offers a pathway for experimental verification on near-term quantum hardware.