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

Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions

Hyakka Nakada, Shu Tanaka

Published Jul 28, 2025• 2 citations
arXivHTMLPDF

Abstract

Quantum Annealing (QA) can efficiently solve combinatorial optimization problems whose objective functions are represented by Quadratic Unconstrained Binary Optimization (QUBO) formulations. For broader applicability of QA, quadratization methods are used to transform higher-order problems into QUBOs. However, quadratization methods for complex problems involving Machine Learning (ML) remain largely unknown. In these problems, strong nonlinearity and dense interactions prevent conventional methods from being applied. Therefore, we model target functions by the sum of rectified linear unit bases, which not only have the ability of universal approximation, but also have an equivalent quadratic-polynomial representation. In this study, the proof of concept is verified both numerically and analytically. In addition, by combining QA with the proposed quadratization, we design a new black-box optimization scheme, in which ML surrogate regressors are inputted to QA after the quadratization process.

DOI
10.7566/jpsj.94.094801

Related papers

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

Quantum Annealing Combinatorial Optimization (QACO)

Jincheng Zhang

This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.

•Sep 3, 2026•0 citations

Quadratic unconstrained binary optimization formulation for rectified-linear-unit-type functions

Go Sato, Makiko Konoshima, Takuya Ohwa +2 more

We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.

arXiv:1811.03829•Physical review. E•Apr 4, 2019•7 citations

Embedding Inequality Constraints for Quantum Annealing Optimization.

Tomáš Vyskočil, Scott Pakin, Hristo N. Djidjev

Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.

•Jan 1, 2017•0 citations

Cutting-Edge Trajectory Optimization through Quantum Annealing

Andrea Carbone, Federico De Grossi, Dario Spiller

This paper introduces an innovative approach to explore the capabilities of Quantum Annealing (QA) for trajectory optimization in dynamic systems. The proposed method involves transforming trajectory optimization problems into equivalent binary optimization problems using Quadratic Unconstrained Binary Optimization (QUBO) representation. The procedure is general and adaptable, making it applicable to a wide range of optimal control problems that entail the satisfaction of dynamic, boundary, and path constraints. Specifically, the trajectory is discretized and approximated using polynomials. In contrast to the conventional approach of determining the polynomial degree (n) solely based on the number of boundary conditions, a specific factor is introduced in our method to augment the polynomial degree. As a result, the ultimate polynomial degree is calculated as a composite of two components: n = l + (m−1), where m denotes the count of boundary conditions and l signifies the number of independent variables. By leveraging inverse dynamics, the control required to follow the approximated trajectory can be determined as a linear function of independent variables l. As a result, the optimization function, which is represented by the integral of the square of the control, can be formulated as a QUBO problem and the QA is employed to find the optimal binary solutions.

Applied Sciences•Nov 30, 2023•7 citations

Automaton-based methodology for implementing optimization constraints for quantum annealing

Hristo N. Djidjev

Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.

ACM International Conference on Computing Frontiers (CF)•May 11, 2020•1 citation
Quantum Annealing (QA) can efficiently solve combinatorial optimization problems whose objective functions are represented by Quadratic Unconstrained Binary Optimization (QUBO) formulations. For broader applicability of QA, quadratization methods are used to transform higher-order problems into QUBOs. However, quadratization methods for complex problems involving Machine Learning (ML) remain largely unknown. In these problems, strong nonlinearity and dense interactions prevent conventional methods from being applied. Therefore, we model target functions by the sum of rectified linear unit bases, which not only have the ability of universal approximation, but also have an equivalent quadratic-polynomial representation. In this study, the proof of concept is verified both numerically and analytically. In addition, by combining QA with the proposed quadratization, we design a new black-box optimization scheme, in which ML surrogate regressors are inputted to QA after the quadratization process.
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.
This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.
We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.
This paper introduces an innovative approach to explore the capabilities of Quantum Annealing (QA) for trajectory optimization in dynamic systems. The proposed method involves transforming trajectory optimization problems into equivalent binary optimization problems using Quadratic Unconstrained Binary Optimization (QUBO) representation. The procedure is general and adaptable, making it applicable to a wide range of optimal control problems that entail the satisfaction of dynamic, boundary, and path constraints. Specifically, the trajectory is discretized and approximated using polynomials. In contrast to the conventional approach of determining the polynomial degree (n) solely based on the number of boundary conditions, a specific factor is introduced in our method to augment the polynomial degree. As a result, the ultimate polynomial degree is calculated as a composite of two components: n = l + (m−1), where m denotes the count of boundary conditions and l signifies the number of independent variables. By leveraging inverse dynamics, the control required to follow the approximated trajectory can be determined as a linear function of independent variables l. As a result, the optimization function, which is represented by the integral of the square of the control, can be formulated as a QUBO problem and the QA is employed to find the optimal binary solutions.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.