A local-information limit on a quantum optimization method

Can a quantum computer find good solutions to difficult constraint problems dramatically faster than an ordinary computer? For a method called decoded quantum interferometry, or DQI, a new theoretical study identifies an important restriction: how much information its decoder can access.

Brandon Augustino and colleagues at JPMorganChase’s Global Technology Applied Research center connect decoding limits to transitions studied in statistical physics. Their arXiv preprint, submitted on November 9, 2026, combines mathematical proofs with classical computer simulations. It is not a quantum-hardware demonstration, and the supplied source does not establish peer-reviewed publication.

Turning optimization into decoding

The researchers study randomly generated problems in which each constraint involves a fixed, small number of variables, and each variable appears in a fixed number of constraints. Their main examples have at least three variables per constraint and more constraints than variables.

In the binary example, Max-XORSAT, each variable is zero or one. A constraint specifies whether the sum of several variables must be even or odd. The goal is to satisfy as many constraints as possible, even when satisfying them all is impossible.

DQI attempts to prepare a quantum superposition that favors good candidate solutions. An amplitude function sets their relative quantum weights. For one important choice, the Gibbs product amplitude function, measuring the target state samples a Gibbs distribution: solutions violating fewer constraints receive greater probability. A mathematical temperature parameter controls this preference; it is not the operating temperature of a quantum processor.

Preparing that state requires decoding a related linear code from quantum information. This decoding task is part of the algorithm, not the correction of hardware noise. Its difficulty can determine whether DQI is useful.

A sharp limit for local information

A local decoder estimates codeword symbols using quantum systems within a limited neighborhood in the problem’s connection graph. Here, the permitted graph distance grows logarithmically with problem size, with a suitably small constant. Locality concerns the information accessed, not merely the size of individual quantum gates.

The authors first analyze tree-shaped graphs. They show that the best possible quantum measurement for decoding a tree’s central symbol follows a recursion matching a classical inference problem called tree reconstruction. That problem asks whether observations arbitrarily far away retain information about a central variable.

The correspondence gives a precise boundary. Where distant observations lose that information, local quantum decoding can become reliable. Beyond the reconstruction threshold, even an optimal measurement of the permitted neighborhood retains a nonzero error probability. More elaborate processing of the same local information cannot remove the obstruction.

The researchers then prove that typical neighborhoods in their random finite graphs supply the required tree-like decoding input. A two-stage decoder based on belief propagation with quantum messages reaches the attainable regime, completing the remaining symbols through linear equations.

For Max-XORSAT, they also bound the expected satisfied fraction for symmetric amplitude functions—those depending only on the number of violated constraints—when decoding succeeds with probability approaching one. The amplitude function must be chosen independently of the constraint right-hand sides, which specify the required parities. The expected satisfied fraction is averaged over uniformly random right-hand sides. Under these conditions, changing the symmetric weighting cannot surpass the asymptotic local-decoding ceiling.

What the classical comparison establishes

The quantum limit is a theorem. The broad conclusion about exponential speedups requires another ingredient: an efficient classical sampler throughout the same regime.

Statistical-physics reasoning predicts that such sampling is possible, but the paper explicitly treats this as a conjecture. Existing rigorous results cover only part of the relevant range.

The simulations support the prediction without proving it. In optimization tests, simulated annealing exceeded the estimated local-decoding ceiling on average across all 62 binary problem families and 105 larger-alphabet families tested, given sufficient computation. Some longer-run comparisons used only one to four instances, and the smallest margins were comparable to variation between instances. These are finite-size results, not proofs of asymptotic runtime.

The opening for nonlocal decoders

Removing the locality restriction reveals a second boundary. For binary Max-XORSAT in the configuration-model ensemble, with the Gibbs product amplitude function, an optimal decoder called the pretty-good measurement succeeds below the condensation threshold. Above it, every decoder has exponentially small whole-codeword success probability with high probability over the instance. Behavior exactly at the threshold remains open.

For arbitrary symmetric amplitude functions exceeding the corresponding optimization ceiling by a fixed amount, the result is weaker: decoding success cannot approach one, rather than necessarily becoming exponentially small. The output ceiling again assumes independence from the right-hand sides and averages the expected satisfied fraction over uniformly random ones.

This tightens an earlier information-theoretic ceiling, but no efficient implementation of the optimal decoder is known. The condensation result is also not proved for Gallager’s ensemble, which supplies the simulation benchmarks.

Within this symmetric-amplitude, reliable-decoding setting—and assuming the classical-sampling conjecture—a possible advantage requires efficient nonlocal decoding beyond reconstruction, plus performance exceeding nonlocal classical methods. Deeper decoders on cyclic graphs, other amplitude choices and constant-failure decoding require separate analysis.