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:2405.03029 · Engineering Optimization

Optimal box contraction for solving linear systems via simulated and quantum annealing

Sanjay Suresh, Krishnan Suresh

Published Oct 15, 2024• 3 citations
arXivHTMLPDF

Abstract

Solving linear systems of equations is an important problem in engineering. Many quantum algorithms, such as the Harrow–Hassidim–Lloyd algorithm and the box algorithm, have been proposed for solving such systems. The focus of this article is on improving the efficiency of the box algorithm. The basic principle behind this algorithm is to transform the linear system into a series of quadratic unconstrained binary optimization (QUBO) problems, which are then solved on annealing machines. The computational efficiency of the box algorithm is entirely determined by the number of iterations, which, in turn, depends on the box contraction ratio, typically set to 0.5. Here, it is shown through theoretical analysis that a contraction ratio of 0.5 is sub-optimal and that a computational speed-up can be achieved with a contraction ratio of 0.2. This is confirmed through numerical experiments where a computational speed-up between 20% to 60% is observed when the optimal contraction ratio is used.

DOI
10.1080/0305215x.2024.2408686

Related papers

Solving linear systems by quadratic unconstrained binary optimization on D-Wave quantum annealing device

Kyungtaek Jun, Rebecca Conley, Yecheng Huang +2 more

Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.

•Apr 9, 2021•6 citations

QUBO formulations for a system of linear equations

Kyungtaek Jun

With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in modern science and engineering. The Harrow Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. The algorithm was difficult to apply to general linear equations because it required various conditions for the matrix. In this paper, we introduce a new algorithm that can be applied to all linear systems. For a given general square matrix A∈Rn×n and a vector b→∈Rn, we will find quadratic unconstrained binary optimization (QUBO) models for a vector x→∈Rn that satisfies Ax→=b→. To formulate QUBO models for solving linear systems, we made use of a linear least-square problem with binary representation of the solution. We validated those QUBO models on the D-Wave system and discussed the results. For a simple system, we provide a Python code to calculate the matrix characterizing the relationship between the variables, and to print the test code that can be used directly in the D-Wave system.

Results in Control and Optimization•Feb 5, 2024•25 citations

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

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

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2026•1 citation

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

QUBO formulations for numerical quantum computing

Kyungtaek Jun

With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all science and engineering. The Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. For a given n by n matrix A and a vector b, we will find unconstrained binary optimization (QUBO) models for a vector x that satisfies Ax=b. To formulate QUBO models for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate those QUBO models on the D-Wave system and discuss the results. For a simple system, we provide a Python code to calculate the matrix characterizing the relationship between the variables and to print the test code that can be used directly in the D-Wave system.

arXiv:2106.10819•Jun 21, 2021•9 citations

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

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

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•May 27, 2025•0 citations
Solving linear systems of equations is an important problem in engineering. Many quantum algorithms, such as the Harrow–Hassidim–Lloyd algorithm and the box algorithm, have been proposed for solving such systems. The focus of this article is on improving the efficiency of the box algorithm. The basic principle behind this algorithm is to transform the linear system into a series of quadratic unconstrained binary optimization (QUBO) problems, which are then solved on annealing machines. The computational efficiency of the box algorithm is entirely determined by the number of iterations, which, in turn, depends on the box contraction ratio, typically set to 0.5. Here, it is shown through theoretical analysis that a contraction ratio of 0.5 is sub-optimal and that a computational speed-up can be achieved with a contraction ratio of 0.2. This is confirmed through numerical experiments where a computational speed-up between 20% to 60% is observed when the optimal contraction ratio is used.
Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.
With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in modern science and engineering. The Harrow Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. The algorithm was difficult to apply to general linear equations because it required various conditions for the matrix. In this paper, we introduce a new algorithm that can be applied to all linear systems. For a given general square matrix A∈Rn×n and a vector b→∈Rn, we will find quadratic unconstrained binary optimization (QUBO) models for a vector x→∈Rn that satisfies Ax→=b→. To formulate QUBO models for solving linear systems, we made use of a linear least-square problem with binary representation of the solution. We validated those QUBO models on the D-Wave system and discussed the results. For a simple system, we provide a Python code to calculate the matrix characterizing the relationship between the variables, and to print the test code that can be used directly in the D-Wave system.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
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.
With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all science and engineering. The Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. For a given n by n matrix A and a vector b, we will find unconstrained binary optimization (QUBO) models for a vector x that satisfies Ax=b. To formulate QUBO models for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate those QUBO models on the D-Wave system and discuss the results. For a simple system, we provide a Python code to calculate the matrix characterizing the relationship between the variables and to print the test code that can be used directly in the D-Wave system.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.