1 of 42

QIP 2026 Highlights: Optimization by Decoding

Devdatt Dubhashi

​

2 of 42

3 of 42

Tutorials

  • L. Lami: Quantum Hypothesis Testing
  • A. Chailloux, Algorithmic Regev Reduction
  • J. Shuster, Random Unitaries
  • D. Ahranov: Error mitigation

​

Keynotes

  • J. Watrous: Quantum education
  • S. Boixo, OTOC correlators
  • R. Kothari, Multiqubit Toffoli

​

​

4 of 42

  • S. Jordan et al, “Optimization by decoded quantum interferometry”, Nature 646 831-836 (2025)
  • A. Chailloux and J-P Tillich, “The Quantum Decoding Problem”, TQC 2024.
  • T Debris-Alazard, N Remaud, J-P Tillich, “Quantum Reduction of Finding Short Code Vectors

to the Decoding Problem”, IEEE Trans. Inf. Theory, 70(7) 2024.

  • A. Chailloux and J-P Tillich, “Quantum Advantage from Soft Decoders”, STOC 2025.

5 of 42

MAX-XORSAT

  •  

the number among the m linear equations that are

satisfied minus the number unsatisfied.

6 of 42

​

�

​

7 of 42

Codes and their Dual

8 of 42

Coding Problems

9 of 42

Coding Problems

10 of 42

Fundamental Property of QFT for Codes

11 of 42

Regev Reduction

12 of 42

Regev Reduction

13 of 42

Overall Algorithm

14 of 42

15 of 42

Instantiate general recipe: LDPC Codes

 

16 of 42

17 of 42

Overall Algorithm

18 of 42

MAX-LINSAT

19 of 42

Approximation Guarantee

20 of 42

OPI Problem

OPI is studied under the name ‘list recovery’,

and in the cryptography literature it is studied under the

name “noisy polynomial reconstruction/interpolation”

21 of 42

22 of 42

OPI and Reed Solomon Codes

  • OPI is a special case of max-LINSAT over Fp with m = p − 1 constraints in which B is a Vandermonde matrix and, thus, C⊥ is a Reed–Solomon code.
  • Syndrome decoding for Reed–Solomon codes can be solved in polynomial time out to half the distance of the code, for example, using the Berlekamp–Massey algorithm.
  • Consequently, in DQI we can take ℓ = ⌊(n + 1)/2⌋.

​

23 of 42

24 of 42

25 of 42

DQI achieves a superpolynomial

speed-up for this problem, assuming no polynomial-time algorithm. is found that can match the satisfaction fraction that DQI achieves

26 of 42

Optimization by Decoding:�Road to Quantum Advantage?

Find a code C such that

    • Decoding problem can be solved in polynomial time
    • Shortest code word in dual code corresponds to an interesting, natural optimization problem (like maxLINSAT or OPI) that is hard classically.

​

Regev Reduction gives a Quantum polynomial time algorithm.

27 of 42

Extensions to Regev

  • Quantum decoders
  • Decoders with errors

28 of 42

29 of 42

30 of 42

31 of 42

32 of 42

33 of 42

34 of 42

35 of 42

36 of 42

37 of 42

Errors in Decoder

  • Regev reduction assumes decoder is perfect i.e. no errors.
  • Unfortunately not guaranteed to be robust: small error in decoder could result in large errors in SCP problem
  • Big limitation since there are good decoding algorithms if you allow small error.

38 of 42

Solution: Inhomogeneous setting!

39 of 42

Closest Codeword problem

40 of 42

41 of 42

42 of 42

Extensions of Regev Reduction

  • Decoder can be quantum algorithm
  • Decoder can be noisy.
  • Can be used to sample from good distribution of codewords

i.e. a codeword randomly sampled from average distance to given word

(A. Gheorghiu et al 2025).

​