Faster quantum subroutine for matrix chain multiplication via Chebyshev approximation

Area of Science:

• Quantum Computing
• Computational Mathematics
• Linear Algebra

Background:

• Matrix operations are fundamental to numerous computational tasks across diverse scientific and engineering disciplines.
• Quantum computing presents a powerful paradigm for accelerating computationally intensive algorithms, including matrix operations.

Purpose of the Study:

• To introduce a novel quantum matrix multiplication (QMM) algorithm designed for efficient matrix chain multiplication.
• To achieve quadratic acceleration for scenarios involving repeated application of the same matrix (K times).

Main Methods:

• The algorithm utilizes amplitude encoding to represent quantum states.
• It combines quantum walks with Chebyshev polynomial approximation for computational efficiency.
• The approach is designed to maintain logarithmic complexity concerning matrix dimension and precision.

Main Results:

• The proposed QMM algorithm demonstrates quadratic acceleration for matrix chain multiplication with repeated matrix applications.
• The algorithm is applicable to any complex matrix.
• Numerical simulations suggest optimization strategies for matrices with large condition numbers.

Conclusions:

• The developed QMM algorithm offers a significant speedup for a critical class of matrix operations.
• The algorithm's integration into broader matrix operations and optimization for challenging matrices are discussed, paving the way for practical quantum advantage.