20240028664. Quantum Computer Amendable Sparse Matrix Equation Solver simplified abstract (University of Manitoba)

Quantum Computer Amendable Sparse Matrix Equation Solver

Organization Name

University of Manitoba

Inventor(s)

Vladimir I. Okhmatovski of Winnipeg (CA)

Christopher D. Phllips of Winnipeg (CA)

Quantum Computer Amendable Sparse Matrix Equation Solver - A simplified explanation of the abstract

This abstract first appeared for US patent application 20240028664 titled 'Quantum Computer Amendable Sparse Matrix Equation Solver

Simplified Explanation

The abstract of the patent application describes the development of a generalized algorithm based on the Harrow/Hassidim/Lloyd algorithm. This new algorithm provides an alternative unitary for eigenphase estimation, which is derived from research in the field of quantum walks. The advantage of this alternative unitary is that it can be applied to any arbitrary matrix equation, making it well-defined. The algorithm is particularly useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with a complexity of (nlog(n)), where n is the number of unknowns and nis is the total number of nonzero elements in the system matrix. This efficiency is independent of the matrix structure, allowing the quantum procedure to outperform classical methods for various system types. The abstract also demonstrates this using the example of sparse approximate inverse (spai) preconditioning, which involves the application of matrix inverses for matrices with n=(n).

• The patent application describes a generalized algorithm based on the Harrow/Hassidim/Lloyd algorithm.
• The algorithm provides an alternative unitary for eigenphase estimation, derived from research in quantum walks.
• The alternative unitary is well-defined for any arbitrary matrix equation.
• The algorithm is particularly useful for sparse matrix equations.
• It allows for the inverse of a matrix to be applied with a complexity of (nlog(n)), where n is the number of unknowns and nis is the total number of nonzero elements in the system matrix.
• The efficiency of the algorithm is independent of the matrix structure.
• The quantum procedure can outperform classical methods for various system types.
• The example of sparse approximate inverse (spai) preconditioning is used to demonstrate the algorithm's effectiveness.

Potential Applications:

• Sparse matrix equations in various fields such as physics, engineering, and computer science.
• Eigenphase estimation in quantum computing and quantum simulations.
• Preconditioning techniques for solving large-scale linear systems.

Problems Solved:

• Efficiently applying the inverse of a matrix in sparse matrix equations.
• Overcoming the limitations of classical methods for certain system types.
• Improving the efficiency of eigenphase estimation in quantum computing.

Benefits:

• Reduced complexity in applying the inverse of a matrix, leading to faster computations.
• Improved performance compared to classical methods for sparse matrix equations.
• General applicability to arbitrary matrix equations.
• Potential advancements in quantum computing and quantum simulations.

Original Abstract Submitted

a generalization of the harrow/hassidim/lloyd algorithm is developed by providing an alternative unitary for eigenphase estimation adopted from research in the area of quantum walks, which has the advantage of being well defined for any arbitrary matrix equation. the procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with (nlog(n)) complexity, where n is the number of unknowns, and nis the total number of nonzero elements in the system matrix. this efficiency is independent of the matrix structure, and hence the quantum procedure can outperform classical methods for many common system types. we show this using the example of sparse approximate inverse (spai) preconditioning, which involves the application of matrix inverses for matrices with n=(n).