Trying to solve hard optimisation problems with quantum techniques requires transformations of domain objectives and constraints into formats compatible with a chosen quantum algorithm. This often introduces inefficiencies and overheads that limit or even endanger potential quantum advantage for current and future approaches.To understand and mitigate these inefficiencies, software toolchains are essential for implementing transformations, analysing overheads and eventually selecting optimal transformation paths. Decoded Quantum Interferometry~(DQI) is a novel approach that achieves apparent quantum advantage for certain algebraic optimisation problems.It natively operates on Max-LINSAT, which is unusual for combinatorial optimisation, and creates the need for software solutions that alleviate the burden of manually transforming problems of interest into this format. We present DQI-Kit, a software framework that provides a unified, extensible interface for automatically encoding constrained optimisation problems into Max-LINSAT.Users can describe the various types of objectives and constraints that are common in industrial optimisation problems. Our framework converts these into Max-LINSAT instances via a series of problem transformations and computes an estimate of the expected performance of DQI on these instances. We provide an initial analysis of the implemented transformations, discussing inefficiencies and ways to mitigate them. DQI-Kit is the basis for our ultimate goal of establishing a standardised framework that will enable further investigations to identify practical use cases for which quantum advantage with DQI can be achieved.
Trying to solve hard optimisation problems with quantum techniques requires transformations of domain objectives and constraints into formats compatible with a chosen quantum algorithm. This often introduces inefficiencies and overheads that limit or even endanger potential quantum advantage for current and future approaches.To understand and mitigate these inefficiencies, software toolchains are essential for implementing transformations, analysing overheads and eventually selecting optimal transformation paths. Decoded Quantum Interferometry~(DQI) is a novel approach that achieves apparent quantum advantage for certain algebraic optimisation problems.It natively operates on Max-LINSAT, which is unusual for combinatorial optimisation, and creates the need for software solutions that alleviate the burden of manually transforming problems of interest into this format. We present DQI-Kit, a software framework that provides a unified, extensible interface for automatically encoding constrained optimisation problems into Max-LINSAT.Users can describe the various types of objectives and constraints that are common in industrial optimisation problems. Our framework converts these into Max-LINSAT instances via a series of problem transformations and computes an estimate of the expected performance of DQI on these instances. We provide an initial analysis of the implemented transformations, discussing inefficiencies and ways to mitigate them. DQI-Kit is the basis for our ultimate goal of establishing a standardised framework that will enable further investigations to identify practical use cases for which quantum advantage with DQI can be achieved.
Trying to solve hard optimisation problems with quantum techniques requires transformations of domain objectives and constraints into formats compatible with a chosen quantum algorithm. This often introduces inefficiencies and overheads that limit or even endanger potential quantum advantage for current and future approaches. To understand and mitigate these inefficiencies, software toolchains are essential for implementing transformations, analysing overheads and eventually selecting optimal transformation paths. Decoded Quantum Interferometry (DQI) is a novel approach that achieves apparent quantum advantage for certain algebraic optimisation problems. It natively operates on Max-LINSAT, which is unusual for combinatorial optimisation, and creates the need for software solutions that alleviate the burden of manually transforming problems of interest into this format. We present DQI-Kit, a software framework that provides a unified, extensible interface for automatically encoding constrained optimisation problems into Max-LINSAT. Users can describe the various types of objectives and constraints that are common in industrial optimisation problems. Our framework converts these into Max-LINSAT instances via a series of problem transformations and computes an estimate of the expected performance of DQI on these instances. We provide an initial analysis of the implemented transformations, discussing inefficiencies and ways to mitigate them. DQI-Kit is the basis for our ultimate goal of establishing a standardised framework that will enable further investigations to identify practical use cases for which quantum advantage with DQI can be achieved.
Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection (OPI) problem, strong evidence exists to show that an superpolynomial speedup exists over the best classical methods in obtaining an approximate solution. In this review, we give a self-contained description of DQI and the necessary background to understand the algorithm. Specifically, we give the essentials of Galois fields, optimization problems such as max-LINSAT and OPI, and coding theory, followed by a step-by-step walkthrough of the quantum algorithm and its operating principle.
Decoded Quantum Interferometry (DQI) is a recently introduced quantum algorithm that reduces discrete optimization to decoding with potential advantages over the best-known polynomial-time classical algorithms for certain Max-LINSAT problems. In its original formulation, however, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest. In this work, we develop multivariate Decoded Quantum Interferometry (multivariate DQI) for weighted optimization problems, focusing on the weighted Max-LINSAT problem over a prime field. Grouping constraints into N blocks by distinct weights, we introduce multivariate DQI states built from N-variable polynomials of bounded total degree, and derive a closed-form asymptotic expression for both their optimal expectation value and their concentration behavior. We give an explicit preparation circuit using a single decoder call, and extend the analysis to imperfect decoding. We also show that, for certain weighted OPI problems, multivariate DQI outperforms a natural weighted analogue of Prange's algorithm, which serves as the weighted counterpart of the classical benchmark used in the unweighted setting. Finally, we extend the ideas to Hamiltonian DQI, obtaining approximate Gibbs states for commuting Pauli Hamiltonians with block structure.
A recent paper by Jordan et al. introduced Decoded Quantum Interferometry (DQI), a novel quantum algorithm that uses the quantum Fourier transform to reduce linear optimization problems -- max-XORSAT and max-LINSAT -- to decoding problems. In this paper, we extend DQI to optimization problems involving quadratic constraints, which we call max-QUADSAT. Leveraging a connection to quadratic Gauss sums, we give an efficient algorithm to prepare the DQI state for max-QUADSAT (DISCLAIMER: A mistake was found in one of the algorithm's steps, which invalidates this result unless a fix is found). To demonstrate that our algorithm achieves a quantum advantage, we introduce the Quadratic Optimal Polynomial Intersection (quadratic-OPI) problem, a restricted variant of OPI for which, to our knowledge, the standard DQI framework offers no algorithmic speedup. We show that quadratic-OPI is an instance of max-QUADSAT and use our algorithm to optimize it. Lastly, we present a new generalized proof of the "semicircle law" for the fraction of satisfied constraints, generalizing it to any DQI state of problems where the distribution of the number of satisfied constraints for a random assignment is sufficiently close to a binomial distribution. This condition holds exactly for the DQI state of max-LINSAT, and approximately holds in the max-QUADSAT case, with the approximation becoming exponentially better as the problem size increases. This establishes performance guarantees for our algorithm.
Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems. Existing analyses are closely tied to Hamming space, which underlies the optimisation objective, Dicke state preparation and the decoding step of the algorithm. Here we extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry, where points are grouped into shells by their distance from a basepoint. Mathematically, these geometries are translation association schemes. In this setting the algorithm can be analysed by tracking one amplitude per shell, and biasing the prepared state towards high-quality solutions becomes a finite tridiagonal eigenvalue problem. As a non-Hamming example, we develop an efficient DQI protocol for finding an m x n finite-field matrix with smallest rank difference to a target matrix. Initial states are uniform superpositions over fixed-rank matrices, and Gabidulin codes provide candidates for efficient low-rank decoding up to a cutoff l. For this objective, this finds solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample. For Gabidulin nearest-codeword instances, a covering-radius obstruction shows that this bound does not imply an additive guarantee for the true optimum, and we do not claim a quantum advantage for the rank-metric construction. The results instead identify the geometric and coding ingredients for DQI beyond Hamming space.
Decoded quantum interferometry (DQI) uses classical error correction to solve optimization problems, but it is hard to tell which problems could give it a quantum advantage. We develop soundness rules that screen candidate problems by their code parameters, decoding guarantees and classical baselines. For the standard objective of counting satisfied constraints, we prove that under worst-case Hamming decoding DQI's guarantee can exceed Prange completion by at most (2−1)/2. Optimal polynomial intersection (OPI) attains this margin cap asymptotically, so no candidate in this setting can exceed OPI's margin. We also derive a performance law for real-valued objectives: the objective fixes both the solution quality and which errors the decoder must correct. An AI-agent search guided by these rules found two candidate applications. Alternant max-agreement on McEliece-type public keys tests what a secret decoder is worth to DQI against classical solvers that see only the public instance. Multiplicative polynomial intersection, a knapsack-type problem built from discrete logarithms, pairs a cosine objective with a public decoder for signed errors. For both we prove decoding guarantees and finite-length comparisons with Prange restarts, and on the larger instances we tested, DQI's expected quality exceeds what our classical solvers reach within fixed budgets.