Skip to content
Quantum.world

The Signal

Preprint expects no exponential DQI speedup with local decoders

A theoretical study links the limits of local quantum decoders for decoded quantum interferometry to a statistical-physics threshold. Its authors expect no exponential sampling speedup on the instances studied, but say that comparison depends on a classical sampling prediction.

Preprint expects no exponential DQI speedup with local decoders

Local quantum decoders face a limit that makes an exponential sampling speedup unlikely for a class of decoded quantum interferometry problems, according to a new theoretical study. The authors expect the same approach to offer no advantage in approximate optimization under the amplitude-function conditions they studied, although the comparison with classical sampling rests on a prediction rather than a proof.

Source arxiv.org

The theoretical preprint was submitted to arXiv on November 9. Its authors work at Global Technology Applied Research at JPMorganChase. The result concerns random, regular sparse instances with k at least 3, not every problem that decoded quantum interferometry could address.

A decoding threshold

Decoded quantum interferometry, or DQI, recasts optimization of sparse linear constraint problems and sampling from their Gibbs measures as a problem of decoding a linear code from a quantum state. The decoder's task is to recover a codeword from qudits; its performance is one of the choices that determines how DQI performs.

The study focuses on amplitude functions that depend on a solution through its total cost. For the Max-XORSAT problem, that cost is the number of violated equations. Local decoders estimate a codeword symbol using qudits in a limited neighborhood around it.

The authors say they proved that, above a point called the tree reconstruction threshold, no local decoder can recover the whole codeword with high probability in the setting studied. The obstruction concerns the information available locally, rather than the computational complexity of a particular measurement.

The team also found that a decoder based on belief propagation with quantum messages, or BPQM, reaches the threshold. That decoder measures suitable local neighborhoods and then recovers the remaining symbols by solving linear congruences.

Where the classical comparison stands

The comparison with classical sampling is conditional. A statistical-physics method known as the cavity method predicts that local Markov chains equilibrate rapidly up to the same threshold, but the paper identifies a polynomial-time classical sampling algorithm throughout the region below that threshold as an open problem.

For approximate optimization, the authors expect no advantage with local decoders when the amplitude functions depend only on the number of violated constraints. Their general approximation bounds assume symmetric amplitude functions that do not depend on the offset, as well as reliable recovery of the codeword.

A wider decoder and open questions

The paper also examines the optimal decoder, known as the pretty-good measurement, for which no efficient implementation is known. For Max-k-XORSAT instances drawn from the configuration model, the authors find that its success is governed by a different point, the condensation threshold.

That limit is a stricter bound than the one previously derived from the Holevo bound, the authors say. They leave open whether an efficient nonlocal decoder can succeed between the local and condensation thresholds and let DQI exceed the best classical values.

The authors also leave open whether unrestricted-depth BPQM on finite graphs with cycles can succeed above the local threshold. Amplitude functions that are neither symmetric nor of the block form examined in the paper fall outside its results.

Sources

  1. No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders
  2. arXiv

Related stories

Explore

More articles