Researchers cut two-qubit depth in quantum algorithm using classical optimisation

Researchers at Indian Institute of Technology Madras and IBM Research have achieved a reduction to two-qubit depth in quantum algorithms designed to solve complex optimization problems. Their new hybrid quantum-classical workflow tackles a key limitation of the Quantum Approximate Optimization Algorithm (QAOA) when applied to graphs not naturally suited to quantum hardware. The team evaluated the workflow on IBM’s ibm_kingston quantum computer, using 120 distinct instances of 6-regular and Erdős-Rényi graphs with 40, 60, and 100 vertices, and verified that the resulting circuits substantially reduce required two-qubit depth while yielding near-optimal solutions.

Max-Cut QAOA Depth Reduction via Interaction Selection

MinLA-based vertex ordering constructs a surrogate Quantum Approximate Optimization Algorithm (QAOA) ansatz that substantially reduces two-qubit depth, addressing a key limitation when solving non-hardware-native Max-Cut instances. This approach preferentially retains short-range interactions, enabling a reduction in circuit complexity before quantum execution. The team’s workflow does not simply reduce the problem. It actively compensates for information lost during interaction removal through classical refinement of solutions. To recover solution quality, the researchers developed two classical strategies, signed-residue-based local search and bipartite-block optimization, that refine quantum processing unit (QPU)-sampled bitstrings directly on the original Max-Cut objective.

Each conditional block problem within the bipartite-block optimization is solved exactly using a s-t minimum cut, ensuring a precise refinement of potential solutions. Recovery is performed independently for each sampled configuration, guaranteeing monotonic improvement in cut value without requiring additional, costly QPU executions. This allows for a more efficient use of quantum resources.

Experimental evaluation on IBM’s ibm_kingston quantum computer demonstrated the effectiveness of this hybrid approach. The results show that surrogate Hamiltonians reduce transpiled two-qubit depth while remaining within prescribed hardware limitations. “These results demonstrate the potential of hardware-aware interaction selection and classical recovery to extend QAOA to graph instances whose full cost Hamiltonians exceed practical circuit-depth budgets,” the paper states.

The work addresses a fundamental challenge in quantum optimization: the mismatch between the dense structure of many problems and the sparse connectivity of current quantum processors. By strategically reducing interactions and then recovering lost information through classical means, the researchers offer a pathway to tackling larger, more complex Max-Cut instances.

The combination of MinLA reordering and band-limited interaction selection preserves more interactions than aggressive reduction strategies, allowing for a more accurate representation of the original problem within the constraints of the quantum hardware. This approach could be extended to other combinatorial optimization problems with similar graph-based formulations, potentially broadening the applicability of QAOA.

MinLA Vertex Ordering for Short-Range Interactions

Employing the Minimum Linear Arrangement (MinLA) heuristic, the team obtained low-cost orderings that place frequently interacting qubits in close proximity within the computational graph. Visualizations reveal that MinLA consistently positions a greater number of edge entries closer to the main diagonal, particularly at shorter interaction spans. This arrangement allows for a higher fraction of the original interactions to be preserved when limiting the interaction radius, a key step in reducing two-qubit depth. The resulting hardware-feasible surrogate Hamiltonian is given by HCp,L = 1/2sum_((u,v) ∈ E_(k^*(p,L)))(I-Z_uZ_v), where Ek^*(p,L) represents the edges retained within the specified radius.

The fraction of interactions retained, η(p,L) = |Ek^*(p,L)|/|E|, is determined by the graph structure, QAOA depth and the hardware’s depth budget, rather than a fixed sparsification ratio. This approach allows the team to construct circuits with reduced two-qubit depth while maintaining a substantial portion of the original problem’s connectivity. The retained edges are not selected arbitrarily; the MinLA ordering ensures that the most important, short-range interactions are prioritized, maximizing the potential for accurate solutions even after the reduction in circuit size.

Surrogate Hamiltonian Construction for Depth Control

This constraint is met while simultaneously retaining a substantial portion of the original graph structure, a key factor in maintaining solution quality. This selective retention isn’t arbitrary; the method prioritizes preserving interactions that are both numerous and short-range, maximizing the impact of the remaining connections. These retention rates were achieved using fixed QAOA parameters, as detailed in their implementation. “We further developed signed-residue and bipartite-block recovery procedures that operate on the original graph and monotonically improve sampled solutions without requiring additional QPU executions,” the researchers write.

The workflow ensures that every decision variable is retained and every executed interaction originates from the original Hamiltonian, a critical aspect of maintaining the integrity of the optimization process. By combining hardware-aware interaction filtering with this classical recovery, the team constructed surrogate Hamiltonians that satisfy the prescribed depth budget while still yielding near-optimal cuts on the original graphs. This hybrid approach represents a step towards extending the applicability of QAOA to larger, more complex problems on near-term quantum hardware.

Classical Recovery of MAX-CUT Solutions

The workflow detailed in this work improves sampled configurations through classical refinement against the original MAX-CUT objective, a strategy that allows for high-quality solutions even when not all interactions are initially executed on the quantum processor. This approach addresses a core challenge in quantum optimization: balancing circuit depth with solution quality for problems defined on graphs that do not naturally align with the hardware’s connectivity.

By refining configurations post-quantumly, the team sidesteps the need for deeper circuits to explore the full solution space directly. Two distinct classical recovery procedures were developed to explore neighborhoods of a configuration and improve the cut value, accepting updates only when they demonstrably increase the objective function for the original graph. One strategy, signed-residue-based local search, uses the structure of edge contributions to refine sampled configurations, while the other, bipartite-block optimization, solves conditional block problems exactly using a s-t minimum cut.

The bipartite-block recovery consistently achieved higher mean approximation ratios than the signed-residue approach, particularly for larger graphs. The team verified these results using 120 instances on the ibm_kingston quantum computer, demonstrating the method’s scalability and robustness.

Signed-Residue and Bipartite-Block Recovery Strategies

Each strategy addresses information lost during a reduction in quantum circuit complexity by using the structure of the graph itself, with bipartite-block optimization solving conditional minimum-cut subproblems to explore solution neighborhoods. These findings demonstrate a pathway for using future improvements in quantum hardware, as processors with lower error rates and increased qubit connectivity become available, expanding the range of optimization problems addressable with quantum computing.

IBM_Kingston Evaluation on Non-Hardware-Native Graphs

Researchers found that, while a 910-edge interaction problem initially demanded a depth of 62, implementation on the processor increased that to 255 due to the need for SWAP operations to route interactions. This increase in circuit complexity can introduce noise, prompting the development of hardware-aware reductions that preserve problem structure while remaining executable on current superconducting processors. The team’s approach differs from earlier experimental studies on Max-Cut, which focused on graphs with up to 40 vertices, demonstrating a scalability to larger, more complex problems.

The resulting circuits retained more of the original graph structure than those created using chain-based reductions. Classical refinement is important in this hybrid approach, with two strategies developed to improve solution quality. “Recovery is performed independently on each sampled configuration,” the paper states, emphasizing the efficiency of this parallel processing on classical processors.

The best recovered cut is then returned, maximizing the benefit of the initial quantum sampling. The evaluation focused on three key aspects: circuit-depth reduction, solution quality from surrogate sampling and the effectiveness of classical recovery. Results demonstrate that the workflow not only minimizes circuit complexity but also yields near-optimal cuts on the original graphs after classical refinement.

Extending QAOA Beyond Circuit-Depth Budgets

This reduction is accomplished by selectively removing interactions between qubits and then using classical computation to restore solution quality, a strategy that circumvents limitations imposed by the physical connectivity of current quantum hardware. The approach prioritizes retaining short-range interactions during this filtering process, guided by a Minimum Linear Arrangement (MinLA)-based vertex ordering, to construct a simplified quantum circuit.

These instances, sourced from the HAMLIB library, were specifically chosen to be non-hardware-native, meaning their ideal qubit connectivity does not match the physical layout of ibm_kingston. The researchers verify that the surrogates substantially reduce transpiled two-qubit depth while staying within the prescribed two-qubit depth, and with recovery yield near-optimal cuts on the original graphs.

👉 More information
🗞 Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery
✍️ K. Bharati (Indian Institute of Technology Madras); Nathan Earnest-Noble and Ritajit Majumdar (IBM Research)
🧠 ArXiv: https://arxiv.org/abs/2611.18002v1

Stay current

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

Avatar of Rusty Flint

Rusty Flint

Rusty is a quantum science nerd. He's been into academic science all his life, but spent his formative years doing less academic things. Now he turns his attention to write about his passion, the quantum realm. He loves all things Quantum Physics especially. Rusty likes the more esoteric side of Quantum Computing and the Quantum world. Everything from Quantum Entanglement to Quantum Physics. Rusty thinks that we are in the 1950s quantum equivalent of the classical computing world. While other quantum journalists focus on IBM's latest chip or which startup just raised $50 million, Rusty's over here writing 3,000-word deep dives on whether quantum entanglement might explain why you sometimes think about someone right before they text you. (Spoiler: it doesn't, but the exploration is fascinating)

Latest Posts by Rusty Flint: