The field of quantum computing offers a unique opportunity to revolutionize numerical linear algebra and scientific computing. This is due to the capability of quantum computers to efficiently model complex structures, and their ability to represent and act on high dimensional vectors and matrices using exponentially fewer qubits. These advantages arise due to the principles of superposition and entanglement inherent to qubits.

However, the current landscape of quantum computing research emphasizes intricate, tailor-made circuit designs, created in an adhoc manner for specific mathematical challenges. While such state-of-the-art quantum algorithms offer a powerful approach by translating various computations into circuits, their development not straightforward. Development often requires significant “circuit engineering” to achieve the desired mathematical outcomes. In this talk, I will discuss our recent progress on developing a unified and systemic approach to utilizing quantum computing for numerical linear algebra. Our research centers around a novel Quantum Linear Algebra (qLA) framework offering fundamental matrix algebra building blocks, akin to BLAS – but for Quantum Computers.

The motivation is to make progress toward harnessing the power of quantum computing to perform linear algebra operations efficiently, while enabling seamless development of numerical linear algebra algorithms utilizing quantum computers. Even though quantum computing offers, in principle, the potential for exponential improvements in runtime and storage complexity, for linear algebra operations even modest gains are valuable and seemingly much more realistic. Indeed, even seemingly minor efficiency improvements, such as reducing from \(O(n^{3})\) to \(O(n^{2})\) the complexity of core operations like matrix-matrix product, can have significant real-world impact. This makes quantum numerical linear algebra a highly promising area for exploration. Developing a high-level framework for quantum linear algebra algorithms is key to unlocking qNLA’s potential in scientific computing and machine learning. Such a framework would empower developers by hiding low-level circuit complexities, ultimately accelerating progress in this exciting field.

The qLA framework is designed to provide a high-level interface for writing and executing linear algebra subroutines by translating mathematical formulas directly into quantum circuits. While qLA-based algorithms are classical to classical, they will produce circuits specifically intended for efficient execution on quantum computers. The framework enables a wide range input models, a broad range of matrix algebra operations, and facilitate seamless circuit design. Beyond its core functionalities, the framework is developed so that it can be leveraged to design quantum algorithms for scientific computing and machine learning problems, particularly those problems involving computationally intensive linear algebra operations. The talk will discuss both the algorithms and functionalities within the qLA framework, and how they can be leveraged to design novel quantum algorithms.

An initial version of the qLA framework, called quantum Matrix States Linear Algebra (qMSLA), is described in our accepted manuscript [1]. qMSLA focuses on a single input model: state preparation circuits (the term will be explained in the talk), and provides a minimal set of linear algebra operations that can be used to design quantum algorithm for estimating multivariate traces, i.e. the trace of products of matrices. In the talk, I will discuss our recent work on expanding this framework with additional input models (block encoding and density preparation circuits), a comprehensive list of foundational matrix algebra operations, and the relation between input models.

References

• [1]  Liron Mor Yosef, Shashanka Ubaru, Lior Horesh, Haim Avron Multivariate Trace Estimation Using Quantum State Space Linear Algebra SIAM Journal on Matrix Analysis and Applications, to appear.