Researchers at Université de Sherbrooke have demonstrated a new hybrid quantum-classical framework, Lp-Quts, capable of tackling optimization problems with up to 300 vertices, a scale exceeding the current capacity of neutral atom quantum computer hardware. The approach integrates a neutral atom quantum computer sampler with a classical cutting-plane algorithm, achieving solutions within 5-10% of optimality and outperforming both direct analog quantum protocols and standard “greedy” algorithms with equivalent sampling resources.
This work demonstrates how quantum samplers can deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees. Cédrick Perron, Yves Bérubé-Lauzière, and Victor Drouin-Touchette detail how, for t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from classical cutting-plane theory.
Lp-Quts Framework Integrates Quantum Sampling with Classical Cutting-Planes
This achievement stems from integrating an NAQC sampler with a classical cutting-plane algorithm, allowing for problem instances beyond the reach of standalone quantum systems. At each iteration, a relaxed linear program (RLP) establishes bounds for the MWIS and generates a reduced graph, subsequently sampled by the analog quantum sampler. A newly developed sample-informed separation problem then directs the selection of odd-cycle cuts, accelerating the overall convergence rate. Simulated annealing currently remains the strongest sample-based solver at this scale, but Lp-Quts presents a compelling alternative by combining the strengths of both quantum and classical approaches.
Neutral Atom Quantum Computers Encode MWIS via Rydberg Blockade
Neutral atom quantum computers use alkaline atoms, typically Rubidium, trapped and cooled to their ground state for quantum computations. These systems encode the maximum weighted independent set (MWIS) problem by using the Rydberg blockade, a natural enforcement of independence constraints with minimal overhead. This allows for the ratio of node weights in the MWIS to be represented by the final-time detuning ratios of the atoms.
The architecture’s suitability for MWIS problems stems from its ability to directly map problem constraints onto physical interactions. Specifically, the Hamiltonian governing the system at a final time T encodes the MWIS of a reduced graph, establishing a direct link between the quantum state and the optimization solution. This contrasts with other quantum hardware platforms where such direct encoding may require more complex implementations.
The Rydberg blockade phenomenon, arising when interaction strength surpasses drive amplitude, dictates how graph structures are embedded within neutral atom quantum computers. The driving laser’s detuning can be tuned to implement weights on these vertices.
Gadget-Based Reductions Introduce Quadratic Overhead in Atom Count
Embedding arbitrary graphs onto neutral atom quantum computers (NAQCs) often requires the use of gadgets, chains of ancilla atoms that translate a problem’s connectivity into a form the hardware can handle. While these gadgets maintain a direct correspondence between optimal solutions of the original and reduced graphs, Cédrick Perron of Université de Sherbrooke and colleagues found that this process introduces a significant cost. Specifically, the number of additional atoms needed scales quadratically with the number of vertices in the original graph, creating an O(|V|^2) overhead where |V| represents the number of vertices.
This means that as the size of the problem increases, the number of atoms required for the embedding grows disproportionately fast. The team’s analysis reveals that finding the minimum number of ancilla atoms needed is itself a computationally hard problem, equivalent to solving a set cover problem, which is known to be NP-Complete.
Although approximations exist, these embeddings do not preserve the quality of near-optimal solutions. Solutions found in the reduced graph, even with small optimality gaps, do not necessarily translate to equally good solutions when mapped back to the original problem. This degradation in solution quality further complicates the use of gadgets, limiting their effectiveness in practical applications. This quadratic overhead presents a fundamental challenge for scaling NAQC-based MWIS solvers.
The researchers note that while gadgets enable the encoding of more complex problems, they do so at the expense of increased resource requirements and potential loss of solution accuracy. The findings suggest that alternative approaches to graph embedding, or hardware capable of natively supporting more complex connectivity, will be important for realizing the full potential of NAQCs for solving large-scale optimization problems.
UD Graph Approximations Impact Solution Quality and Scalability
This edge reduction is important because it allows the quantum sampler to focus on a smaller, more manageable problem space, despite exceeding the current capabilities of existing neutral atom quantum computer hardware. A key innovation within Lp-Quts lies in its sample-informed separation problem, which guides the selection of odd-cycles for inclusion in the classical cutting-plane algorithm. This process uses the principle of complementary slackness, identifying edges critical to the structure of the current relaxed linear program solution.
Retaining only these “tight” edges, those with positive dual variables, creates a reduced graph, , that preserves the essential constraints while minimizing computational load. This approach is particularly effective for t-perfect graphs, a specific class where the resulting constraints precisely define the convex hull of integer solutions, guaranteeing polynomial-time convergence to the optimal solution.
Limitations of Quantum Annealing and Existing MWIS Performance Bounds
While analog quantum approaches are often constrained by realizable graph geometries, this framework uses a classical cutting-plane algorithm to induce a reduced graph, enabling the exploration of larger, more complex problems. Despite improvements from single bitflip greedy post-processing, its effectiveness decreases as problem size grows without additional heuristic rules, a limitation that Lp-Quts addresses through its sample-informed separation problem.
Most quantum heuristics for the maximum weighted independent set (MWIS) lack provable performance bounds on general graphs, creating a challenge for practical industrial applications, but Lp-Quts directly confronts this issue by integrating a quantum independent-set sampler into a classical framework.
This outcome highlights the potential of combining classical optimization techniques with quantum samplers, offering a pathway to near-optimal solutions with reduced quantum resource requirements. The team hopes this result will further encourage the community to embrace and explore the marriage of OR tools with quantum techniques, establishing a foundation for future advancements in the field.
The researchers report.
Detuning Controls Vertex Weights in Analog NAQC Implementation
By modulating the detuning, , for each atom, researchers effectively assign a weight to each vertex within the graph, directly influencing the optimization process. This technique uses the Rydberg blockade phenomenon, where interactions between atoms, represented by edges in the graph, are governed by the blockade radius, and the strength of the driving laser. Simultaneous excitation of nearby atoms is prohibited when the interaction strength exceeds the drive amplitude, > Ω, establishing the physical constraints of the problem.
A novel separation problem, designed to balance classical and quantum contributions, further refines the algorithm’s performance. The equation [ = + ] quantifies this balance, where measures the average occupation of vertices in a candidate odd-cycle, , over the sampled independent sets. The weighting parameter, α ≥ 0, allows for precise control over the influence of the quantum sampler on the cut selection process.
👉 More information
🗞 Iterative optimization with partial convergence guarantees on neutral atom quantum computers
✍️ Cédrick Perron, Yves Bérubé-Lauzière and Victor Drouin-Touchette
🧠 DOI: http://link.aps.org/doi/10.1103/txz1-dfxf




See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
