Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.22060 · IEEE International Conference on Quantum Software (QSW)

SAT Strikes Back: Parameter and Path Relations in Quantum Toolchains

Lukas Schmidbauer, Wolfgang Mauerer

Published Jul 7, 2025• 7 citations
arXivHTMLPDF

Abstract

In the foreseeable future, toolchains for quantum computing should offer automatic means of transforming a high level problem formulation down to a hardware executable form. Thereby, it is crucial to find (multiple) transformation paths that are optimised for (hardware specific) metrics. We zoom into this pictured tree of transformations by focussing on$k$-SAT instances as input and their transformation to QUBO, while considering structure and characteristic metrics of input, intermediate and output representations. Our results can be used to rate valid paths of transformation in advance—also in automated (quantum) toolchains. We support the automation aspect by considering stability and therefore predictability of free parameters and transformation paths. Moreover, our findings can be used in the manifesting era of error correction (since considering structure in a high abstraction layer can benefit error correcting codes in layers below). We also show that current research is closely linked to quadratisation techniques and their mathematical foundation.

DOI
10.1109/qsw67625.2025.00021

Related papers

It’s Quick to be Square: Fast Quadratisation for Quantum Toolchains

Lukas Schmidbauer, Elisabeth Lobe, Ina Schaefer +1 more

Many of the envisioned use-cases for quantum computers involve optimisation processes. While there are many algorithmic primitives to perform the required calculations, all eventually lead to quantum gates operating on quantum bits, with an order as determined by the structure of the objective function and the properties of target hardware. When the structure of the problem representation is not aligned with structure and boundary conditions of the executing hardware, various overheads degrading the computation may arise, possibly negating any possible quantum advantage. Therefore, automatic transformations of problem representations play an important role in quantum computing when descriptions (semi-)targeted at humans must be cast into forms that can be “executed” on quantum computers. Mathematically equivalent formulations are known to result in substantially different non-functional properties depending on hardware, algorithm and detail properties of the problem. Given the current state of noisy intermediate-scale quantum (NISQ) hardware, these effects are considerably more pronounced than in classical computing. Likewise, efficiency of the transformation itself is relevant because possible quantum advantage may easily be eradicated by the overhead of transforming between representations. In this article, we consider a specific class of higher-level representations, that is, PUBOs, and devise novel automatic transformation mechanisms into widely used QUBOs that substantially improve efficiency and versatility over the state of the art. In addition, we conduct a comprehensive investigation of industry-relevant problem formulations and their conversion into a quantum-specific representation, identifying significant obstacles in scaling behaviour and demonstrating how these can be circumvented.

arXiv:2411.19934•ACM Transactions on Quantum Computing•Mar 24, 2026•9 citations

Polynomial Reduction Methods and their Impact on QAOA Circuits

Lukas Schmidbauer, Karen Wintersperger, Elisabeth Lobe +1 more

Abstraction layers are of paramount importance in software architecture, as they shield the higher-level formulation of payload computations from lower-level details. Since quantum computing (QC) introduces many such details that are often unaccustomed to computer scientists, an obvious desideratum is to devise appropriate abstraction layers for QC. For discrete optimisation, one such abstraction is to cast problems in quadratic unconstrained binary optimisation (QUBO) form, which is amenable to a variety of quantum approaches. However, different mathematically equivalent forms can lead to different behaviour on quantum hardware, ranging from ease of mapping onto qubits to performance scalability. In this work, we show how using higher-order problem formulations (that provide better expressivity in modelling optimisation tasks than plain QUBO formulations) and their automatic transformation into QUBO form can be used to leverage such differences to prioritise between different desired non-functional properties for quantum optimisation. Based on a practically relevant use-case and a graph-theoretic analysis, we evaluate how different transformation approaches influence widely used quantum performance metrics (circuit depth, gates count, gate distribution, qubit scaling), and also consider the classical computational efforts required to perform the transformations, as they influence possibilities for achieving future quantum advantage. Furthermore, we establish more general properties and invariants of the transformation methods. Our quantitative study shows that the approach allows us to satisfy different trade-offs, and suggests various possibilities for the future construction of general-purpose abstractions and automatic generation of useful quantum circuits from high-level problem descriptions.

arXiv:2406.08889•IEEE International Conference on Quantum Software (QSW)•Jul 7, 2024•19 citations

Engineering the development of quantum programs: Application to the Boolean satisfiability problem

Diego Alonso, Pedro Sánchez, Francisco Sánchez-Rubio

The development of quantum programs is becoming a reality due to the rapid advancement of quantum computing. Over the past few years, a multitude of hardware platforms, algorithms, and programming languages have emerged to support this paradigm. By the very nature of Quantum Mechanics principles, there is an enormous change of philosophy when building quantum programs, which operate in a probabilistic space, unlike the deterministic behaviour shown by classical programming languages. These conceptual differences can be overcome by using techniques and tools of Software Engineering. In this paper, we apply Model-Driven Engineering techniques in a systematic way to ease the generation of quantum programs and we apply it to solve the satisfiability problem, very important in many engineering domains like verification of discrete systems and test of integrated circuits. To that aim, we contribute with a metamodel for representing quantum circuits and a model-to-text transformation to generate working IBM Qiskit code. This model-driven infrastructure is employed to automatically generate quantum programs from SAT equations through a model-to-model transformation that embeds Grover’s algorithm. Besides, we provide formulas for calculating the number of required quantum elements from SAT equations, crucial in the current context of limited quantum resources. The interoperability with other tools and the extensibility to target additional quantum platforms is guaranteed thanks to the use of a model-based toolchain. We cover several usage scenarios to validate the approach, providing exemplary SAT equations, the generated Qiskit code and the results of executing this code in IBM Quantum infrastructure.

Advances in Engineering Software•Aug 11, 2022•24 citations

An Automated Toolchain for QUBO-based Optimization with Quantum-inspired Annealers

Yun-Ting Zhang, Chin-Fu Nien, Chia-Wei Lin +4 more

Recently, quantum computers have drawn attention to their potential to solve problems faster than classical computers. However, quantum hardware’s limited practicality and scalability have led to an interest in alternative approaches to solving optimization problems. One such approach is classical quantum-inspired annealers, which provide efficient and scalable solutions for combinatorial optimization problems (COPs) using classical hardware. To use annealers, COPs must be formulated as quadratic unconstrained binary optimization (QUBO) forms. Current tools require coding expertise and manual parameter tuning, posing barriers to entry. To address these challenges, we developed a user-friendly software toolchain that offers several advantages. Our toolchain features a friendly input and output interface, an automated parameter tuner, and a library of commonly encountered COPs. Our software toolchain’s accessibility promotes the use of quantum-inspired annealers and accelerates the development of practical solutions for real-world problems.

International SoC Design Conference•Oct 25, 2023•0 citations

Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows

Benjamin Zec, Lukas Schmidbauer, Maja Franz +1 more

Integrated HPC/QC systems aim to combine classical high-performance computing with quantum processors, but cannot be reduced to mechanisms for dispatching quantum kernels. An integrated architecture must support aspects such as observability, which cannot be implemented using QPUs alone, as well as fallback execution and cost-aware decisions on whether to replace quantum tasks with classical surrogates. Such mechanisms must be approximate or benefit from problem structure to soften the inescapable exponential classical worst-case complexity. In this work, we study tensor-network ground-state search, as such a surrogate, for optimisation problems. This combines key quantum primitives with advanced classical simulation. It provides initial empirical indicators for surrogate selection criteria, and exposes end-to-end toolchain effects that may be missed when transformation steps are studied in isolation. We compare a native polynomial unconstrained optimisation to-higher-order-Ising and a quadratised quadratic unconstrained binary optimization to-quadratic-Ising formulation for Max-3-SAT. Both are encoded as matrix product operator and optimised using density matrix renormalisation group approaches, with simulated annealing (SA) as classical performance baseline. Our results show that quadratisation is not a neutral transformation step: auxiliary variables and pairwise couplings substantially degrade solution quality relative to the native higher-order representation, while SA matches or outperforms DMRG across all tested instances. Since the optima of Boolean satisfiability (SAT)-derived problems are classical product states, DMRGs advantages dont materialise here. These findings suggest that surrogate selection in HPC/QC runtimes must be encoding- and instance-aware and provide empirical groundwork for informed decisions on fallback strategies and architecture co-design.

quant-pharXiv:2608.02041•Aug 4, 2026•0 citations

Transformation-Dependent Performance-Enhancement of Digital Annealer for 3-SAT

Münch, Christian, Fritz Schinkel, Sebastian Zielinski +1 more

Quadratic Unconstrained Binary Optimization (QUBO) problems are NP-hard problems and many real-world problems can be formulated as QUBO. Currently there are no algorithms known that can solve arbitrary instances of NP-hard problems efficiently. Therefore special-purpose hardware such as Digital Annealer, other Ising machines, as well as quantum annealers might lead to benefits in solving such problems. We study a particularly hard class of problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT) problems, and specifically 3-SAT. One intriguing aspect about 3-SAT problems is that there are different transformations from 3-SAT to QUBO. We study the transformations' influence on the problem solution, using Digital Annealer as a special-purpose solver. Besides well-known transformations we investigate a novel in this context not yet discussed transformation, using less auxiliary variables and leading to very good performance. Using exact diagonalization, we explain the differences in performance originating from the different transformations. We envision that this knowledge allows for specifically engineering transformations that improve a solvers capacity to find high quality solutions. Furthermore, we show that the Digital Annealer outperforms a quantum annealer in solving hard 3-SAT instances.

arXiv:2312.11645•Dec 18, 2023•8 citations
In the foreseeable future, toolchains for quantum computing should offer automatic means of transforming a high level problem formulation down to a hardware executable form. Thereby, it is crucial to find (multiple) transformation paths that are optimised for (hardware specific) metrics. We zoom into this pictured tree of transformations by focussing onkkk-SAT instances as input and their transformation to QUBO, while considering structure and characteristic metrics of input, intermediate and output representations. Our results can be used to rate valid paths of transformation in advance—also in automated (quantum) toolchains. We support the automation aspect by considering stability and therefore predictability of free parameters and transformation paths. Moreover, our findings can be used in the manifesting era of error correction (since considering structure in a high abstraction layer can benefit error correcting codes in layers below). We also show that current research is closely linked to quadratisation techniques and their mathematical foundation.
Many of the envisioned use-cases for quantum computers involve optimisation processes. While there are many algorithmic primitives to perform the required calculations, all eventually lead to quantum gates operating on quantum bits, with an order as determined by the structure of the objective function and the properties of target hardware. When the structure of the problem representation is not aligned with structure and boundary conditions of the executing hardware, various overheads degrading the computation may arise, possibly negating any possible quantum advantage. Therefore, automatic transformations of problem representations play an important role in quantum computing when descriptions (semi-)targeted at humans must be cast into forms that can be “executed” on quantum computers. Mathematically equivalent formulations are known to result in substantially different non-functional properties depending on hardware, algorithm and detail properties of the problem. Given the current state of noisy intermediate-scale quantum (NISQ) hardware, these effects are considerably more pronounced than in classical computing. Likewise, efficiency of the transformation itself is relevant because possible quantum advantage may easily be eradicated by the overhead of transforming between representations. In this article, we consider a specific class of higher-level representations, that is, PUBOs, and devise novel automatic transformation mechanisms into widely used QUBOs that substantially improve efficiency and versatility over the state of the art. In addition, we conduct a comprehensive investigation of industry-relevant problem formulations and their conversion into a quantum-specific representation, identifying significant obstacles in scaling behaviour and demonstrating how these can be circumvented.
Abstraction layers are of paramount importance in software architecture, as they shield the higher-level formulation of payload computations from lower-level details. Since quantum computing (QC) introduces many such details that are often unaccustomed to computer scientists, an obvious desideratum is to devise appropriate abstraction layers for QC. For discrete optimisation, one such abstraction is to cast problems in quadratic unconstrained binary optimisation (QUBO) form, which is amenable to a variety of quantum approaches. However, different mathematically equivalent forms can lead to different behaviour on quantum hardware, ranging from ease of mapping onto qubits to performance scalability. In this work, we show how using higher-order problem formulations (that provide better expressivity in modelling optimisation tasks than plain QUBO formulations) and their automatic transformation into QUBO form can be used to leverage such differences to prioritise between different desired non-functional properties for quantum optimisation. Based on a practically relevant use-case and a graph-theoretic analysis, we evaluate how different transformation approaches influence widely used quantum performance metrics (circuit depth, gates count, gate distribution, qubit scaling), and also consider the classical computational efforts required to perform the transformations, as they influence possibilities for achieving future quantum advantage. Furthermore, we establish more general properties and invariants of the transformation methods. Our quantitative study shows that the approach allows us to satisfy different trade-offs, and suggests various possibilities for the future construction of general-purpose abstractions and automatic generation of useful quantum circuits from high-level problem descriptions.
The development of quantum programs is becoming a reality due to the rapid advancement of quantum computing. Over the past few years, a multitude of hardware platforms, algorithms, and programming languages have emerged to support this paradigm. By the very nature of Quantum Mechanics principles, there is an enormous change of philosophy when building quantum programs, which operate in a probabilistic space, unlike the deterministic behaviour shown by classical programming languages. These conceptual differences can be overcome by using techniques and tools of Software Engineering. In this paper, we apply Model-Driven Engineering techniques in a systematic way to ease the generation of quantum programs and we apply it to solve the satisfiability problem, very important in many engineering domains like verification of discrete systems and test of integrated circuits. To that aim, we contribute with a metamodel for representing quantum circuits and a model-to-text transformation to generate working IBM Qiskit code. This model-driven infrastructure is employed to automatically generate quantum programs from SAT equations through a model-to-model transformation that embeds Grover’s algorithm. Besides, we provide formulas for calculating the number of required quantum elements from SAT equations, crucial in the current context of limited quantum resources. The interoperability with other tools and the extensibility to target additional quantum platforms is guaranteed thanks to the use of a model-based toolchain. We cover several usage scenarios to validate the approach, providing exemplary SAT equations, the generated Qiskit code and the results of executing this code in IBM Quantum infrastructure.
Recently, quantum computers have drawn attention to their potential to solve problems faster than classical computers. However, quantum hardware’s limited practicality and scalability have led to an interest in alternative approaches to solving optimization problems. One such approach is classical quantum-inspired annealers, which provide efficient and scalable solutions for combinatorial optimization problems (COPs) using classical hardware. To use annealers, COPs must be formulated as quadratic unconstrained binary optimization (QUBO) forms. Current tools require coding expertise and manual parameter tuning, posing barriers to entry. To address these challenges, we developed a user-friendly software toolchain that offers several advantages. Our toolchain features a friendly input and output interface, an automated parameter tuner, and a library of commonly encountered COPs. Our software toolchain’s accessibility promotes the use of quantum-inspired annealers and accelerates the development of practical solutions for real-world problems.
Integrated HPC/QC systems aim to combine classical high-performance computing with quantum processors, but cannot be reduced to mechanisms for dispatching quantum kernels. An integrated architecture must support aspects such as observability, which cannot be implemented using QPUs alone, as well as fallback execution and cost-aware decisions on whether to replace quantum tasks with classical surrogates. Such mechanisms must be approximate or benefit from problem structure to soften the inescapable exponential classical worst-case complexity. In this work, we study tensor-network ground-state search, as such a surrogate, for optimisation problems. This combines key quantum primitives with advanced classical simulation. It provides initial empirical indicators for surrogate selection criteria, and exposes end-to-end toolchain effects that may be missed when transformation steps are studied in isolation. We compare a native polynomial unconstrained optimisation to-higher-order-Ising and a quadratised quadratic unconstrained binary optimization to-quadratic-Ising formulation for Max-3-SAT. Both are encoded as matrix product operator and optimised using density matrix renormalisation group approaches, with simulated annealing (SA) as classical performance baseline. Our results show that quadratisation is not a neutral transformation step: auxiliary variables and pairwise couplings substantially degrade solution quality relative to the native higher-order representation, while SA matches or outperforms DMRG across all tested instances. Since the optima of Boolean satisfiability (SAT)-derived problems are classical product states, DMRGs advantages dont materialise here. These findings suggest that surrogate selection in HPC/QC runtimes must be encoding- and instance-aware and provide empirical groundwork for informed decisions on fallback strategies and architecture co-design.
Quadratic Unconstrained Binary Optimization (QUBO) problems are NP-hard problems and many real-world problems can be formulated as QUBO. Currently there are no algorithms known that can solve arbitrary instances of NP-hard problems efficiently. Therefore special-purpose hardware such as Digital Annealer, other Ising machines, as well as quantum annealers might lead to benefits in solving such problems. We study a particularly hard class of problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT) problems, and specifically 3-SAT. One intriguing aspect about 3-SAT problems is that there are different transformations from 3-SAT to QUBO. We study the transformations' influence on the problem solution, using Digital Annealer as a special-purpose solver. Besides well-known transformations we investigate a novel in this context not yet discussed transformation, using less auxiliary variables and leading to very good performance. Using exact diagonalization, we explain the differences in performance originating from the different transformations. We envision that this knowledge allows for specifically engineering transformations that improve a solvers capacity to find high quality solutions. Furthermore, we show that the Digital Annealer outperforms a quantum annealer in solving hard 3-SAT instances.