Quantum Circuit Design for Decoded Quantum Interferometry

Understand

Decoded Quantum Interferometry (DQI) is a recently proposed quantum algorithm for approximating solutions to combinatorial optimization problems by reducing instances of linear satisfiability to bounded-distance decoding over superpositions of quantum states.

• A central challenge in realizing DQI is the design of a decoder that operates coherently on quantum superpositions.
• In this work, we present a concrete quantum circuit implementation of DQI, with a focus on the decoding subroutine.
• Our design leverages a reversible Gauss-Jordan elimination circuit for the decoding stage.