From Constraint to Code: DQI-Kit – A Software Framework for Decoded Quantum Interferometry
Simon Thelen, Wolfgang Mauerer · 2026
Read From Constraint to Code: DQI-Kit – A Software Framework for Decoded Quantum Interferometry by Simon Thelen, Wolfgang Mauerer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16955.txt.
Introduction
Thelen and Mauerer present DQI-Kit, a software tool that encodes constrained optimisation problems into Max-LINSAT for decoded quantum interferometry. Hard optimisation with quantum methods usually forces domain goals and constraints into formats a chosen algorithm accepts, adding overhead that can threaten quantum advantage. Their tool offers a unified, open interface for auto encoding, letting users describe common work goals and constraints, and estimates DQI performance on resulting cases. An initial analysis of the transforms discusses inefficiencies and fixes.
Catalog record
| CREATOR | Simon Thelen, Wolfgang Mauerer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61398 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16955
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
From Constraint to Code: DQI-Kit – A Software Framework for Decoded Quantum Interferometry Simon Thelen, Wolfgang Mauerer Abstract 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. DQI native Optimal for DQI Objectives Constraints Weighted Max-XORSAT a\oplus b\oplus c=1[\times 2] a\oplus c=0 Max-XORSAT a\oplus b\oplus c=1 a\oplus b+c=1 a\oplus c=0 Classical Hamiltonian 2ZIZ-3ZZZ Linear objective 4a-c Set inclusion constraint a-b\in\{1,2\}\mod{6} Pseudo-Boolean function a(b+c-bc) Binary linear objective 3x+2y Boolean constraint x\wedge(y\vee z) Low degree pseudo-Boolean function ab-2bc Linear inequality 2a-3b+4>c Linear equality 4a+b=3c Binary non-linear constraint a(b+c)\geq 2bc Weighted Set-Max-LINSAT 2a-c\in\{1,2\}\pmod{p} b+2c\in\{0\}\pmod{p}[\times 2] Symmetric Set-Max-LINSAT 2a-c\in\{1,2\}\pmod{p} b+2c\in\{0,1\}\pmod{p} Fig. 1 : Transformations between formulations implemented by DQI-Kit. Red dashed lines represent transformations that increase the number of constraints; blue dotted lines represent transformations that add additional auxiliary variables; yellow dash-dotted lines represent transformations that lead to many linearly dependent constraints often negatively impacting DQI performance; grey solid lines represent (favourable) transformations where none of the above apply. I Introduction Owing to their computational difficulty even for small instance sizes, hard combinatorial optimisation problems are considered prime candidates for quantum advantage. Consequently, they are one of the most widely studied aspects of quantum software. Many proposed algorithmic approaches such as quantum annealing and QAOA can be applied to optimisation problems in QUBO format (Quadratic Unconstrained Binary Optimisation) [ 61 , 6 , 57 , 58 , 4 , 5 ] . This, in principle, allows for approximating solutions to all NP-complete optimisation problems, as the required transformations are well known [ 31 ] . Although QUBO formulations are, in practical applications, much less common than classical problem formulations such as Boolean satisfiability (SAT) or mixed-integer linear programs (MILP), extensive research has been conducted on how to bridge the gap between domain problem descriptions and QUBO formulations [ 63 , 30 , 14 ] . This enables domain experts to apply QUBO-based quantum algorithms to a broad class of industrial use cases. Decoded Quantum Interferometry (DQI) provides a new algorithmic framework that reduces combinatorial optimisation problems to the decoding problem of a classical error-correcting code [ 25 ] . Unlike most previous quantum approaches, which are largely heuristic in nature, the approximation performance of DQI can often be efficiently computed analytically. This allows researchers and engineers to evaluate the potential of DQI in size regimes that would otherwise be inaccessible with current hardware, enabling them to identify problem classes suitable for the algorithm. The optimisation problems native to DQI are Max-XORSAT and its generalisation Max-LINSAT. Formulating domain use cases as Max-LINSAT instances works very differently than for established formulations [ 50 , 15 , 28 ] like SAT, MILP or QUBO. Consequently, both research and tool support are necessary, as both are currently lacking. Moreover, the solution quality of DQI varies substantially between instances as it depends on properties of an error-correcting code based on the specific Max-LINSAT instance. Thus, assessing the suitability of DQI for a specific problem formulation requires knowledge of coding theory, adding further barriers not only for many quantum researchers, but also for domain users. Published research on potential applications of DQI has mostly focused on coding-theoretic problems that have little to no practical relevance outside of purely algebraic contexts. Consequently, we introduce DQI-Kit , a framework that aims to aid quantum software engineers in overcoming these difficulties. It available in our code repository and reproduction package (links in PDF) [ 33 ] . DQI-Kit provides an extensible, unified interface to model various types of constraints and objectives that are common in many industrial combinatorial optimisation problems. Our framework converts such constraints and objectives into DQI-native Max-LINSAT formulations by performing a series of problem transformations, as shown in Figure 1 . DQI-Kit also estimates the approximation performance achievable with DQI and compares it to the results of several classical solvers. As visualised by the different-coloured arrows in Figure 1 , not all problem encodings are equally efficient, highlighting the need for a systematic exploration of the space of possible formulations and transformation paths. We aim to initiate this exploration by providing a first analysis of the efficiency of the encoding approaches implemented by our framework (which is known to be an important issue in general for quantum algorithms [ 17 , 5 , 54 , 49 , 52 , 50 , 51 ] ). The rest of this work is structured as follows: In Section II , we explain the context of our work by presenting the Max-LINSAT problem formulation and by providing brief introductions to both error-correcting codes and the DQI algorithm. Section III covers the problem encodings and transformations implemented by DQI-Kit. In Sections IV and V , we derive guidelines on how to identify problem instances suitable to DQI and options to mitigate some of the limitations of DQI. Section VI presents the DQI-Kit framework. Related work is discussed in Section VII . Finally, we summarise our contributions and give an overview on future work in Section VIII . II Preliminaries II-A The Max-LINSAT Problem The canonical problem that DQI is designed to solve is Max-LINSAT , formalised as follows: Definition 1 . Given a finite field \mathbb{F}_{q} , a matrix \boldsymbol{B}\in\mathbb{F}_{q}^{m\times n} and a vector \boldsymbol{v}\in\mathbb{F}_{q} , Max-LINSAT is the problem of finding a variable assignment \boldsymbol{x}\in\mathbb{F}_{q}^{n} that maximises f(\boldsymbol{x})=\sum_{i=1}^{m}f_{i}(\boldsymbol{x})\text{ with }f_{i}(\boldsymbol{x})=\begin{cases}1&\text{if }\boldsymbol{x}\cdot\boldsymbol{b}_{i}=v_{i},\\ 0&\text{otherwise}\end{cases} where \boldsymbol{b}_{i} denotes the i -th row of \boldsymbol{B} and \cdot denotes the Euclidean inner product. In other words, a Max-LINSAT instance is defined by a set of m linear constraints over n variables x_{j}\in\mathbb{F}_{q} , where the i -the constraint is \sum_{j=1}^{n}B_{ij}x_{j}=v_{i} . The objective is then to find a variable assignment that satisfies as many constraints as possible. Recall that for any finite field \mathbb{F}_{q} , q is either a prime or a prime power. If q is prime, the field \mathbb{F}_{q} can be defined (up to isomorphism) as the set \mathbb{Z}_{q}=\{0,1,\dots,q-1\} along with addition and multiplication modulo q . Thus, for prime q ,