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

ACM Symposium on Applied Computing

Towards QPU-only Quantum Annealing: Optimal Penalty Weights for CQM-to-BQM Conversion

Junhwan Cho, MinJae Lee, Insung Kim, Dongjae Lee

Published Mar 23, 2026• 0 citations
Publisher
DOI
10.1145/3748522.3779943

Related papers

Quantum Annealing and Related Optimization Methods

Arnab Das, Bikas K. Chakrabarti

•Jan 1, 2008•125 citations

Optimal Penalty Weights for CQM-to-BQM Conversion]{Towards QPU-only Quantum Annealing: Optimal Penalty Weights for CQM-to-BQM Conversion

Junwhan Cho, Minjae Lee, Insung Kim +1 more

Abstract Quantum Annealing hardware, particularly D-Wave systems, requires problems to be formulated as Binary Quadratic Models (BQM). While hybrid solvers support Constrained Quadratic Models (CQM) with native constraint handling, Quantum Processing Unit-only execution remains an important research direction. CQMs can be transformed into BQMs by encoding constraints as penalty terms, with weights controlling the trade-off between optimization and constraint satisfaction. However, optimal penalty weight selection for general CQM-to-BQM transformation remains underexplored. This work investigates optimal penalty weights for such transformations. We focus on a restricted class of CQMs where constraints follow a specific structural form while the objective function remains general, and experimentally determine optimal weights using classical solvers. We present methods for encoding these constraints and conduct experiments to examine how optimal penalty weights vary with problem scale and constraint count. Through comprehensive analysis, we identify patterns and relationships that provide practical guidance for penalty weight selection.

•Apr 1, 2026•0 citations

Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing

Hendrik Künnemann, Frank Phillipson

The problem of finding the maximum weighted cycle in a directed graph maps to optimization problems in NP, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches on the quantum computer are based on a Quadratic Unconstrained Binary Optimization (QUBO) problem formulation. This paper develops four different QUBO approaches to this problem. The first two take the starting vertex and the number of vertices used in the cycle as given, while the latter two loosen the second assumption of knowing the size of the cycle. A QUBO formulation is derived for each approach. Further, the number of binary variables required to encode the maximum weighted cycle problem with one or both assumptions for the respective approach is made explicit. The problem is motivated by finding the maximum weighted debt cycle in a debt graph. This paper compares classical computing versus currently avaiable (hybrid) quantum computing approaches for various debt graphs. For the classical part, it investigated the Depth-First-Search (DFS) method and Simulated Annealing. For the (hybrid) quantum approaches, we utilized direct embedding on the quantum annealer and two types of quantum hybrid solvers. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) machine functioned promising. The DFS method, direct QPU, and hybrid BQM (Binary Quadratic Model), on the other hand, performed less, due to memory issues, surpassing the limit of decision variables, and finding the right penalty values, respectively.

Mathematics•Jun 16, 2023•1 citation

Optimization algorithms for Quantum Annealing

E. Arvidsson

•Jan 1, 2020•0 citations

Where the Quantum Lives in D-Wave Hybrid Portfolio Optimization

Luis Lozano

We audit how much of D-Wave's hybrid quantum-classical portfolio-optimization service is actually quantum. On cardinality-constrained mean-variance-turnover instances spanning N = 10 to 640 with a Gurobi MIQP optimality anchor, the constraint-native LeapHybridCQM service matches Gurobi's proven optimum on all 54 instances where Gurobi proves optimality, but mean QPU access time is only 0.034 seconds out of a 5-second wall-clock budget, roughly 0.7% of the run. The remaining ~99% is the service's classical decomposition, sub-problem assembly, and feasibility-aware reassembly. The reported D-Wave hybrid win on this problem class is therefore a constraint-native classical pipeline with a small QPU contribution, not a quantum-sampling win. Two structural results sharpen this audit: (i) the cardinality penalty contributes a dense rank-one term that makes the penalty-encoded logical graph fully connected regardless of the original covariance density, collapsing the intended density benchmark axis for all penalty-encoded paths while leaving CQM's sparsity intact; (ii) the CQM service returns identical solutions at every tested wall-clock budget from 5 to 300 seconds and across 10 repeated calls, a determinism property of the service on this problem class. Together with two classical baselines (Gurobi MIQP and simulated annealing) and a comparison against the penalty-encoded LeapHybridBQM interface, these results extend the prior CQM-vs-BQM observation of Sakuler et al. (2025) from "CQM handles constraints natively" to the operational decomposition of where the win actually originates, a finding that reframes how D-Wave hybrid performance should be reported in quantum-finance benchmarks.

•May 10, 2026•0 citations

Quantum Annealing Algorithms: State of the Art

Du Weilin, Li Bin, Yu Peng Tian

Journal of Computer Research and Development•Sep 15, 2008•2 citations
Abstract Quantum Annealing hardware, particularly D-Wave systems, requires problems to be formulated as Binary Quadratic Models (BQM). While hybrid solvers support Constrained Quadratic Models (CQM) with native constraint handling, Quantum Processing Unit-only execution remains an important research direction. CQMs can be transformed into BQMs by encoding constraints as penalty terms, with weights controlling the trade-off between optimization and constraint satisfaction. However, optimal penalty weight selection for general CQM-to-BQM transformation remains underexplored. This work investigates optimal penalty weights for such transformations. We focus on a restricted class of CQMs where constraints follow a specific structural form while the objective function remains general, and experimentally determine optimal weights using classical solvers. We present methods for encoding these constraints and conduct experiments to examine how optimal penalty weights vary with problem scale and constraint count. Through comprehensive analysis, we identify patterns and relationships that provide practical guidance for penalty weight selection.
The problem of finding the maximum weighted cycle in a directed graph maps to optimization problems in NP, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches on the quantum computer are based on a Quadratic Unconstrained Binary Optimization (QUBO) problem formulation. This paper develops four different QUBO approaches to this problem. The first two take the starting vertex and the number of vertices used in the cycle as given, while the latter two loosen the second assumption of knowing the size of the cycle. A QUBO formulation is derived for each approach. Further, the number of binary variables required to encode the maximum weighted cycle problem with one or both assumptions for the respective approach is made explicit. The problem is motivated by finding the maximum weighted debt cycle in a debt graph. This paper compares classical computing versus currently avaiable (hybrid) quantum computing approaches for various debt graphs. For the classical part, it investigated the Depth-First-Search (DFS) method and Simulated Annealing. For the (hybrid) quantum approaches, we utilized direct embedding on the quantum annealer and two types of quantum hybrid solvers. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) machine functioned promising. The DFS method, direct QPU, and hybrid BQM (Binary Quadratic Model), on the other hand, performed less, due to memory issues, surpassing the limit of decision variables, and finding the right penalty values, respectively.
We audit how much of D-Wave's hybrid quantum-classical portfolio-optimization service is actually quantum. On cardinality-constrained mean-variance-turnover instances spanning N = 10 to 640 with a Gurobi MIQP optimality anchor, the constraint-native LeapHybridCQM service matches Gurobi's proven optimum on all 54 instances where Gurobi proves optimality, but mean QPU access time is only 0.034 seconds out of a 5-second wall-clock budget, roughly 0.7% of the run. The remaining ~99% is the service's classical decomposition, sub-problem assembly, and feasibility-aware reassembly. The reported D-Wave hybrid win on this problem class is therefore a constraint-native classical pipeline with a small QPU contribution, not a quantum-sampling win. Two structural results sharpen this audit: (i) the cardinality penalty contributes a dense rank-one term that makes the penalty-encoded logical graph fully connected regardless of the original covariance density, collapsing the intended density benchmark axis for all penalty-encoded paths while leaving CQM's sparsity intact; (ii) the CQM service returns identical solutions at every tested wall-clock budget from 5 to 300 seconds and across 10 repeated calls, a determinism property of the service on this problem class. Together with two classical baselines (Gurobi MIQP and simulated annealing) and a comparison against the penalty-encoded LeapHybridBQM interface, these results extend the prior CQM-vs-BQM observation of Sakuler et al. (2025) from "CQM handles constraints natively" to the operational decomposition of where the win actually originates, a finding that reframes how D-Wave hybrid performance should be reported in quantum-finance benchmarks.