← Latest papers
⚛️ quantum physics

Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery

This paper proposes a hybrid quantum-classical workflow that reduces QAOA circuit depth on non-hardware-native graphs by constructing MinLA-based surrogate models with fewer interactions and subsequently recovering near-optimal solutions for the original MAX-CUT problem through classical refinement strategies.

Original author: K. Bharati, Nathan Earnest-Noble, Ritajit Majumdar

Published 2026-11-16
📖 7 min read🧠 Deep dive

Original author: K. Bharati, Nathan Earnest-Noble, Ritajit Majumdar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the race to build useful quantum computers, scientists are currently navigating a difficult middle ground. They possess machines that can perform specific calculations far faster than traditional computers, yet these machines are still fragile and limited in size. One of the most promising ways to use them is to solve complex puzzles known as optimization problems, where the goal is to find the best possible arrangement among millions of options. A leading method for doing this is called the Quantum Approximate Optimization Algorithm. It works by preparing a quantum state that represents many possible answers at once and then refining it to find the best one. However, a major hurdle exists: real quantum chips are not built to handle every type of puzzle directly. The chips have a specific, sparse layout of connections between their tiny processing units, while many interesting problems involve dense webs of connections that do not fit. To force a mismatched problem onto a chip, engineers must insert extra steps to move information between distant units, a process that adds layers of complexity and noise. This noise often destroys the delicate quantum information before the answer can be found, leaving the machine unable to solve the very problems it was meant to tackle.

Researchers at IBM Research and the Indian Institute of Technology Madras have developed a new strategy to bypass this bottleneck, allowing quantum computers to solve larger, more complex graph problems than previously possible. Their approach, tested on a 156-qubit processor, involves a clever two-step workflow that balances what the quantum machine can do with what a classical computer can fix. Instead of trying to force the entire complex problem onto the chip at once, the team first creates a simplified, "surrogate" version of the problem that fits within the chip's physical limits. They achieve this by reordering the problem's components so that the most important connections are short and local, then selecting only those connections that can be executed without overwhelming the machine with error-prone routing steps. This allows the quantum computer to run a much shorter, cleaner circuit and generate a set of candidate solutions.

The true innovation lies in what happens next. The researchers do not simply accept the quantum computer's output as the final answer. Instead, they take the best candidate solutions generated by the simplified quantum circuit and feed them into a classical computer. This classical computer then performs a rigorous, step-by-step refinement process to repair the information that was left out during the simplification. It evaluates the candidates against the original, full, complex problem and systematically improves them until they reach a near-perfect state. By separating the heavy lifting of quantum sampling from the final polishing of the answer, the team successfully solved instances of a classic graph problem called MAX-CUT on graphs with up to 100 vertices. These graphs were far too dense to run directly on the hardware, yet the hybrid method produced solutions that were almost as good as the theoretical best possible answers.

The core of this method relies on a specific way of organizing the problem data before it ever reaches the quantum chip. The researchers used a mathematical technique called Minimum Linear Arrangement to reorder the vertices of the graph. Imagine the problem as a map of cities connected by roads; the goal is to find a way to split the cities into two groups so that the number of roads crossing between the groups is maximized. On a standard quantum chip, the connections between cities are fixed and sparse. If the cities in the problem are far apart on the map, the chip must build long, winding bridges to connect them, which introduces errors. The researchers' ordering technique rearranges the cities so that those with many connections to each other are placed right next to one another in the sequence. This allows them to select a "band" of interactions that are all close together, discarding the long, expensive connections that would require too many error-prone steps to execute.

This selection process is guided by a strict budget for the depth of the circuit, which is essentially a measure of how many steps the quantum computer must take in a row. The researchers determined the widest possible band of connections that could fit within this depth limit for their specific hardware. They ensured that every single city in the problem remained part of the simplified model, even if some of its connections were temporarily ignored. This created a surrogate Hamiltonian, a simplified version of the problem's energy landscape that the quantum computer could actually run. When they ran this simplified circuit on the IBM processor, they found that it reduced the required number of steps by more than half compared to trying to run the full problem, while still retaining a significant portion of the original graph's structure. For the largest graphs tested, which had nearly a thousand connections, the method kept about half of the interactions, a feat that would have been impossible with previous techniques that stripped the graph down to a simple chain.

The quantum computer then sampled thousands of potential solutions from this simplified landscape. Because the circuit was shorter and cleaner, the solutions it produced were of higher quality than those from a noisy, full-depth attempt would have been. However, these solutions were still based on an incomplete picture of the problem. To fix this, the team employed two distinct classical recovery strategies. The first was a greedy approach that looked at each city individually and flipped its group assignment if doing so improved the total number of crossing roads. The second, more sophisticated strategy looked at pairs of groups of cities and solved a specific type of optimization problem to find the best way to rearrange them together. This second method, which uses a technique related to finding the minimum cut in a network, allowed the system to escape local traps where a single change would not help, but a coordinated change would.

The results of this hybrid workflow were striking. On graphs with 100 vertices, the raw output from the quantum computer, even after being simplified, was already quite good. But after the classical recovery step, the quality of the solutions jumped dramatically. The best solutions found after recovery achieved an approximation ratio of nearly 0.997, meaning they were within 0.3 percent of the absolute best possible answer. This was true even though the quantum computer never executed the full, complex set of interactions required by the original problem. The researchers verified that this improvement came entirely from the classical refinement, as the recovery process ran independently on each candidate solution without needing any further time on the quantum processor.

This work demonstrates that the limitations of current quantum hardware do not necessarily prevent it from solving large, complex problems. By acknowledging the hardware's constraints and designing a workflow that respects them, the researchers showed that one can extract useful signals from a simplified quantum execution and amplify them through classical computation. The method is particularly powerful because it is scalable; as quantum processors improve and can tolerate deeper circuits, the "band" of interactions can be widened to include more of the original problem, requiring less work from the classical computer. Conversely, for today's noisy machines, the method provides a practical path forward, proving that a combination of hardware-aware simplification and classical recovery can deliver high-quality solutions for problems that were previously out of reach. The study confirms that the future of quantum optimization may not lie in waiting for perfect, error-free machines, but in building smart, hybrid systems that know how to work with the imperfect tools currently available.

Drowning in papers in your field?

Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.

Try Digest →