With the increasing popularity of quantum computing and in particular quantum annealing, there has been growing research to evaluate the meta-heuristic for various problems in linear algebra: from linear least squares to matrix and tensor factorization. At the core of this effort is to evaluate quantum annealing for solving linear least squares and linear systems of equations. In this work, we focus on the viability of using quantum annealing for solving these problems. We use simulations based on the adiabatic principle to provide new insights for previously observed phenomena with the D-wave machines, such as quantum annealing being robust against ill-conditioned systems of equations and scaling quite well against the number of rows in a system. We then propose a hybrid approach which uses a quantum annealer to provide a initial guess of the solution $x_0$ , which would then be iteratively improved with classical fixed point iteration methods.With the increasing popularity of quantum computing and in particular quantum annealing, there has been growing research to evaluate the meta-heuristic for various problems in linear algebra: from linear least squares to matrix and tensor factorization. At the core of this effort is to evaluate quantum annealing for solving linear least squares and linear systems of equations. In this work, we focus on the viability of using quantum annealing for solving these problems. We use simulations based on the adiabatic principle to provide new insights for previously observed phenomena with the D-wave machines, such as quantum annealing being robust against ill-conditioned systems of equations and scaling quite well against the number of rows in a system. We then propose a hybrid approach which uses a quantum annealer to provide a initial guess of the solution $x_0$, which would then be iteratively improved with classical fixed point iteration methods.

arXiv:2206.10576Jun 21, 20226 citations

Formulation and evaluation of ocean dynamics problems as optimization problems for quantum annealing machines

Takuro Matsuta, Ryo Furue

Recent advancements in quantum computing suggest the potential to revolutionize computational algorithms across various scientific domains including oceanography and atmospheric science. The field is still relatively young and quantum computation is so different from classical computation that suitable frameworks to represent oceanic and atmospheric dynamics are yet to be explored. Quantum annealing (QA), one of the major paradigms, focuses on combinatorial optimization tasks. Given its potential to excel in NP-hard problems, QA may significantly accelerate the calculation of ocean and atmospheric systems described by the Navier-Stokes equations in the future. In this paper, we apply both QA and simulated annealing (SA), its classical counterpart, to a simplified ocean model known as the Stommel problem. We use the Stommel problem, which is not an NP problem and therefore does not benefit from QA today, just as an example, a first step in exploring QA for more intricate problems governed by the Navier-Stokes equations. We cast the linear partial differential equation governing the Stommel model into an optimization problem by the least-squares method and discretize the cost function in two ways: finite difference and truncated basis expansion. In either case, SA successfully reproduces the expected solution when appropriate parameters are chosen. In contrast, QA using the D-Wave quantum annealing machine fails to obtain good solutions for some cases owing to hardware limitations; in particular, the highly limited connectivity graph of the machine limits the size of the solvable problems, at least under currently available algorithms. Either expanding the machine's connectivity graph or improving the graph-embedding algorithms would probably be necessary for quantum annealing machines to be usable for oceanic and atmospheric dynamics problems.Recent advancements in quantum computing suggest the potential to revolutionize computational algorithms across various scientific domains including oceanography and atmospheric science. The field is still relatively young and quantum computation is so different from classical computation that suitable frameworks to represent oceanic and atmospheric dynamics are yet to be explored. Quantum annealing (QA), one of the major paradigms, focuses on combinatorial optimization tasks. Given its potential to excel in NP-hard problems, QA may significantly accelerate the calculation of ocean and atmospheric systems described by the Navier-Stokes equations in the future. In this paper, we apply both QA and simulated annealing (SA), its classical counterpart, to a simplified ocean model known as the Stommel problem. We use the Stommel problem, which is not an NP problem and therefore does not benefit from QA today, just as an example, a first step in exploring QA for more intricate problems governed by the Navier-Stokes equations. We cast the linear partial differential equation governing the Stommel model into an optimization problem by the least-squares method and discretize the cost function in two ways: finite difference and truncated basis expansion. In either case, SA successfully reproduces the expected solution when appropriate parameters are chosen. In contrast, QA using the D-Wave quantum annealing machine fails to obtain good solutions for some cases owing to hardware limitations; in particular, the highly limited connectivity graph of the machine limits the size of the solvable problems, at least under currently available algorithms. Either expanding the machine's connectivity graph or improving the graph-embedding algorithms would probably be necessary for quantum annealing machines to be usable for oceanic and atmospheric dynamics problems.

arXiv:2405.11782PLoS ONEJun 26, 20252 citations

Solving problems with quantum annealing

M. C. Thom

Digitale WeltMar 8, 20214 citations

Optimization algorithms for Quantum Annealing

E. Arvidsson

Jan 1, 20200 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.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 SciencesNov 30, 20237 citations

x_0

, which would then be iteratively improved with classical fixed point iteration methods.