Quantum optimisation at QCE26 leaned on its classical half

This guide follows 42 talks on quantum optimisation at IEEE Quantum Week 2026 in Toronto. They brought new ways to tune QAOA, circuits that obey hard rules and a proof that exact QAOA scores become intractable at two layers.

On the afternoon of Wednesday 16 September, as a workshop on quantum optimisation wound up, Stuart Hadfield of the NASA Quantum AI Laboratory told the room a story about a number. Max-cut asks how to split a network into two groups so that as many links as possible run between them. For decades, Hadfield recalled, the best methods with a guarantee were stuck near one half of the best answer. Then Michel Goemans and David Williamson found a method guaranteed to come within about 0.878 of the best. Hadfield wanted a leap like that. QAOA, the best-known quantum method for such problems, has yet to make one.

The field is combinatorial optimisation, the business of picking the best choice from a vast but finite set, such as the shortest delivery round or the cheapest factory schedule. The options grow exponentially with the problem. For many such problems no known method, classical or quantum, is sure to find the best answer quickly every time. Most quantum methods first rewrite the problem as a QUBO, short for quadratic unconstrained binary optimisation. Each choice becomes a yes or no. The cost then acts like the energy of a physical system.

A quantum annealer, such as the ones D-Wave builds, changes its qubits slowly so they settle toward the lowest energy. Gate-based machines run QAOA instead. It takes turns between a layer that scores each answer and a layer that mixes them, while an ordinary computer tunes its angles.

Read together, the 42 talks followed here, from the conference also known as QCE26, make a case the field may not enjoy hearing. The ordinary computer won nearly every gain. It came from how the angles were chosen, how the rules were written in or how the answers were sifted afterwards. On gate-model machines the quantum half ran mostly in simulation, and the leap Hadfield asked for did not appear.

The strongest case against that reading came from the people building the circuits. Timo Ziegler of Leibniz Universität Hannover said their group had beaten the Goemans-Williamson bound on 22-node max-cut a year earlier. Jonas Stein of LMU Munich showed a knapsack method whose time to solution grew far more slowly than the usual penalties allow. That held in simulation, at least.

Ruslan Shaydulin of JPMorganChase showed QAOA passing the best proven classical guarantee for cutting graphs into many colours, though a greedy heuristic of the team’s own still beat it. Phillip Lotshaw of Oak Ridge National Laboratory won a best-paper award in the QSYS track for a loop whose median normalised score on 30-vertex graphs was about 0.95, where 1 is the best cut and 0 the worst. Those results are real, and a fair reader could call them the groundwork any future advantage will need.

Look at where Lotshaw’s gain came from. Their method keeps the best answer so far and builds a simple unentangled state around it, so each update can be worked out on paper. The same loop without the quantum circuit still scored about 0.875 on that scale. The talks on tuning QAOA had the same shape, with classical networks, closed-form formulas and spectral shortcuts setting the angles. Each is clever classical computing in service of a quantum circuit. At Siemens, Hila Safi found that only Fujitsu’s Digital Annealer, a classical machine inspired by annealing, solved a factory schedule at every size.

Yet the deeper difficulty is what kind of progress the field rewards. Max-cut’s own history shows that the leap to 0.878 came from one new idea, relaxing each yes-or-no choice into a direction in space, and from no amount of tuning. The talks in this theme mostly tune. A paper that trims an exponent in simulation can be written this year, while the leap Hadfield asked for has no timetable, and the incentives of a conference favour the first.

Tuning QAOA without the long search

QAOA has a handful of angles per layer, and finding good ones is a slow classical search that can go flat as circuits grow. Seven talks tried to skip most of that search. Five did it with classical tools, and two let the quantum circuit steer itself, through feedback or measurements made partway through.

A learned model sets angles across four problems

Kien Nguyen of the University of Delaware asked whether one trained model could set QAOA angles across several graph problems at once. Nguyen wrote the paper with their advisor Ilya Safro. Earlier methods work within one kind of problem. Their model, a recurrent network fed with a summary of the graph and its rules, proposes angles step by step.

The four problems were max-cut, maximum independent set, maximum clique and minimum vertex cover. The team trained on 1,000 random graphs of 6 to 10 nodes and tested on 100 graphs of 12, where a plain search from random angles often needs more than 200 steps. At depth 8 the network took just 10 steps. Those steps beat the long search for independent set and clique. A questioner noted that the model had missed the close link between vertex cover and independent set.

Coordinate descent for multi-angle QAOA

Daeyeun Kim led this work with Seungcheol Oh, Yun Pyo Hong and Joongheon Kim, and a doctoral student from Korea University presented it. Multi-angle QAOA gives every edge and vertex its own angle. Plain QAOA shares one set across each layer. At a fixed depth that can do no worse, but it brings many more angles for an ordinary computer to set, 260 at depth 5 on a 12-vertex graph.

With all other angles fixed, the score along any one angle is a sine wave. Three evaluations pin it down. So the method moves each angle in turn straight to the peak of its own wave, and a full sweep over 260 angles costs about the same as one step of ordinary gradient descent. Several runs reached about 0.94 of the best cut on noiseless max-cut. They then flattened below the best value gradient descent reached.

A spectral gap sets the schedule

Kieran McDowall presented work with Konstantinos Georgopoulos and Petros Wallden, of the National Quantum Computing Centre, the Quantum Software Lab and the University of Edinburgh. A linear ramp is a cheap common way to set QAOA angles. McDowall said that on plain search it gives up Grover’s speed-up. McDowall wanted the schedule to slow down where the gap between the lowest two energy levels is narrowest, since that is where a slow quantum process most often goes wrong.

The full gap is as hard to find as the answer, so McDowall computes it for small cases, averages it and reuses the shape on larger ones. A shape taken from 6 to 12 vertices and used out to 22 stayed close to the exact curve. At depth 10 the new ramp beat the linear one at middle sizes. The gain vanished when depth was ample or far too small.

Angles that carry across hypergraphs

Phillip Lotshaw of Oak Ridge closed a Thursday algorithms session. Lotshaw did the work with Lucas Braydwood of the NASA Ames Quantum Artificial Intelligence Laboratory. Good QAOA angles for max-cut are known to carry from one graph to another once scaled by weight and degree, and Lotshaw asked whether the same holds for hypergraphs, where one cost term can join three or more vertices.

Lotshaw derived a one-layer rule that rescales one of the two angles and divides the other by the square root of the degree. On 3,060 hypergraphs of 14 vertices, the rescaled angle matched the best angles at one layer and kept improving out to ten layers, while moving the other angle alone rose once and then levelled off. Asked why the runs stopped at 14 vertices, Lotshaw said the best angle shrinks toward zero as graphs grow.

A classical surrogate cuts multi-angle training by 94.5 percent

Youngseok Lee and Hyunwoo Kim of NORMA in Seoul moved most of the training of multi-angle QAOA onto an ordinary computer. That version gives every cost term and every mixer its own angle. It adds up fast. A 20-qubit circuit can carry 840 angles, and each gradient step on hardware needs two runs per angle, so the team first trains every angle for 500 steps on a cheap classical stand-in. That stand-in, Pauli propagation, drops terms that touch more than three or four qubits.

The method, called SAFE, then prunes the angles that stayed near zero and gives the rest 100 exact steps. Kim showed results at 12 to 20 qubits. Pruning cut 64.3 percent of angles on average with no loss in the best score, except for max-cut at depth 2, and on a 20-qubit spin-glass test the estimated quantum workload fell from 32,424 to 1,780. All of it ran in noiseless emulation. Kim said no theory yet says when the shortcut keeps the shape of the score surface.

Small graphs teach FALQON better steps than large ones

Gabriel Fernandes Thomaz of the Eldorado Institute worked with colleagues from Eldorado and two Brazilian universities. FALQON builds each layer from a feedback rule on the state so far. That drops the tuning loop. The second-order version adds curvature, a measure of how the cost bends, which lets each time step be larger so the circuit needs fewer layers.

The team tested max-cut on random graphs where every vertex has three links, from 6 to 24 nodes, with 16 layers in simulation. Steps trained at six nodes and moved to 24 gave an approximation ratio of 0.900. Steps trained at 18 nodes gave only 0.841. The team reads this as larger steps carrying the state further within the 16 layers, and Thomaz said the mathematics still needs work, with other graph families and hardware runs to come.

Mid-circuit measurements replace the tuning loop

Antoine Lemelin of the École de technologie supérieure worked with Olivier Landon-Cardinal, Christophe Pere and Camille Coti. Lemelin found the QAOA loop wasteful. Each time the circuit is read out, the quantum state is lost, so every pass of the loop starts again from nothing while an ordinary computer waits for the scores. The new circuit looks like phase estimation, with a helper qubit read after each step of the problem’s cost.

The settings are fixed in advance. A 0 on the helper boosts low-cost answers and damps high-cost ones, while a 1 sets off a QAOA-style mixer, so the run goes on either way and no outer loop is needed. On IBM’s Quebec machine, seven rounds on a three-node vertex-cover problem gave the right answer about 3,100 times, far ahead of every other result. Cases of up to 8 to 10 qubits worked. Noisy simulations showed that errors on the helper qubit matter most, and Lemelin sees it as an early fault-tolerant method more than a near-term one.

Using quantum circuits to start classical methods

The usual warm start feeds a good classical answer into a quantum circuit. Six talks ran it the other way, or blended the two, and the classical side kept a strong hand.

Depth-one QAOA warms up a classical max-cut solver

Bao Bach of the University of Delaware ran the usual warm start in reverse. Bach used a one-layer QAOA circuit to start a classical max-cut method that places each vertex on a circle, in work with Filip Maciejewski of RIACS and USRA and with Ilya Safro. One-layer QAOA has a closed formula for the chance each edge is cut. So Bach needs no sampling at all.

Tests ran 500 instances at each size. The QAOA start led at first, but on 500-vertex graphs a classical baseline with several random restarts caught up by about 180 iterations. On 1,000-vertex graphs it took longer. One variant still won about 60 percent of the larger comparisons while the budget was short, a margin that shrank as the budget grew.

A best-paper loop that the classical version nearly matches

Phillip Lotshaw of Oak Ridge National Laboratory presented a paper that won a best-paper award in the QSYS track. Lotshaw wrote it with Titus Morris, Stuart Hadfield and Ryan Bennink. Their group’s earlier max-cut circuit found best solutions on IonQ machines from 12 to 32 qubits, but it needed a large table of numbers to be estimated on the hardware at every single step.

The new method keeps the best answer so far and builds a simple unentangled state around it, with one angle that shrinks so later steps search closer. Because that state has no entanglement, the update can be worked out on paper, and the quantum computer only runs the circuit and returns samples. On 100 random graphs with three links per vertex, the median normalised score, with 1 the best cut and 0 the worst, was 1 at 10 vertices and about 0.95 at 30. Without the quantum circuit, the loop reached about 0.875. Lotshaw said how the shot count must grow for graphs of hundreds of vertices is still open.

Hypergraph partitioning as a distribution

Cameron Ibrahim, a PhD student at the University of Delaware, presented work with colleagues from Delaware, Los Alamos and the US Naval Academy. Their example was splitting workers between two shifts so that shared tools are used evenly across a year. That leads to hypergraphs. It also leads to a target that is a whole spread of odds over many cuts.

Ibrahim argued this suits quantum hardware. A trained circuit already defines such a spread, which is usually sampled briefly and then thrown away. In simulation on random hypergraphs, a QAOA-style circuit beat the standard classical method on one measure of spread for all but one instance, and on a slice of a public email network it needed two layers to pass it.

QAOA correlations make a classical solver ten times faster

Maxime Dupont of Rigetti Computing handed classical solvers a problem reshaped by QAOA. The idea is called quantum preconditioning. QAOA works out how strongly each pair of variables tends to agree, and that table of links, its correlation matrix, then goes to the solver in place of the first problem. At one layer the two give the same results for one common kind of solver, and at unlimited depth the table holds the answer outright.

On random max-cut, a table built at one or two layers made reaching 99.9 percent accuracy about ten times faster at around 4,000 variables. With the Burer-Monteiro solver, Dupont said, the time fell from a day to an hour to three minutes. Dupont called the gain quantum-inspired. The tables came from many small classical simulations, so no quantum machine did the work.

Noise-directed remapping reaches qudits and hard rules

Stuart Hadfield of the NASA Quantum AI Laboratory and USRA wrote this paper with Filip Maciejewski and Davide Venturelli. Real noise drifts toward one state, often all zeros. Yet most optimisers do not care which state stands for true, so noise-directed adaptive remapping, or NDAR, relabels the problem after each round to put the best answer so far on the state the noise likes.

Earlier work on Rigetti’s 82-qubit Ankaa-2 lifted one-layer QAOA from about random guessing to an approximation ratio near 0.9 in about a dozen rounds. The new paper extends the method to qudits, systems with more than two levels, and to problems with hard rules. For four-colouring a graph, Hadfield compared four encodings that trade qubit count against how many qubits each check touches. No qudit experiment has run yet.

Hardware noise gives a warm start a slight edge

Davide Venturelli of USRA turned qubit decay into a search move. Superconducting qubits tend to fall back to zero, a process called amplitude damping, so the team relabels the problem to put the best answer so far where the noise pushes. The newest version folds this into warm-started QAOA.

The team ran it on 100-qubit parts of ibm_boston, an IBM Heron chip, at one layer with 10,000 shots per circuit. It did a little better than the usual warm start. It fell short of tensor-network simulation, and Venturelli said such runs remain about three orders of magnitude behind a phone running a classical solver, and asked the field to publish plots of time against quality.

Building the rules into the circuit

Real problems come with rules. A knapsack must stay under its weight limit. A salesperson must visit every city exactly once. The usual trick adds a penalty for every forbidden answer, and a badly set penalty floods the output with useless ones. Nine talks built the rules into the circuit instead, and the knapsack problem was the favourite test.

Indicator-function QAOA for knapsacks

Jonas Stein of LMU Munich presented a Physical Review A paper with David Bucher as first author. Penalties stretch the range of scores a circuit must handle, and Stein’s method avoids them. It gives every forbidden answer the worst allowed score, and it works that out inside the circuit with phase estimation, a routine that reads the rule’s sign onto helper qubits.

On knapsacks of 6 to 22 items, in simulation, the fitted time to solution grew as 1.30 to the power N for the new method, against 1.62 for penalties worked out in advance and 1.97 for the common slack penalties. Stein said phase estimation still rules out runs on today’s hardware.

A conic framework for hard rules

Timo Ziegler of Leibniz Universität Hannover presented work with Lennart Binkowski, Tobias Osborne, Marvin Schwiering and René Schwonnek. Deep circuits flatten the training signal, Ziegler said. Shallow ones fall into poor dips, and penalty terms need fresh tuning for each problem, so the framework drops QAOA and needs just two classical checks, one for cost and one for whether an answer is allowed.

It builds a chain of steps from sums of quantum operations, and a classical convex method picks the weights. The knapsack study used exact matrices and no device. Seeded with a greedy answer on ten instances, the score never fell below the seed, and four starts under an approximation ratio of 0.9 rose to 0.98. Ziegler called the starting success chance very weak and said the chain cannot reach quantum advantage.

Every allowed tour, and nothing else

Marvin Schwiering of Leibniz Universität Hannover wanted a fixed circuit that can reach every allowed answer and no forbidden one. The work began as a master’s thesis. It was done with Timo Ziegler, Lennart Binkowski and Benjamin Sambale. They aimed at a gap in Hadfield’s well-known mixer, which keeps the rules but only promises to reach every allowed answer when the circuit can grow as long as it likes.

For the travelling salesperson the allowed answers are orderings of the cities, and Schwiering showed that the list of steps needed to reach all of them must grow at least as n times log n. A binary insertion scheme achieves it. On a nine-city tour in noiseless simulation their circuits beat Hadfield’s mixer at matched depth, though they used 17 and 28 angles against 7. Schwiering was candid that classical solvers already prove the best tours for thousands of cities.

A biased search for knapsacks with negative weights

Sören Wilkening presented work with co-authors Timo Ziegler and Maximilian Hess. Their group’s earlier circuit walks through knapsack items one at a time and adds each only if it still fits, so the state holds only allowed packings before a search for the best. A negative weight breaks this, since a branch cut as too heavy could become allowed again later.

Their fix shifts both sides of the rule by the negative weights. Those lost branches come back. Wilkening also tilted each step toward a classical guess, so packings near the guess carry more weight. Against Gurobi and simulated annealing, some instances reached a good answer sooner, but that test assumed a very fast error-corrected gate and left out the cost of error correction itself.

A cheaper oracle for subset sum

Abhoy Kole presented a paper from the University of Bremen and DFKI, with first author Fynn Meyer and co-authors including Rolf Drechsler. Subset sum asks whether some chosen numbers add up to a target. Grover search can speed up that check, but every round calls an oracle, the circuit that spots a right answer, so the team set out to make the oracle cheaper.

One qubit per element records whether that element is in the subset, while the running total is built with an adder that writes numbers into the phases of the qubits. Kole claimed 90 percent fewer qubits than another encoding. Small simulations found the right subset on more than 90 percent of trials. Its phase gates are non-Clifford, the costly kind for an error-corrected machine. Kole said Grover will not run on today’s noisy devices.

Infineon’s nested search for knapsacks

Laurin Demmler, an external PhD candidate at Infineon, presented work with Maximilian Hess. Infineon’s supply chain between fabs in Germany and Singapore throws up knapsack-type problems that are often solved greedily, Demmler said, by grabbing the best-looking items first. The base method is Grover adaptive search. It is a chain of searches, each hunting for an answer better than the best so far.

The new step runs the packing circuit on the first few items. It boosts the partial packings that could still win. To test beyond simulation sizes, the team used the classical solver Gurobi to find good answers in advance. On loose instances the nested search reached better answers sooner at equal gate budget, while weakly linked ones showed no gain at all. Every run was a noiseless simulation.

A counterdiabatic term keeps a portfolio budget and lifts the score

Jose Falla of the University of Delaware, with Ilya Safro, built a budget rule into QAOA for a small portfolio. The task picks 4 assets out of 12. So only 495 of the 4,096 possible bit strings are allowed, and a generic mixer can spread most of its weight outside that budget, Falla said. The team kept the budget in the mixer and added a counterdiabatic term, a fix that stops unwanted jumps when a system is driven fast.

The test used 10 sample cases built with Qiskit’s finance tools. The new layers beat both standard XY mixers, which also keep the budget, and the gap held at every depth from 1 to 10. The price is more two-qubit gates. That is because the extra term brings in parts that act on three qubits at once, and Falla confirmed the study ran only on a simulator.

A penalty-free encoding runs 128-vertex graphs on IBM hardware

Ulrike Stege of the University of Victoria presented work led by Prashanti Priya Angara and four others. It takes three hard graph problems that are close kin, maximum independent set, vertex cover and maximum clique. Their tool, SCOOP, writes each one for QAOA with no penalty for answers that break the rules, and the angles were trained on classical simulators except for the big cases. The circuits ran on IBM machines.

On the QOBLIB benchmark set, the largest case had 128 vertices and 1,471 edges. It needed 13,555 two-qubit gates on IBM hardware and still reached an approximation ratio of 0.75, the only graph to fall below 0.8. Stege called quantum advantage a loaded term. For these cases Stege put the claim at utility.

A pilot-assignment circuit nearly matches exhaustive search

Xiaoyu Ma of Western University, working with Fang Fang and Xianbin Wang, took constrained QAOA into wireless networks. In cell-free massive MIMO, many access points serve users together. Each user needs a pilot signal so the network can gauge its channel, but pilots are scarce, so users share them and two users who clash on one pilot spoil each other’s signal. Ma used one qubit per user and pilot. A mixer moves a user between pilots so each always holds exactly one.

In simulation the clash cost sat close to exhaustive search. That held for four to seven users and three layers, where the method also came in slightly below a greedy method and far below random assignment. More layers narrowed the gap to the best answer, while more users widened it. Ma called it a small proof of concept. One listener warned that this kind of mixer adds circuit depth on noisy hardware.

Annealers, encodings and penalties

D-Wave’s annealers are the quantum optimisers most of these talks could run on. Eight talks worked on how problems are written for them and for other machines, and what the machines return.

Fewer qubits for colouring problems

Tristan Zaborniak, now a postdoctoral fellow at the University of British Columbia, presented work done at the University of Victoria. The problems give each vertex a label, such as a colour, and seek the fewest labels. The usual way spends one qubit per vertex per colour. Their way writes each colour as a binary number, so it needs far fewer qubits at the start, though the terms it creates are harder for the chip to handle.

On a D-Wave annealer, 300 graphs of 5 to 50 nodes ran a thousand shots each. After the extra terms were cut down to fit the chip, the qubit counts nearly matched the usual form. Yet time to solution fell. Zaborniak traced that to chains of linked qubits whose lengths varied much less from one problem to the next, which made the runs more even.

Penalties that fit the chip

Loong Kuan Lee of Fraunhofer IAIS presented work with colleagues from Los Alamos, the European Space Agency, TU Dortmund and Fraunhofer. An annealer needs a QUBO. An inequality rule wants a sharp step penalty that a QUBO cannot copy, so Lee projects the step onto simple products of bits and keeps only the low-order ones, which gives the weights in one pass with no tuning.

Lee can also keep only the links the chip already has. Then the problem needs no long chains of qubits. On a classical stand-in for annealing, a rival penalty method lost up to 17 percentage points of allowed answers on dense knapsacks, and on two D-Wave Advantage processors Lee’s version gave the lower mean gap to the best answer.

An annealer that plays favourites

Shunta Ide, a master’s student at Keio University, showed that quantum annealing plays favourites. When several answers tie for best, a classical sampler finds each one equally often. The annealer does not. Ide tested this on splitting a graph into two equal halves with the lightest cut. The equal-size rule was set either as a penalty or by a special driver that never leaves the allowed answers, so it can only move between splits of the right size.

In noiseless simulation of one instance, two of four tied answers came out near 0.4 each and two near 0.1. D-Wave hardware favoured the same states, more weakly. Ide showed that a large penalty pulls the annealer toward the behaviour of the rule-keeping driver, which is itself unfair, and that driver could only be simulated, since it cannot be set up on the D-Wave machine.

Keeping a learned model steady over time

Shun Furusawa of KDDI Research presented work with colleagues from KDDI Research and Keio University. The target is problems that change over time. Think of tuning a wireless network as radio conditions shift, where the team’s method fits a simple learned model to past results, turns it into a QUBO and asks an annealer for the next thing to try.

Furusawa found a quirk. Retraining can spin the model’s hidden matrix freely without changing any prediction, which fills the history with drift that means nothing. Their fix rotates each new matrix back into line with the last. On a base-station placement task with 126 variables, every variant run on a D-Wave Advantage2 beat random sampling, though the gaps between the variants sat within hardware noise.

American Express drops the weight limit

A paper by Sutapa Samanta, Dagen Wang and Andras Ferenczi of American Express took on the knapsack from a finance angle. The method drops the weight limit. It keeps a reward for value plus a pull toward total weight just under the cap, then samples many low-energy answers and throws out the ones that are too heavy on an ordinary computer. The presenter called it an honest caveat that a best answer far below the limit could be missed.

On 100 instances at each size from 50 to 2,000 items, simulated annealing with the filter came within 0.2 percent of Google OR-Tools. The 50-item instances also ran on annealing hardware. The presenter said noise made the results so poor that the team stopped using it.

A lopsided penalty halves the variables in a location problem

Jorge Saavedra Benavides of The Catholic University of America and three co-authors worked on where to put sites when several rules hold at once. A cap on a total is usually met by adding spare yes-or-no bits until the rule becomes an exact sum. That costs a lot of bits. So the team used a lopsided penalty, which needs half as many and goes by the name of unbalanced penalisation.

The test grids, 2 by 4 and 3 by 3, needed 12 and 13 qubits. Each was averaged over 10 random cases, and the lopsided penalty with a linear ramp and a warm start from a classical answer did best at low depth. A cost study then compiled 50-layer circuits for IBM’s Marrakesh chip. The figure does not say they were run. At 18 variables the chip needed nearly 14,000 two-qubit gates, while the method itself asked for about 2,000.

An annealer step helps a genetic algorithm on most tests

Rushit Kansara of the German Aerospace Center, with Maria Isabel Roldan Serrano, handed one step of a genetic algorithm to a D-Wave annealer. Problems with several goals have no single best answer. They have a front of trade-offs, where a gain on one goal costs another, and a standard genetic algorithm called NSGA-II breeds a crowd of answers toward that front. Kansara’s QANSGA adds a step written as a QUBO.

The yardstick was IGD, which measures how well the answers cover the true front. On the 15-variable MW1 problem, QANSGA’s score improved by 99.3 percent over NSGA-II. On DAS-CMOP8, with 30 variables and seven rules, it lost 9.7 percent, and the team traced that loss to the annealer’s limited links when the problem is laid onto the chip and to a stand-in model’s accuracy. It gained on the other four problems the team showed.

Twelve atoms route four vans

Vittorio Vitale of Pasqal mapped a small delivery problem onto neutral atoms in a tutorial on analog quantum computing. Four vans each choose one of three routes. Vans slow each other on a shared route, and two routes share a bridge. As a QUBO that is 12 yes-or-no variables, with a penalty for a van that picks two routes, and each van becomes a triangle of atoms so close that the Rydberg blockade lets only one be excited.

An adiabatic sweep then changes the drive slowly so the atoms stay in their lowest-energy state. This ran on a local emulator of Pasqal’s machine. Across 10 pulse lengths with 1,000 shots each, the share of valid answers rose above 90 percent, and the best plan’s chance rose from 4.2 percent to about 20 percent. Vitale also solved the problem by listing every option on a laptop.

Theory and where quantum optimisation goes next

The last block of the Wednesday workshop drew the fences around the whole field. A proof, a pipeline and a panel set out what can be computed, what can be built and what should come next. Earlier talks added more. They brought a result on circuit structure, a guarantee QAOA could pass, a tutorial on a rival algorithm and a second panel.

Exact QAOA scores are #P-hard at two layers

Stuart Hadfield of the NASA Quantum AI Laboratory and USRA RIACS opened the block with one theorem. For one QAOA layer, their own formula gives the expected cut value quickly. From two layers up, Hadfield said, computing it exactly is #P-hard, as hard as counting every best cut of a graph, a class theorists believe is harder still than NP.

Hadfield built a larger graph from simple gadgets and tied all the angles to one variable, so the expected value became a polynomial whose top coefficient counts the best cuts. Hadfield was careful about scope. The result holds for exact values, and Hadfield’s slide said sampling from QAOA can still be useful. The case of noisy, rough estimates remains open.

Sparser graphs for trapped-ion pulses

Swati Gupta of MIT Sloan, an operations researcher, changes the problem graph before it reaches the circuit. On trapped ions, pulses that act on all qubits at once combine with single-qubit flips to build the needed links. Finding the fewest pulses is hard, Gupta said, so their group splits the graph into stars and trims it to far fewer edges while keeping its cuts close to the original.

Gupta said sparse instances keep about 10 percent of edges. On small graphs, splitting the leftover weights into simple graphs best preserved the score map under noise, which is the circuit’s score plotted over its two angles. The method now sits in a pipeline at Oak Ridge.

The panel asks for a leap

The workshop chair closed by asking Hadfield, Gupta and Stein where the field’s foundations should go. Hadfield recalled decades of max-cut methods stuck near one half before Goemans and Williamson, and wanted a similar leap for quantum methods. Gupta asked for shared benchmarks. Stein noted that most results so far rest on academic test problems.

Which vertex is fixed changes what QAOA can reach

Jose Falla of the University of Delaware returned with Bao Bach, Boris Tsvelikhovskiy and Ilya Safro. Flipping every bit of a cut gives the same cut. So one vertex can be fixed and the circuit trimmed by a qubit, and Falla showed that the choice of vertex still changes the circuit’s dynamical Lie algebra. That is the set of all motions its parts can make together, and its size bears on how much a circuit can express and how well it trains.

Computing that algebra directly usually costs exponential time. So on trees Falla labels each vertex with a fingerprint built from its distance to the fixed root and the parity of its degree. A vertex with a unique label is certified to have its own local control. On 1,000-node random trees the method certified 643 such controls on average, and Falla was clear that it says nothing about approximation ratio or noise.

QAOA passes a proven classical guarantee on Max-k-Cut

Ruslan Shaydulin of JPMorganChase found a setting where QAOA beats the best classical algorithm with a proven guarantee. Classical solvers are very good at two-way cuts. Shaydulin said the team’s parallel Burer-Monteiro solver gets close to the upper bound in minutes on 10,000-node graphs, which leaves a quantum machine a window of seconds. So the team moved to Max-k-Cut, where each node takes one of k colours.

Random regular graphs have few short loops. So QAOA’s score on a large graph can be predicted from a small tree around one edge, by a method Shaydulin called quadratically faster than earlier ones. Against Frieze-Jerrum, a semidefinite method in the line of Goemans and Williamson, QAOA’s predicted score passed at depth 5 or less for every k studied. A greedy heuristic the team wrote still beats it, though a fitted trend suggests QAOA might overtake near depth 20.

Decoded quantum interferometry wins where a code is hidden

Simon Thelen of OTH Regensburg and Wolfgang Mauerer of the Technical University of Applied Science Regensburg gave a two-part tutorial on decoded quantum interferometry, or DQI. It needs error-corrected circuits. It also borrows its whole plan from the codes that protect data, and the morning built it up from there. The key test is that the problem’s table of rules, with rows and columns swapped, must check a code that can fix k errors.

The target was Max-LINSAT, which asks for as many true linear equations as possible in arithmetic that wraps round at a prime, like a clock. The method sets up an even mix over strings with exactly k ones, then decodes to clear a register. A sparse example with 108 ones sat beside a dense one with 341, to show that sparse codes have fast decoders and come close to the best rates a code can reach. A closed formula gives the quality, so no circuit was run.

The afternoon asked where DQI can win, and the answer was narrow. Advantage is claimed on one problem built from a Reed-Solomon code, where simulated annealing does no better than guessing at large sizes. Sparse problems tell the opposite story. On one with 20,000 variables, simulated annealing beat DQI paired with a fast decoder across the whole range.

A second panel splits over fault-tolerant QAOA

Reuben Tate of Los Alamos National Laboratory chaired a panel of Shaydulin, Venturelli and Marwa Farag of NVIDIA. Shaydulin said AI agents now do much of the group’s work, and that the QAOA runs set against DQI took them a weekend. Farag called for an open benchmark set for optimisation. Chemistry already has one.

Fault tolerance drew the sharpest split. Shaydulin argued that QAOA stays cheap on error-corrected machines, at tens of thousands of T gates, the costly steps on such machines, for 10 to 50 layers. Venturelli wanted noise kept as a tool.

Industrial tests of quantum optimisation

Five talks set quantum optimisation against the plans, plants and wafers that firms already handle with classical tools, and against the people who would have to use it. Most of the verdicts went to the classical side. The most hopeful one came from simulation.

Quantum interior point methods lose even on generous terms

Lennart Binkowski of Quantagonia asked if a quantum method could ever beat classical solvers on linear programmes. These have a linear cost and linear rules, and classical software has solved them well for decades, so the quantum version keeps the classical loop and hands only each inner set of equations to a quantum solver. Binkowski did not run it. The theory was turned into a formula with every constant kept.

Every choice favoured the quantum side, with one round to finish and no cost at all for error correction. A classical solver then ran real cases from four standard test libraries to log the inputs the bound needs. At real gate speeds it lost everywhere. The share of cases where the quantum bound won fell to zero well before today’s fastest two-qubit gates, and Binkowski said these methods need a new design, with reading out the full answer as the main block.

Only a classical annealer solved the Siemens schedule at every size

Hila Safi of Siemens and OTH Regensburg presented work with four co-authors on a real factory problem. On Siemens lines that place parts on circuit boards, jobs are spread across machines. Each job needs its own tools, called rigs, and they take time to change. To save qubits, the team gave the choice of which machine runs which job to the quantum or quantum-like solver and left the order of jobs to simple classical sorting.

Cases ran up to 32 machines, 85 rigs and 256 jobs. D-Wave’s hybrid solver found the best answer up to about 15 qubits, and on IBM Heron chips QAOA managed only toy sizes. Only the Fujitsu Digital Annealer, a classical machine that copies annealing, solved every size. It beat simple rules of thumb given equal time, and Safi said the way the problem is written, split and fed to the machine matters more than raw size.

A quantum kernel tunes a simulated diamond process faster

Yusuke Suzuki of Tokyo Electron America and Mitsuharu Takeori of IBM Research Tokyo presented work with five colleagues. Each test wafer costs time and money. So process engineers use Bayesian optimisation, which fits a cheap model to past trials and picks the next one to try, and the team swapped that model’s sense of how alike two settings are for a quantum kernel. The kernel compares settings through quantum states.

The simulated chamber had 18 settings, such as heat, pressure and gas flow, folded into one score. In a 54-qubit simulation the quantum version got better faster than Optuna’s classical sampler and ended with a better score. Takeori stressed that the circuit used little entanglement. So it can still be run on an ordinary computer, and on an IBM Heron chip the noise was too high to repeat the run from scratch.

Applied work needs people who span qubits to patients

Emily Tucker of Clemson University said applied quantum optimisation needs people who can cross every layer, from the qubits to the people helped. Tucker set a health-care problem beside the quantum stack. One runs from patients up to models, the other from physics up to code. Put a quantum expert behind a classical modeller, Tucker warned, and the expert takes on the modeller’s view of the problem and can lose any speed-up.

The first case was job-shop scheduling, from work with IonQ led by Lopez-Ruiz. A fixed QAOA schedule worked only in a narrow band of settings at 12, 24 and 32 qubits. Thinking about daily use had pushed the team to a version that warm-starts itself round after round, and Tucker said it still worked with settings off by a factor of ten. A second project places radio nodes before a hurricane. The aim, prompted by Hurricane Helene in 2024, is to keep ambulance crews in the North Carolina mountains in touch when roads and links fail.

Perhaps one conversation in 50 finds a quantum problem

Tucker and Dupont closed the applications block of the workshop on a panel with the session’s first speaker. That speaker had put each generator’s on-off choice on a qubit. The hybrid method tied with picking at random up to 13 generators, because its optimiser drew about 10 million samples, more than the number of possible answers.

The three speakers agreed on the main point, that classical solvers already handle most problems well. Tucker put the hit rate low, saying that perhaps one in 50 conversations with experts in a field proves useful for quantum work. One listener made a proposal. The field should pick a single flagship hard problem.

What it means for companies with optimisation problems

A company with a knapsack or a scheduling problem today should take the classical half of these methods and leave the quantum half in the lab. Simulated annealing with a filter, OR-Tools and Gurobi did the reliable work in these talks, and the American Express team stopped using annealing hardware on its knapsacks because of noise. For researchers, Hadfield’s proof marks where exact QAOA scores become intractable. The open case of noisy estimates is where any claim for quantum sampling must be won.

QAOA itself grew from work led by Edward Farhi in 2014. Ziegler’s group reported beating the classical bar on chosen graphs. Antoine Lemelin cut against this reading by replacing the classical tuning loop with measurements made inside the circuit, though only on instances of up to about ten qubits. Yet no quantum method carries a guarantee of its own, the thing Goemans and Williamson supplied with one new idea. Until a quantum method promises better than 0.878, the classical half will keep doing the steering. The leap Hadfield asked for in Toronto has not yet been found.