Decoded Quantum Interferometry (DQI) Reading List

1. Optimization by Decoded Quantum Interferometry

• Paper: here
• Original paper on DQI.
• Solves max-k-XORSAT with extension on max-LINSAT using LDPC codes.
• Quantum advantage claim on the Optimal Polynomial Intersection (OPI) problem using Reed-Solomon codes.
• Analytic bounds for each problem.

2. Algebraic Geometry Codes and Decoded Quantum Interferometry

• Paper: here
• Extension to Hermitian codes for OPI problem.
• Represents a fundamental advantage for quantum implementations: while Reed-Solomon codes require log₂(n) qubits per field element for block length n, Hermitian codes achieve the same block length using only (2/3)log₂(n) qubits per element.
• This decrease in quantum resource requirements becomes increasingly significant as problem sizes grow.

3. Verifiable Quantum Advantage via Optimized DQI Circuits

Resources estimation in the quantum advantage regime.

• Paper: here
• Analysis of OPI over Binary Extension Fields.
• Reed-Solomon codes possess efficient classical decoders, such as the Berlekamp-Massey decoder or the Extended Euclidean Algorithm (EEA). In the paper they introduce 2 distinct compilation strategies for the EEA, each achieving minimal qubit overhead while being tailored for different algorithmic requirements. These strategies are general and offer substantial improvements for other quantum algorithms utilizing the EEA, such as those in elliptic curve cryptography and DQI with EEA-based decoders for other codes like algebraic geometry codes and RS codes with prime fields.
• Construct end-to-end reversible quantum circuits for the full RS decoder that integrate our optimized EEA modules. The design is compatible with both the explicit and implicit EEA approaches and fully accounts for the resource costs of the subsequent decoding stages—Chien Search and Forney’s algorithm—when operating on the compact, shared-register data structures produced by our EEA implementations.
• For estimating physical costs, we assume one large rectangular grid of physical qubits with nearest neighbor connections, a uniform gate error rate of 0.1%, a surface code cycle time of 1 microsecond, and a control system reaction time of 10 microseconds. With these assumptions, the imagined physical layout of the algorithm will consist of a compute region using hot storage and a memory region using cold storage. The compute region will store logical qubits “normally", as distance d surface code patches using 2(d+ 1)² physical qubits. The cold storage memory region will store qubits more densely, by using 2D yoked surface codes.
• To summarize, we estimate that solving a classically intractable instance of the OPI problem using DQI requires ≈ 800k physical qubits and ≈ 1 hour of runtime. This estimate assumes a quantum computer with a surface code cycle time of 1 microsecond, a control system reaction time of 10 microseconds, a square grid of qubits with nearest neighbor connectivity, and a uniform depolarizing noise model with a noise strength of 1 error per 1000 gates.
• Code here: https://zenodo.org/records/17301475

4. Hamiltonian Decoded Quantum Interferometry (HDQI)

• Paper: here
• Generalization of original DQI algorithm.
• Uses coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding and quantum state preparation.
• Applications:
  • Naturally solves a quantum optimization problem, where the objective function corresponds to the energy of H.
  • HDQI efficiently prepares Gibbs states up to an inverse temperature that scales linearly with the number of efficiently decodable errors on the symplectic code of H. HDQI thus presents a new approach for Gibbs sampling, by mapping this problem to a decoding task.

5. On the Complexity of Decoded Quantum Interferometry

• DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset. This type of hardness is shared by Shor’s algorithm, but the hidden subset here has no apparent group structure.

6. Decoded Quantum Interferometry Requires Structure

• Prove that if the decoding step of DQI corrects up to the efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP) for the MAX-k-XOR-SAT.

7. No Quantum Advantage in Decoded Quantum Interferometry for MaxCut

• Show that the instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee are solvable exactly in classical polynomial time.

8. Towards solving industrial integer linear programs with Decoded Quantum Interferometry

• Apply DQI to an industrial optimization problem in the automotive industry: the vehicle option-package pricing problem.
• Developing a detailed quantum circuit implementation for belief propagation, a heuristic algorithm for decoding LDPC codes. Simple resource estimation.
• Github repository : here.

9. Quantum Circuit Design for Decoded Quantum Interferometry

• Concrete quantum circuit implementation of DQI, with a focus on the decoding subroutine.

10. Decoded Quantum Interferometry Under Noise

• Rigorous analysis of DQI under noise, focusing on local depolarizing noise.

11. Quantum advantage from soft decoders

• Provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the ISIS∞ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI.

12. Optimization of Quadratic Constraints by Decoded Quantum Interferometry

• Extend DQI to optimization problems involving quadratic constraints, which we call max QUADSAT.