FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes

One of the most promising uses for today's small, error-prone quantum computers is solving optimization problems shaped like graphs, but the translation into a circuit is unforgiving — every EDGE in the problem becomes a pair of two-qubit operations, and those are both the slowest and by far the most error-prone thing these machines do, so the achievable problem size is governed by edge count rather than anything else; this paper (Georgia Tech) notices that the research field benchmarks on graphs where every node has the same few connections, while real problems overwhelmingly follow a power-law shape in which a handful of hub nodes carry vastly more connections than everyone else, so a small number of nodes are responsible for a large share of the damage; the response is to fix those hubs to each of their two possible values in turn, which does not discard information but demotes each of their edges from an expensive two-qubit interaction into a cheap single-qubit adjustment — and a symmetry in the problem means one of each pair of resulting sub-problems can be inferred rather than run.

The argument in one glance

Problem

Every edge in the problem costs the most error-prone operation the machine has

One of the most promising near-term uses of quantum computers is an algorithm that solves graph-shaped optimization problems by translating the graph into a quantum circuit. The translation is unforgiving. Every EDGE becomes two TWO-QUBIT operations in every layer of the circuit, and those operations are the worst thing these machines do — roughly ten times slower than single-qubit operations, with error rates around one percent. It gets worse in practice, because real machines cannot connect every qubit to every other, so the compiler inserts extra operations to shuffle values into position, and after compilation the count grows faster than linearly with edge count. Since qubits also lose their state within microseconds, the chance of a useful answer collapses as problems grow. Even heavily optimized state-of-the-art systems cannot handle these problems beyond about two dozen nodes.
What people did

Cut the circuit into pieces small enough to run reliably

If a circuit is too large to run, the natural response is to divide it. Established circuit-cutting techniques do exactly this — sever a chosen number of connections in the circuit, run the resulting fragments separately on the machine, and reconstruct what the whole circuit would have produced by mathematically recombining the fragment outputs. This is a real and general technique, and it genuinely lets larger circuits run on smaller machines.
Why it fell short

The recombination is exponential, and the hubs end up in every piece

Circuit cutting works but scales badly here for three separate reasons. The number of fragments grows exponentially with the number of cuts, and so does the cost of recombining their outputs — and for real problem graphs the number of cuts needed exceeds the number of hub nodes, which is already too many. That recombination sits inside a loop where a classical optimizer repeatedly adjusts the circuit and re-runs it, so an exponentially expensive reconstruction step bottlenecks the whole procedure. And cutting these particular multi-layer circuits is awkward in itself. The related idea of splitting the problem GRAPH into subgraphs fares no better, because in a power-law graph the hub nodes end up appearing in every subgraph, which is precisely the structure that made the problem expensive to begin with.
This paper's idea

Fix the hubs to each of their values, demoting their edges rather than cutting them

This paper (Georgia Tech — Ayanzadeh, Alavisamani, Das, Qureshi) starts from an observation about what these problems actually look like. The literature benchmarks on graphs where every node has the same small number of connections, but real-world problems overwhelmingly follow a POWER-LAW shape where a few hub nodes carry vastly more connections than the rest — among 1300 United States airports, the ten busiest have ten times the average connectivity. Those hubs contribute a disproportionate share of the expensive operations, and disproportionately more of the shuffling overhead too, since the need for it grows with connectivity. So rather than cutting anything, FREEZE a hub by fixing it to each of its two possible values in turn. This splits the problem into two halves of its search space, and in each half the hub's edges do not disappear — they DEMOTE from expensive two-qubit interactions into cheap single-qubit adjustments on their neighbours. Freezing one node cuts the expensive operations by 3.13 times, and a symmetry means the second half can be inferred rather than run, so it costs nothing extra.

Why this problem is worth solving

The algorithm here is one of the strongest candidates for near-term usefulness, and its cost structure is unusually simple to state.

The QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM attacks problems of the form “assign each variable one of two values so as to minimise a cost”, which covers a great many practical optimization tasks. The problem is written as a graph — each NODE is a variable, each EDGE is a term in the cost that depends on two variables jointly — and translated into a quantum circuit. A classical optimizer then repeatedly adjusts the circuit’s parameters, re-runs it thousands of times, and uses the results to adjust again, in the same hybrid loop that several near-term quantum methods share. The cost structure is what matters here. Each edge becomes two TWO-QUBIT operations per circuit layer, and on current hardware those are by far the worst operations available — around ten times slower than single-qubit operations and carrying error rates near one percent, against qubits that lose their state within microseconds. Real machines also cannot connect every qubit directly to every other, so the compiler inserts extra operations to shuffle values into adjacency, and after compilation the total grows faster than linearly with the number of edges. The achievable problem size is therefore governed almost entirely by EDGE COUNT

, which is why even heavily optimized systems stall at a couple of dozen nodes.

The opening the paper finds comes from looking at what real problems look like.

A POWER-LAW graph is one where node connectivity is extremely uneven — most nodes have few connections while a small number of HUBS have very many. This describes an enormous range of real systems: airline routes, social networks, web links, citation graphs, biological interactions. Among 1300 United States airports the average has about 26 connections while the ten busiest have roughly ten times that. The research literature on this algorithm, however, has largely benchmarked on graphs where every node has the same small number of connections, or on fully connected ones, neither of which resembles the real cases. The encoding makes the consequence precise. The cost function is a sum of two kinds of term — a LINEAR term for each node, depending on that variable alone, and a QUADRATIC term for each edge, depending on two variables together. Only the quadratic terms require two-qubit operations; the linear terms need only cheap single-qubit rotations. So the expense of a problem is concentrated exactly where the edges are, and in a power-law graph the edges are concentrated on a handful of nodes

What people did before, and where it broke

Optimize the circuit and hope. Substantial work exists on reducing the impact of hardware errors through better compilation and scheduling. It helps, but does not change the fact that edge count sets the cost, so the ceiling stays around a couple of dozen nodes.
Circuit cutting. Sever connections in the circuit, run the fragments separately, and reconstruct the whole from their outputs. A genuine and general technique that does let larger circuits run on smaller machines.
But the recombination is exponential. The number of fragments and the cost of combining their outputs both grow exponentially in the number of cuts, and for real problem graphs the cuts needed exceed the number of hubs — already too many.
And it sits inside a loop. The reconstruction happens every time the classical optimizer adjusts parameters and re-runs, so an exponentially expensive step becomes the bottleneck of the whole procedure rather than a one-off cost.
Splitting the problem graph instead. Partitioning a large graph into subgraphs and running each on a smaller machine sounds natural, but on a power-law graph the hub nodes end up in every subgraph, so the structure causing the expense is faithfully reproduced in each piece.
The gap. Every approach divided the CIRCUIT or the GRAPH, and both divisions leave the hubs intact and require expensive reassembly. Nobody had divided the SEARCH SPACE instead, which is what allows the hubs to be removed outright and the pieces to be recombined by simply picking the better answer. That is the gap FrozenQubits fills.

How freezing a hub shrinks the circuit

Fix the hub to each of its values, demote its edges, and infer the mirror half

Edge count governs what can be run

Every edge becomes two two-qubit operations per layer, and those are ten times slower than single-qubit operations with error rates near one percent. Limited machine connectivity forces extra shuffling operations on top, so the total grows faster than linearly with edges and problems stall at a couple of dozen nodes.
↓ →
Look at what real problem graphs actually look like new

The literature benchmarks graphs where every node has the same few connections, but real problems follow a power-law shape where a few hubs carry vastly more edges than the rest. Among 1300 airports the ten busiest have ten times average connectivity, so a handful of nodes cause a large share of the cost.
↓ →
Fix a hub to each of its two possible values new

Rather than cutting anything, take the highest-connectivity node and substitute each of its two possible values in turn. This divides the search space into two exact halves, one for each value, which together cover everything the original problem covered.
↓ →
Watch the expensive terms demote rather than vanish new

With the hub fixed to a constant, every cost term joining it to a neighbour stops depending on two variables and starts depending on one. Each of its edges therefore becomes a single-qubit adjustment to that neighbour instead of a two-qubit interaction, so no information is discarded and the expensive operations simply disappear.
↓ →
Infer the mirror half instead of running it new

Flipping every variable at once leaves every two-variable term unchanged, since both signs flip and their product is preserved. When the single-variable terms are absent, the two halves are mirror images with identical costs, so only one need be run and the other is obtained by post-processing.
↓ →
Solve the small circuits and take the better answer new

Each half is optimized independently with its own classical loop on a circuit with far fewer expensive operations, and the better of the answers is kept. There is no reassembly step at all, exponentially expensive or otherwise, because the halves are alternatives rather than fragments.

Evaluated with over 5,300 circuits on eight different IBM quantum computers, on power-law graphs alongside the regular and fully connected graphs the literature conventionally uses, with data and code released publicly.

The idea

Check whether your benchmarks resemble your applications. The whole opportunity rests on an observation that required only looking. Research on this algorithm has concentrated on graphs where every node has the same small number of connections, or on fully connected graphs — mathematically clean cases that make results comparable. Real optimization problems are neither. Airline networks, social graphs, web links and citation networks all follow a power-law shape where a few hubs dominate, and that difference is not cosmetic here, because cost is concentrated exactly where edges are. On a regular graph there is no hub to remove and this technique has little to offer; on a real one, a handful of nodes carry a large share of the expense. Noticing that the structure of real inputs differs from the structure of the benchmark suite, and that the difference is exploitable, is the same look-at-the-real-workload discipline covered elsewhere on this site where measuring production behaviour reveals a pattern that the idealized model had no room for.

Freezing demotes the expensive operation rather than discarding the work. The mechanism is more elegant than “remove the hub and hope”. The cost function is a sum of single-variable terms and two-variable terms, and only the two-variable terms need the expensive operations. Fixing a hub to a constant does not delete the terms connecting it to its neighbours — it converts each from a term depending on two variables into a term depending on one, which is now a cheap single-qubit adjustment. The information those edges carried is preserved, re-encoded into the neighbours’ own coefficients. So the reduction is not an approximation; it is a change of representation in which the same problem costs less to express. That reframing, where the fix is to re-encode the work so the expensive operation is no longer needed, is the same move covered elsewhere on this site where changing what a number IS collapses the circuitry needed to compute with it, rather than optimizing the circuitry itself.

Divide the search space, not the circuit, so recombination is free. Circuit cutting divides the artefact and must then reassemble what the whole would have produced, which is exponentially expensive and sits inside the optimizer’s loop. Freezing divides the SEARCH SPACE into halves that are alternatives rather than fragments — one where the hub takes one value, one where it takes the other, together covering everything. Recombining them means comparing two answers and keeping the better, which costs nothing. And a symmetry removes half the remaining work, because flipping every variable simultaneously leaves every two-variable term unchanged, so the two halves are mirror images and only one need be run. Choosing a decomposition whose pieces are cheap to reassemble, rather than the most obvious decomposition, is the same recognise-what-is-equivalent discipline covered elsewhere on this site where exploring one representative per equivalence class replaces exhaustive enumeration.

Freezing an airport hub

From twelve expensive operations to six, then to free

How freezing works on the paper's own example. Numbers from its evaluation on real IBM machines.

Step 1 of 5

The problem as a graph

An optimization problem becomes a graph where each node is a variable taking one of two values and each edge is a cost term depending on two variables jointly. Translated into a circuit, every edge becomes two two-qubit operations per layer — the slowest and most error-prone thing the machine does.

a node connected to six others therefore contributes twelve such operations, before any compilation overhead
limited machine connectivity adds shuffling operations, and the chance of needing them rises with a node's connectivity

Why it works

Every edge becomes two of the machine’s most error-prone operations, and compilation makes the count grow faster than linearly → problem difficulty is governed by edge count → so removing edges is the most direct available lever.
Real problem graphs follow a power-law shape → a few hubs carry a disproportionate share of edges, and of the shuffling overhead that grows with connectivity → so freezing one node removes far more cost than freezing an average one.
Fixing a variable to a constant turns each of its two-variable cost terms into a one-variable term → those need only cheap single-qubit operations → so the expense vanishes without any information being discarded.
The halves are alternatives covering the whole search space rather than fragments of one circuit → recombining means comparing two answers and keeping the better → avoiding the exponentially expensive reconstruction that circuit cutting needs inside the optimizer loop.
Flipping every variable leaves each two-variable term unchanged, since both signs flip → the two halves are mirror images when single-variable terms are absent → so one can be inferred and freezing a single node costs nothing extra.

What it costs (trade-offs and scope)

The benefit depends entirely on the graph having hubs. On the regular graphs the literature conventionally uses, there is no highly connected node to freeze and little to gain. The argument rests on the claim that real applications are power-law shaped, which the paper supports but which is a claim about the world rather than a theorem.
Cost grows exponentially with the number frozen. Freezing several nodes produces two raised to that number of sub-problems. The symmetry makes a single node free and two nodes cost twice the resources, but the growth is unforgiving, and the paper is explicit that a quantum budget must be set.
Returns diminish well before the cost stops growing. Improvement saturates after freezing roughly seven nodes, so the useful range is narrow and choosing where to stop is a decision the user must make, guided by circuit properties that track fidelity.
The symmetry has a precondition. The two halves are mirror images when the single-variable terms are absent, which holds for many combinatorial problems but not universally, and where it fails both halves must genuinely be run.
The evaluation cannot use real-scale problems. Demonstrating advantage with this algorithm needs hundreds of qubits and no existing machine can run that, so the benchmarks are smaller generated power-law graphs rather than industrial instances.

The evaluation

FrozenQubits was evaluated with over 5,300 circuits on eight different IBM quantum computers, using generated power-law graphs of the kind that model real networks, alongside the regular and fully connected graphs the literature conventionally uses. Solution quality was measured by how far the returned answer falls short of the optimum, with circuit properties — count of expensive operations and circuit depth, both including compilation overhead — reported separately. The comparison covers the unmodified algorithm and circuit cutting, and the authors also check whether simply running the baseline for more trials would close the gap.

Running graph optimization on a noisy quantum machine

Property	Run the circuit as generated	Circuit cutting	Freezing hub nodes
What gets divided
Cost of recombining
Effect on hub nodes
Expensive operations
Quantum resources used

Across 5,300 circuits on eight IBM machines, solution quality improves 8.73 times on average and up to 57 times. Freezing one node reduces expensive operations 3.13 times and circuit depth 2.23 times including compilation overhead, at no extra quantum cost thanks to the symmetry; freezing two reduces them 7.19 and 3.65 times at twice the resources.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read the precondition carefully, because the entire benefit depends on the problem graph having hubs. On the regular graphs this literature conventionally benchmarks there is no highly connected node to freeze and little to gain, so the argument rests on the empirical claim that real applications are power-law shaped — well supported, but a claim about the world rather than a theorem. The cost also grows exponentially in how many nodes are frozen, and although the symmetry makes a single node free and two nodes cost twice the resources, the paper is explicit that a quantum budget must be chosen, and that improvement saturates after roughly seven nodes so the useful range is narrow. That symmetry itself has a precondition — the two halves are mirror images when the single-variable cost terms are absent, which holds for many combinatorial problems but not all, and where it fails both halves must genuinely be run. Finally the evaluation cannot use real-scale instances, because demonstrating advantage with this algorithm requires hundreds of qubits and no existing machine approaches that, so the benchmarks are smaller generated graphs. To their credit the authors check the obvious objection, confirming that simply giving the unmodified baseline more trials does not close the gap once its output distribution saturates. Within that scope the lessons travel well: check whether your benchmarks resemble your applications; look for a re-encoding that removes an expensive operation rather than removing work; and when decomposing, choose the split whose pieces are cheap to put back together.

Background

Benchmark structure differs from real structure, and the right split costs nothing to undo

This paper sits in the site’s quantum computing cluster and rhymes with several ideas covered elsewhere on this site. Its opening move is to notice that the field benchmarks on regular graphs while real problems follow a power-law shape, which is the look-at-the-actual-workload discipline the cloud-capacity page shows when measuring why machines are really reclaimed reveals an exploitable pattern, and the flash-memory page shows when characterising real chips reveals structure a vendor configuration ignored. Its mechanism is subtler than removal — fixing a hub converts each of its two-variable cost terms into a one-variable term, so the expensive two-qubit operations disappear while the information they carried is re-encoded into neighbouring coefficients, which is the same change-the-representation-so-the-operation-becomes-cheap move the superconducting-logic page makes when it stops optimizing circuits and changes what a number is. Its choice to divide the SEARCH SPACE rather than the circuit is what makes recombination free, since the halves are alternatives rather than fragments and picking the better answer costs nothing, whereas circuit cutting must reassemble at exponential cost inside the optimizer loop. And its use of a symmetry to avoid running half the sub-problems — flipping every variable leaves every two-variable term unchanged — is the reason-over-equivalence-classes discipline the compiler super-optimizer and concurrency-fuzzing pages share, where recognising that two things are provably identical is what makes an intractable enumeration tractable. It also pairs naturally with the quantum-noise page, since both improve the same hybrid loop where a classical optimizer repeatedly adjusts and re-runs a quantum circuit.

If you remember only three things

1. A leading near-term quantum algorithm solves graph-shaped optimization problems by translating them into circuits, and the translation is unforgiving — every EDGE becomes two two-qubit operations per layer, which are roughly ten times slower than single-qubit operations with error rates near one percent, against qubits that lose their state within microseconds. Limited machine connectivity forces the compiler to add shuffling operations, so after compilation the count grows faster than linearly with edges. Problem difficulty is therefore governed almost entirely by edge count, and even heavily optimized systems stall at a couple of dozen nodes.
2. The opening comes from noticing that the field benchmarks on graphs where every node has the same few connections, while real problems follow a POWER-LAW shape where a few hubs carry vastly more edges — among 1300 airports the ten busiest have ten times average connectivity. Freezing a hub, meaning fixing it to each of its two possible values in turn, splits the search space into two exact halves, and crucially its edges do not disappear but DEMOTE: with the hub constant, each two-variable cost term becomes a one-variable term needing only a cheap single-qubit operation, so the information is re-encoded rather than discarded.
3. Because the halves are alternatives rather than fragments, recombining them means picking the better answer, avoiding the exponentially expensive reconstruction that circuit cutting requires inside the optimizer loop — and a symmetry, since flipping every variable leaves every two-variable term unchanged, means one half can be inferred rather than run, making a single frozen node cost nothing extra. Across 5,300 circuits on eight IBM machines, solution quality improves 8.73 times on average and up to 57 times, with expensive operations cut 3.13 times for one frozen node. The transferable lessons: check whether your benchmarks resemble your applications; look for a re-encoding that removes an expensive operation rather than removing work; and choose the decomposition whose pieces are cheap to reassemble.

Check yourself

Check your understanding

1. Freezing a hub node removes its edges from the circuit. Predict why that is not simply throwing away part of the problem.
2. Circuit cutting also divides a large quantum computation into runnable pieces. Predict why the paper argues it does not suit this problem.
3. The paper claims freezing a single hub costs no extra quantum resources despite producing two sub-problems. Predict how.
4. The technique relies on real problem graphs being power-law shaped. Predict why the paper emphasises the contrast with the field's usual benchmarks.

Sources

FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes (arXiv:2210.17037) — ASPLOS 2023; the full 14-page paper, read in full for this explainer.
ACM Digital Library (DOI 10.1145/3575693.3575741) — published version.
Data and code (Zenodo) — the authors’ released artifacts.