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:2503.24107 · Journal of the Physical Society of Japan

Efficient Construction of Feasible Solutions in Column Generation Using Quantum Annealing

Taisei Takabayashi, Naoki Maruyama, Takuma Yoshihara, Renichiro Haba, Masayuki Ohzeki

Published Aug 18, 2025• 0 citations
arXivHTMLPDF

Abstract

Column generation (CG) has been used to solve constrained 0-1 quadratic programming problems. The pricing problem, which is iteratively solved in CG, can be reduced to an unconstrained 0-1 quadratic programming problem, allowing for the efficient application of quantum annealing (QA). The solutions obtained by CG are continuous relaxations, which cannot be practically used as feasible 0-1 solutions. This study proposes a post-processing method for constructing feasible 0-1 solutions from the continuous relaxations obtained through CG. Numerical experiments on randomly generated problems demonstrate that CG with the proposed post-processing yields solutions comparable to commercial solvers with significantly reduced computation time.

DOI
10.7566/jpsj.94.094005

Related papers

Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing

Sota Hirama, Masayuki Ohzeki

We propose an efficient algorithm that combines column generation and quantum annealing to solve binary quadratic problems. Binary quadratic problems are difficult to solve because they are NP-hard. An attempt to solve binary quadratic problems efficiently by column generation has been studied, but it demands successively solving quadratic unconstrained binary optimization problems. We solve the bottleneck by using quantum annealing or simulated annealing. Our results demonstrate a good approximate solution obtained in 2.7 to 1000 times shorter computational time to use column generation and quantum annealing to solve binary quadratic problems than the existing fast solver.

arXiv:2307.05966•Journal of the Physical Society of Japan•Oct 19, 2023•16 citations

QC-C&CG: Quantum-Classical Algorithm for Two-stage Adaptive Robust Optimization

Duong The Do, Jiaming Cheng, Duong Tung Nguyen

Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.

arXiv:2609.13216•Aug 28, 2026•0 citations

Continuous black-box optimization with quantum annealing and random subspace coding

Syun Izawa, Koki Kitai, Shu Tanaka +2 more

A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. Herein, we apply quantum annealing (QA) to overcome the difficulty in the continuous black-box optimization. As QA specializes in optimization of binary problems, a continuous vector has to be encoded to binary, and the solution of QA has to be translated back. Our method has the following three parts: 1) Random subspace coding based on axis-parallel hyperrectangles from continuous vector to binary vector. 2) A quadratic unconstrained binary optimization (QUBO) defined by acquisition function based on nonnegative-weighted linear regression model which is solved by QA. 3) A penalization scheme to ensure that the QA solution can be translated back. It is shown in benchmark tests that its performance using D-Wave Advantage$^{\rm TM}$ quantum annealer is competitive with a state-of-the-art method based on the Gaussian process in high-dimensional problems. Our method may open up a new possibility of quantum annealing and other QUBO solvers including quantum approximate optimization algorithm (QAOA) using a gated-quantum computers, and expand its range of application to continuous-valued problems.

arXiv:2104.14778•Apr 30, 2021•1 citation

Quadratic Continuous Quantum Optimization

Sascha Mücke, Thore Gerlach, Nico Piatkowski

Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression due to their discrete nature. We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained quadratic programs via a sequence of QUBO instances. Rather than encoding real variables as binary vectors, QCQO implicitly represents them using continuous QUBO weights and iteratively refines the solution by summing sampled vectors. This allows flexible control over the number of binary variables and adapts well to hardware constraints. We prove convergence properties, introduce a step size adaptation scheme, and validate the method on linear regression. Experiments with simulated and real quantum annealers show that QCQO achieves accurate results with fewer qubits, though convergence slows on noisy hardware. Our approach enables quantum annealing to address a wider class of continuous problems.

quant-pharXiv:2512.24759•Jan 1, 2026•0 citations

Extending Quantum Annealing to Continuous Domains: a Hybrid Method for Quadratic Programming

Hristo N. Djidjev

We propose Quantum Enhanced Simulated Annealing (QESA), a novel hybrid optimization framework that integrates quantum annealing (QA) into simulated annealing (SA) to tackle continuous optimization problems. While QA has shown promise in solving binary problems such as those expressed in Ising or QUBO form, its direct applicability to real-valued domains remains limited. QESA bridges this gap by using QA to select discrete search directions that guide SA through the continuous solution space, enabling the use of quantum resources without requiring full problem discretization. We demonstrate QESA’s effectiveness on box-constrained quadratic programming (QP) problems, a class of non-convex optimization tasks that frequently arise in practice. Experimental results show that QESA consistently outperforms classical baselines in solution quality, particularly on larger and more ill-conditioned problems, while maintaining competitive runtime. As quantum annealing hardware matures, QESA offers a scalable and flexible strategy for leveraging quantum capabilities in continuous optimization.

arXiv:2504.02073•ACM Transactions on Quantum Computing•Apr 7, 2026•0 citations

On good encodings for quantum annealer and digital optimization solvers

Alberto Ceselli, Marco Premoli

Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.

Scientific Reports•Apr 6, 2023•10 citations
Column generation (CG) has been used to solve constrained 0-1 quadratic programming problems. The pricing problem, which is iteratively solved in CG, can be reduced to an unconstrained 0-1 quadratic programming problem, allowing for the efficient application of quantum annealing (QA). The solutions obtained by CG are continuous relaxations, which cannot be practically used as feasible 0-1 solutions. This study proposes a post-processing method for constructing feasible 0-1 solutions from the continuous relaxations obtained through CG. Numerical experiments on randomly generated problems demonstrate that CG with the proposed post-processing yields solutions comparable to commercial solvers with significantly reduced computation time.
We propose an efficient algorithm that combines column generation and quantum annealing to solve binary quadratic problems. Binary quadratic problems are difficult to solve because they are NP-hard. An attempt to solve binary quadratic problems efficiently by column generation has been studied, but it demands successively solving quadratic unconstrained binary optimization problems. We solve the bottleneck by using quantum annealing or simulated annealing. Our results demonstrate a good approximate solution obtained in 2.7 to 1000 times shorter computational time to use column generation and quantum annealing to solve binary quadratic problems than the existing fast solver.
Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.
A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. Herein, we apply quantum annealing (QA) to overcome the difficulty in the continuous black-box optimization. As QA specializes in optimization of binary problems, a continuous vector has to be encoded to binary, and the solution of QA has to be translated back. Our method has the following three parts: 1) Random subspace coding based on axis-parallel hyperrectangles from continuous vector to binary vector. 2) A quadratic unconstrained binary optimization (QUBO) defined by acquisition function based on nonnegative-weighted linear regression model which is solved by QA. 3) A penalization scheme to ensure that the QA solution can be translated back. It is shown in benchmark tests that its performance using D-Wave AdvantageTM^{\rm TM}TM quantum annealer is competitive with a state-of-the-art method based on the Gaussian process in high-dimensional problems. Our method may open up a new possibility of quantum annealing and other QUBO solvers including quantum approximate optimization algorithm (QAOA) using a gated-quantum computers, and expand its range of application to continuous-valued problems.
Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression due to their discrete nature. We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained quadratic programs via a sequence of QUBO instances. Rather than encoding real variables as binary vectors, QCQO implicitly represents them using continuous QUBO weights and iteratively refines the solution by summing sampled vectors. This allows flexible control over the number of binary variables and adapts well to hardware constraints. We prove convergence properties, introduce a step size adaptation scheme, and validate the method on linear regression. Experiments with simulated and real quantum annealers show that QCQO achieves accurate results with fewer qubits, though convergence slows on noisy hardware. Our approach enables quantum annealing to address a wider class of continuous problems.
We propose Quantum Enhanced Simulated Annealing (QESA), a novel hybrid optimization framework that integrates quantum annealing (QA) into simulated annealing (SA) to tackle continuous optimization problems. While QA has shown promise in solving binary problems such as those expressed in Ising or QUBO form, its direct applicability to real-valued domains remains limited. QESA bridges this gap by using QA to select discrete search directions that guide SA through the continuous solution space, enabling the use of quantum resources without requiring full problem discretization. We demonstrate QESA’s effectiveness on box-constrained quadratic programming (QP) problems, a class of non-convex optimization tasks that frequently arise in practice. Experimental results show that QESA consistently outperforms classical baselines in solution quality, particularly on larger and more ill-conditioned problems, while maintaining competitive runtime. As quantum annealing hardware matures, QESA offers a scalable and flexible strategy for leveraging quantum capabilities in continuous optimization.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.