Quantum Circuit Design for Decoded Quantum Interferometry
arXiv:2504.18334 · doi:10.1109/QCE65121.2025.00041
Abstract
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. We analyze the circuit's depth and gate complexity and validate its performance through simulations on systems with up to 30 qubits. These results establish a concrete foundation for scalable implementations of DQI and open the door to future algorithmic refinements and hardware-level realizations.
arXiv comment10 pages, 4 figures, 2 tables, comments welcome
References in corpus (19)
- Quantum Machine Learning
- Surface codes: Towards practical large-scale quantum computation
- Ising formulations of many NP problems
- Quantum random access memory
- Multipartite entanglement and high precision metrology
- Challenges and Opportunities in Quantum Optimization
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Deterministic Preparation of Dicke States
- Quantum Circuits with Unbounded Fan-out
- Trading T gates for dirty qubits in state preparation and unitary synthesis
- Short-Depth Circuits for Dicke State Preparation
- Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers
- Improved Quantum Information Set Decoding
- Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
- Optimization by Decoded Quantum Interferometry
- The Quantum Alternating Operator Ansatz for Satisfiability Problems
- Amplitude Amplification for Optimization via Subdivided Phase Oracle
- Quantum State Preparation Using an Exact CNOT Synthesis Formulation