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

A Direct QUBO Formulation for Alignment-Based Conformance Checking: A Preliminary Quantum Annealing Study

Joep Geuskens, Alessandro Berti, Wil M. P. van der Aalst

Published Jul 8, 2026• 0 citations
Publisher

Abstract

Alignment-based conformance checking is a central task in process mining, but computing optimal alignments is computationally hard. This paper studies whether the alignment problem can be expressed directly as a Quadratic Unconstrained Binary Optimization problem and explored with quantum annealing. We present a direct QUBO formulation for optimal alignments on safe Petri nets, with a proof-of-concept implementation supporting exact solving, simulated annealing, and a D-Wave Advantage2 quantum processing unit. The study is intentionally preliminary: rather than claiming a practical quantum advantage, we test whether the formulation is semantically correct and where current hardware helps or fails. On small representative benchmarks, the QUBO recovers correct optimal alignments, including concurrency, loops, silent transitions, and duplicate labels. On loop-heavy instances, the quantum annealer can outperform simulated annealing on success probability. Scalability, however, is strongly limited by hardware connectivity and embedding overhead. Overall, direct QUBO-based alignment finding is feasible in principle, but still far from practical large-scale use.

DOI
10.20944/preprints202607.0523.v1

Related papers

A quantum annealing approach to the minimum distance problem of quantum codes

Ismail, Refaat, Ashish Kakkar, Anatoly Y. Dymarsky

Quantum error-correcting codes (QECCs) are at the heart of fault-tolerant quantum computing. As the size of quantum platforms is expected to grow, one of the open questions is to design new optimal codes of ever-increasing size. A related challenge is to certify the quality of a given code by evaluating its minimum distance, a quantity characterizing code's capacity to preserve quantum information. This problem is known to be NP-hard. Here we propose to harness the power of contemporary quantum platforms to address this question, and in this way help design quantum platforms of the future. Namely, we introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and leveraging established QUBO algorithms and heuristics as well as quantum annealing (QA) to address the latter. The reformulation as a QUBO introduces only a logarithmic multiplicative overhead in the required number of variables. We demonstrate the formulation using the D-Wave Advantage 4.1 quantum annealer and the hybrid quantum-classical algorithm Qbsolv, and benchmark the resulting QUBO-based implementations against specialized classical distance-finding methods. The QA- and SA-assisted implementations show broadly comparable performance, while the classical comparison clarifies the relative strengths of heuristic optimization and exact distance certification. Our results establish a solver-independent QUBO formulation with only a logarithmic multiplicative overhead in the number of variables and characterize connectivity and minor embedding as central limitations of its present implementation on quantum-annealing hardware.

arXiv:2404.17703•Apr 26, 2024•0 citations

Boosting quantum annealing performance through direct polynomial unconstrained binary optimization

Sebastian Nagies, Kevin T. Geier, Javed Akram +3 more

Abstract Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.

arXiv:2412.04398•Quantum Science and Technology•Apr 9, 2025•4 citations

QUBO formulations for parallel machine scheduling

Frank Phillipson, Yoseph Y. Hutten

This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.

Computers & Operations Research•Sep 11, 2026•0 citations

qualign: solving sequence alignment based on quadratic unconstrained binary optimisation

Yuki Matsumoto, Shota Nakamura

Bioinformatics has, among others, the issue of solving complex computational problems with vast amounts of sequencing data. Recently, a new computing architecture, the annealing machine, has emerged that applies to actual problems and is available for practical use. This novel architecture can solve discrete optimisation problems by replacing algorithms designed under the von Neumann architecture. To perform computations on the annealing machine, quadratic unconstrained binary optimisation (QUBO) formulations should be constructed and optimised according to the application. In this study, we developed an algorithm under the annealing machine architecture to solve sequence alignment problems, a known fundamental process widely used in genetic analysis, such as mutation detection and genome assembly. We constructed a QUBO formulation based on dynamic programming to solve a pairwise sequence alignment and derived its general form. We compared with conventional methods to solve 40 bp of pairwise alignment problem. Our implementation, named qualign, solved sequence alignment problems with accuracy comparable to that of conventional methods. Although a small pairwise alignment was solved owing to the limited memory size of this method, this is the first step of the application of annealing machines. We showed that our QUBO formulation solved the sequencing alignment problem. In the future, increasing the memory size of annealing machine will allow annealing machines to impact a wide range of bioinformatics applications positively.Availability: the source code of qualign is available at https://github.com/ymatsumoto/qualign

EMBnet journal•Mar 8, 2023•2 citations

A QUBO Formulation for Qubit Allocation

Bryan Dury, Olivia Di Matteo

To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.

arXiv:2009.00140•Aug 31, 2020•10 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•0 citations
Alignment-based conformance checking is a central task in process mining, but computing optimal alignments is computationally hard. This paper studies whether the alignment problem can be expressed directly as a Quadratic Unconstrained Binary Optimization problem and explored with quantum annealing. We present a direct QUBO formulation for optimal alignments on safe Petri nets, with a proof-of-concept implementation supporting exact solving, simulated annealing, and a D-Wave Advantage2 quantum processing unit. The study is intentionally preliminary: rather than claiming a practical quantum advantage, we test whether the formulation is semantically correct and where current hardware helps or fails. On small representative benchmarks, the QUBO recovers correct optimal alignments, including concurrency, loops, silent transitions, and duplicate labels. On loop-heavy instances, the quantum annealer can outperform simulated annealing on success probability. Scalability, however, is strongly limited by hardware connectivity and embedding overhead. Overall, direct QUBO-based alignment finding is feasible in principle, but still far from practical large-scale use.
Quantum error-correcting codes (QECCs) are at the heart of fault-tolerant quantum computing. As the size of quantum platforms is expected to grow, one of the open questions is to design new optimal codes of ever-increasing size. A related challenge is to certify the quality of a given code by evaluating its minimum distance, a quantity characterizing code's capacity to preserve quantum information. This problem is known to be NP-hard. Here we propose to harness the power of contemporary quantum platforms to address this question, and in this way help design quantum platforms of the future. Namely, we introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and leveraging established QUBO algorithms and heuristics as well as quantum annealing (QA) to address the latter. The reformulation as a QUBO introduces only a logarithmic multiplicative overhead in the required number of variables. We demonstrate the formulation using the D-Wave Advantage 4.1 quantum annealer and the hybrid quantum-classical algorithm Qbsolv, and benchmark the resulting QUBO-based implementations against specialized classical distance-finding methods. The QA- and SA-assisted implementations show broadly comparable performance, while the classical comparison clarifies the relative strengths of heuristic optimization and exact distance certification. Our results establish a solver-independent QUBO formulation with only a logarithmic multiplicative overhead in the number of variables and characterize connectivity and minor embedding as central limitations of its present implementation on quantum-annealing hardware.
Abstract Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.
This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.
Bioinformatics has, among others, the issue of solving complex computational problems with vast amounts of sequencing data. Recently, a new computing architecture, the annealing machine, has emerged that applies to actual problems and is available for practical use. This novel architecture can solve discrete optimisation problems by replacing algorithms designed under the von Neumann architecture. To perform computations on the annealing machine, quadratic unconstrained binary optimisation (QUBO) formulations should be constructed and optimised according to the application. In this study, we developed an algorithm under the annealing machine architecture to solve sequence alignment problems, a known fundamental process widely used in genetic analysis, such as mutation detection and genome assembly. We constructed a QUBO formulation based on dynamic programming to solve a pairwise sequence alignment and derived its general form. We compared with conventional methods to solve 40 bp of pairwise alignment problem. Our implementation, named qualign, solved sequence alignment problems with accuracy comparable to that of conventional methods. Although a small pairwise alignment was solved owing to the limited memory size of this method, this is the first step of the application of annealing machines. We showed that our QUBO formulation solved the sequencing alignment problem. In the future, increasing the memory size of annealing machine will allow annealing machines to impact a wide range of bioinformatics applications positively.Availability: the source code of qualign is available at https://github.com/ymatsumoto/qualign
To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.