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:2307.10379 · npj Quantum Information

Alleviating the quantum Big-M problem

Edoardo Alessandroni, Sergi Ramos-Calderer, Ingo Roth, Emiliano Traversi, Leandro Aolita

Published Jul 26, 2025• 8 citations
arXivHTMLPDF

Abstract

Abstract A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big- M ” problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big- M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ as a function of the weight M , inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.

DOI
10.1038/s41534-025-01067-0

Related papers

Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing

Adrian Harkness, Hamidreza Validi, Ramin Fakhimi +4 more

Quantum computing offers significant potential for solving NP-hard combinatorial (optimization) problems that are beyond the reach of classical computers. One way to tap into this potential is by reformulating combinatorial problems as a quadratic unconstrained binary optimization (QUBO) problem. The solution of the QUBO reformulation can then be addressed using adiabatic quantum computing devices or appropriate quantum computing algorithms on gate-based quantum computing devices. In general, QUBO reformulations of combinatorial problems can be readily obtained by properly penalizing the violation of the problem's constraints in the original problem's objective. However, characterizing tight (i.e., minimal but sufficient) penalty coefficients for this purpose is important and non-trivial for enabling the solution of the resulting QUBO in current and near-term quantum computing devices. Along these lines, we present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem whose values depend on the (weighted) degree of the vertices of the graph defining the problem. These findings contribute to the ongoing effort to make quantum computing a viable tool for solving combinatorial problems at scale. We support our theoretical results with illustrative examples and simple numerical results.

quant-pharXiv:2511.01108•Nov 4, 2025•0 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•12 citations

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•7 citations

Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers

Edoardo Alessandroni, Sergi Ramos-Calderer, Michel Krispin +7 more

Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. Here we study the problem of a priori determining suitable penalization weights from a foundational and practical perspective. We formally establish that finding its optimal value for Gibbs solvers is $\mathsf{NP}$-hard even approximately and $\#\mathsf{P}$-hard exactly. This serves us as a motivation to develop a widely applicable heuristic strategy for determining suitable penalization weights, with provable guarantees for Gibbs solvers, and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics. We further extend the strategy to quantum approximate optimization and demonstrate its performance on Quantinuum's H2-2 trapped-ion processor.

quant-pharXiv:2604.02416•Apr 6, 2026•0 citations

A Relative Approach to Comparative Performance Analysis for Quantum Optimization

Thomas Gabor, Sebastian Zielinski, Sofie Henghuber +1 more

We discuss a small study on how to compare the performance of various solving techniques for quadratic unconstrained binary optimization (QUBO). Since well-known metrics are seldomly applicable, we suggest comparing the relative performance, i.e., how much the quality of solution (compared to other solutions of the same solver) for a QUBO shifts between different solving techniques. We propose looking for big shifts systematically for an empirical complexity analysis.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•0 citations

Best practices for portfolio optimization by quantum computing, experimented on real quantum devices

Giuseppe Buonaiuto, Francesco Gargiulo, Giuseppe De Pietro +2 more

In finance, portfolio optimization aims at finding optimal investments maximizing a trade-off between return and risks, given some constraints. Classical formulations of this quadratic optimization problem have exact or heuristic solutions, but the complexity scales up as the market dimension increases. Recently, researchers are evaluating the possibility of facing the complexity scaling issue by employing quantum computing. In this paper, the problem is solved using the Variational Quantum Eigensolver (VQE), which in principle is very efficient. The main outcome of this work consists of the definition of the best hyperparameters to set, in order to perform Portfolio Optimization by VQE on real quantum computers. In particular, a quite general formulation of the constrained quadratic problem is considered, which is translated into Quadratic Unconstrained Binary Optimization by the binary encoding of variables and by including constraints in the objective function. This is converted into a set of quantum operators (Ising Hamiltonian), whose minimum eigenvalue is found by VQE and corresponds to the optimal solution. In this work, different hyperparameters of the procedure are analyzed, including different ansatzes and optimization methods by means of experiments on both simulators and real quantum computers. Experiments show that there is a strong dependence of solutions quality on the sufficiently sized quantum computer and correct hyperparameters, and with the best choices, the quantum algorithm run on real quantum devices reaches solutions very close to the exact one, with a strong convergence rate towards the classical solution, even without error-mitigation techniques. Moreover, results obtained on different real quantum devices, for a small-sized example, show the relation between the quality of the solution and the dimension of the quantum processor. Evidences allow concluding which are the best ways to solve real Portfolio Optimization problems by VQE on quantum devices, and confirm the possibility to solve them with higher efficiency, with respect to existing methods, as soon as the size of quantum hardware will be sufficiently high.

Scientific Reports•Nov 8, 2023•73 citations
Abstract A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big- M ” problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big- M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ as a function of the weight M , inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.
Quantum computing offers significant potential for solving NP-hard combinatorial (optimization) problems that are beyond the reach of classical computers. One way to tap into this potential is by reformulating combinatorial problems as a quadratic unconstrained binary optimization (QUBO) problem. The solution of the QUBO reformulation can then be addressed using adiabatic quantum computing devices or appropriate quantum computing algorithms on gate-based quantum computing devices. In general, QUBO reformulations of combinatorial problems can be readily obtained by properly penalizing the violation of the problem's constraints in the original problem's objective. However, characterizing tight (i.e., minimal but sufficient) penalty coefficients for this purpose is important and non-trivial for enabling the solution of the resulting QUBO in current and near-term quantum computing devices. Along these lines, we present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max kkk-cut problem whose values depend on the (weighted) degree of the vertices of the graph defining the problem. These findings contribute to the ongoing effort to make quantum computing a viable tool for solving combinatorial problems at scale. We support our theoretical results with illustrative examples and simple numerical results.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. Here we study the problem of a priori determining suitable penalization weights from a foundational and practical perspective. We formally establish that finding its optimal value for Gibbs solvers is NP\mathsf{NP}NP-hard even approximately and #P\#\mathsf{P}#P-hard exactly. This serves us as a motivation to develop a widely applicable heuristic strategy for determining suitable penalization weights, with provable guarantees for Gibbs solvers, and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics. We further extend the strategy to quantum approximate optimization and demonstrate its performance on Quantinuum's H2-2 trapped-ion processor.
In finance, portfolio optimization aims at finding optimal investments maximizing a trade-off between return and risks, given some constraints. Classical formulations of this quadratic optimization problem have exact or heuristic solutions, but the complexity scales up as the market dimension increases. Recently, researchers are evaluating the possibility of facing the complexity scaling issue by employing quantum computing. In this paper, the problem is solved using the Variational Quantum Eigensolver (VQE), which in principle is very efficient. The main outcome of this work consists of the definition of the best hyperparameters to set, in order to perform Portfolio Optimization by VQE on real quantum computers. In particular, a quite general formulation of the constrained quadratic problem is considered, which is translated into Quadratic Unconstrained Binary Optimization by the binary encoding of variables and by including constraints in the objective function. This is converted into a set of quantum operators (Ising Hamiltonian), whose minimum eigenvalue is found by VQE and corresponds to the optimal solution. In this work, different hyperparameters of the procedure are analyzed, including different ansatzes and optimization methods by means of experiments on both simulators and real quantum computers. Experiments show that there is a strong dependence of solutions quality on the sufficiently sized quantum computer and correct hyperparameters, and with the best choices, the quantum algorithm run on real quantum devices reaches solutions very close to the exact one, with a strong convergence rate towards the classical solution, even without error-mitigation techniques. Moreover, results obtained on different real quantum devices, for a small-sized example, show the relation between the quality of the solution and the dimension of the quantum processor. Evidences allow concluding which are the best ways to solve real Portfolio Optimization problems by VQE on quantum devices, and confirm the possibility to solve them with higher efficiency, with respect to existing methods, as soon as the size of quantum hardware will be sufficiently high.