Solving linear systems by cool-ing down …the quantum way
Algorithms for solving linear systems have been workhorses since the development of multiphysics simulations.
These linear systems of equations typically arise when a physics problem is discretized for a solution on a computer (since our beloved computers cannot represent continuous models).
At the same time, engineering research and development on cutting-edge problems is always hungry for increasing computational resources and optimal scaling algorithms. This has led to the need for large-scale linear systems of equations to be solved using the smartest possible methods to find optimal solutions.
A possible solution that we at Quanscient are researching is whether this fundamental operation of approximating the solution as a solution to a linear system can be translated to the quantum computing world.
The problem-solutions
A linear system is a set of equations that can be written in the form of Ax=b, where A is a matrix, x is a vector, and b is a vector. The goal of solving a linear system is to find the vector x that satisfies the equations.
In the context of quantum computing, a linear system can be thought of as a transformation of a vector in a multi-dimensional space. The matrix A represents the transformation rules, and the vector b represents the result of the transformation. The goal is to find the vector x that was transformed into b.
Quantum computers can be used to solve linear systems efficiently because they have exponential capabilities to represent arrays (vectors) and to operate with them more efficiently utilizing quantum parallelism. Recent algorithms have shown that certain types of sparse and periodic matrices can be implemented with quantum gates in a poly-logarithmic number of operations, which imply an exponential speedup as the linear system grows in size.
The method
In the context of quantum computing, we propose a fresh perspective on solving linear systems. This contrasts with two established methods:
- Variational Quantum Linear Solvers: This technique involves optimizing a cost function within specific parameters, similar to adjusting settings for optimal results.
- HHL Algorithm: This method employs complex quantum transformations to "invert" a matrix, essentially finding a solution by matrix multiplication.
Instead of tweaking parameters or using intricate quantum transformations, we redefine the problem. We frame it so that the solution with the lowest energy becomes the optimal one. This notion draws from physics, where minimizing energy is crucial. This approach shares similarities with "adiabatic quantum computing," a quantum method involving gradual parameter adjustments to reach a desired state.
Core ideas:
- Speeding up solving certain large linear systems will impact future simulations of multi-physics systems.
- Within the quantum race for achieving useful quantum advantage, our method could be the seed of breakthrough in multiphysics simulation using quantum computers
- More research is needed to find optimal encoding for structured matrices where quantum speed-up is possible.