Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.05541

Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm

Jiaqi Yao, Ding Liu

quant-phcs.CCcs.LGSubmitted Feb 5, 2026• Announced Feb 6, 2026• 0 citations
v1 · Feb 5, 2026v2 · Feb 9, 2026v3 · Aug 20, 2026
arXivHTMLPDF

Abstract

Matrix multiplication is a fundamental classical computing operation whose efficiency becomes a major challenge at scale, especially for machine learning applications. Quantum computing, with its inherent parallelism and exponential storage capacity, offers a potential solution to these limitations. This work presents a quantum kernel-based matrix multiplication algorithm (QKMM) that achieves an asymptotically optimal computational complexity of $ O(N^2 \log_2 N) $, outperforming the classical optimal complexity of $ O(N^{2.371552}) $, where $N$ denotes the matrix dimension. Through noiseless and noisy quantum simulation experiments, we demonstrate that the proposed algorithm not only exhibits superior theoretical efficiency but also shows practical advantages in runtime performance and stability.

Related papers

Universal Matrix Multiplication on Quantum Computer

J. M. Yao, Huang, Tianjian, Cai, Zipeng +1 more

As the most central and computationally intensive component of deep neural networks, the execution efficiency of matrix multiplication directly determines the training and inference performance of models. Harnessing the parallel processing capabilities afforded by quantum superposition and entanglement to reshape matrix multiplication implementations has become a promising entry point for optimising underlying quantum arithmetic logic and improving the operational efficiency of quantum circuits. This paper proposes a universal quantum matrix multiplication (QMM) framework designed to achieve substantial computational acceleration through an optimised quantum arithmetic logic unit. To circumvent the limitations of multi-register and multi-control gates in conventional quantum arithmetic circuits, we encode classical data directly into parameterised \(R_z\) rotation gates using the quantum Fourier transform (QFT), thereby reducing the base gate complexity of the quantum adder to \(O(n)\). In addition, by adopting the column-wise multiplication principle from classical arithmetic, we optimize the gate complexity of the quantum multiplier to \(O(n^2)\). We further extend this approach to a quantum version of the Strassen algorithm, and experimentally quantify the trade-off between reduced multiplication time and increased overhead in addition resources. This work establishes a reliable technical pathway for constructing general-purpose quantum matrix operations, with the potential to unlock substantial computational power for training modern machine learning models.

arXiv:2408.03085•Aug 6, 2024•1 citation

AQ-Stacker: An Adaptive Quantum Matrix Multiplication Algorithm with Scaling via Parallel Hadamard Stacking

Wladimir Silva

Matrix multiplication (MatMul) is the computational backbone of modern machine learning, yet its classical complexity remains a bottleneck for large scale data processing. We propose a hybrid quantum classical algorithm for matrix multiplication based on an adaptive configuration of Hadamard tests. By introducing classical memoization that caches state preparation blocks outside the main compilation loop, we reduce the total classical pre processing overhead for all N^2 element circuits to O(N^2). This decouples the heavy gate synthesis overhead from the core quantum processing loop, enabling execution complexities that strictly match classical input/output boundaries. We introduce an "Adaptive Stacking" framework that allows the algorithm to dynamically reconfigure its execution pattern - from sequential horizontal stacking to massive vertical parallelism - based on available qubit resources. This flexibility enables a tunable time complexity range, theoretically reaching O(N^2) on fault tolerant systems while maintaining compatibility with near term hardware. Our core theoretical contribution is the formalization of the "Entropy Dividend": an information theoretic concentration bound proving that the effective measurement variance sigma^2_eff <= (1/S) (1 - (1/2N) e^[H_max - H(psi)]) approaches its maximum. This makes AQ-Stacker uniquely suited for stabilizing the stochastic weight distributions of deep neural networks. We validate the numerical stability of our approach through Quantum Machine Learning (QML) Statevector simulations, achieving 96% accuracy on the MNIST handwritten digit dataset. Our results suggest that entropic noise suppression and parallel Hadamard stacking provide a scalable path toward super-classical efficiency in next-generation quantum-enhanced AI.

quant-pharXiv:2604.02530•Apr 6, 2026•0 citations

Quantum-Efficient Convolution through Sparse Matrix Encoding and Low-Depth Inner Product Circuits

Mohammad Rasoul Roshanshah, Payman Kazemikhah, Hossein Aghababa

Convolution operations are foundational to classical image processing and modern deep learning architectures, yet their extension into the quantum domain has remained algorithmically and physically costly due to inefficient data encoding and prohibitive circuit complexity. In this work, we present a resource-efficient quantum algorithm that reformulates the convolution product as a structured matrix multiplication via a novel sparse reshaping formalism. Leveraging the observation that localized convolutions can be encoded as doubly block-Toeplitz matrix multiplications, we construct a quantum framework wherein sparse input patches are prepared using optimized key-value QRAM state encoding, while convolutional filters are represented as quantum states in superposition. The convolution outputs are computed through inner product estimation using a low-depth SWAP test circuit, which yields probabilistic amplitude information with reduced sampling overhead. Our architecture supports batched convolution across multiple filters using a generalized SWAP circuit. Compared to prior quantum convolutional approaches, our method eliminates redundant preparation costs, scales logarithmically with input size under sparsity, and enables direct integration into hybrid quantum-classical machine learning pipelines. This work provides a scalable and physically realizable pathway toward quantum-enhanced feature extraction, opening up new possibilities for quantum convolutional neural networks and data-driven quantum inference.

arXiv:2507.19658•Jul 25, 2025•0 citations

Quantum State Superposition-Based Hardware Acceleration of Matrix Multiplication

Jincheng Zhang

This paper explores a novel approach to accelerating matrix multiplication by leveraging the principles of quantum state superposition. Traditional matrix multiplication is computationally intensive, particularly for large matrices, and is a core component of many scientific and engineering applications. We propose a hardware acceleration strategy that maps the matrix multiplication process onto a quantum circuit exploiting the inherent parallelism offered by quantum superposition. The core idea involves representing matrix elements as quantum states and performing the multiplication operations using controlled quantum gates. This approach aims to potentially achieve exponential speedups compared to classical algorithms. We detail the theoretical framework, outlining the quantum circuit design, and discuss the key challenges and potential improvements associated with this methodology. The primary focus is on the algorithmic design and conceptual framework rather than experimental validation, offering a foundational exploration of this concept.

•Aug 31, 2026•0 citations

A Resource Efficient Quantum Kernel

Utkarsh Singh, Jean‐Frédéric Laprade, Aaron Z. Goldberg +1 more

Quantum processors may enhance machine learning by mapping high-dimensional data onto quantum systems for processing. Conventional feature maps, for encoding data onto a quantum circuit are currently impractical, as the number of entangling gates scales quadratically with the dimension of the dataset and the number of qubits. In this work, we introduce a quantum feature map designed to handle high-dimensional data with a significantly reduced number of qubits and entangling operations. Our approach preserves essential data characteristics while promoting computational efficiency, as evidenced by extensive experiments on benchmark datasets that demonstrate a marked improvement in both accuracy and resource utilization when using our feature map as a kernel for characterization, as compared to state-of-the-art quantum feature maps. Our noisy simulation results, combined with lower resource requirements, highlight our map's ability to function within the constraints of noisy intermediate-scale quantum devices. Through numerical simulations and small-scale implementation on a superconducting circuit quantum computing platform, we demonstrate that our scheme performs on par or better than a set of classical algorithms for classification. While quantum kernels are typically stymied by exponential concentration, our approach is affected with a slower rate with respect to both the number of qubits and features, which allows practical applications to remain within reach. Our findings herald a promising avenue for the practical implementation of quantum machine learning algorithms on near future quantum computing platforms.

arXiv:2507.03689•Jul 4, 2025•7 citations

Quantum Linear Algebra for Machine Learning

Hamid D. Ismail

This chapter examines quantum linear algebra as a foundational framework for quantum machine learning. Because many core learning tasks, including regression, dimensionality reduction, kernel evaluation, recommendation systems, and representation learning, depend on linear algebraic operations, this chapter explores how these operations can be reformulated in the quantum setting. Emphasis is placed on the shift from explicit numerical computation to coherent manipulation of quantum states and measurement-based access to information. This chapter introduces quantum inner product estimation as a primitive for similarity and kernel evaluation, highlighting the swap test and related overlap-estimation methods. It then develops quantum matrix inversion and the HHL algorithm, emphasizing the preparation of solution states rather than explicit solution vectors and discussing the importance of conditioning and regularization. Quantum singular value decomposition is presented through Hermitian embeddings, phase estimation, block encoding, and quantum singular value transformation, providing a unified framework for spectral filtering and low-rank approximation. This chapter concludes with quantum principal component analysis, in which covariance structure is represented by a density matrix and accessed through quantum phase estimation and density matrix exponentiation. Throughout, practical demonstrations in Qiskit and PennyLane illustrate the algorithms, while careful attention is given to the limitations imposed by state preparation, measurement, noise, and classical data loading.

CRC Press eBooks•Nov 4, 2026•0 citations
Reducing the Complexity of Matrix Multiplication to O(N2log2N)O(N^2log_2N)O(N2log2​N) by an Asymptotically Optimal Quantum Algorithm
Matrix multiplication is a fundamental classical computing operation whose efficiency becomes a major challenge at scale, especially for machine learning applications. Quantum computing, with its inherent parallelism and exponential storage capacity, offers a potential solution to these limitations. This work presents a quantum kernel-based matrix multiplication algorithm (QKMM) that achieves an asymptotically optimal computational complexity of O(N2log⁡2N)O(N^2 \log_2 N)O(N2log2​N), outperforming the classical optimal complexity of O(N2.371552)O(N^{2.371552})O(N2.371552), where NNN denotes the matrix dimension. Through noiseless and noisy quantum simulation experiments, we demonstrate that the proposed algorithm not only exhibits superior theoretical efficiency but also shows practical advantages in runtime performance and stability.
As the most central and computationally intensive component of deep neural networks, the execution efficiency of matrix multiplication directly determines the training and inference performance of models. Harnessing the parallel processing capabilities afforded by quantum superposition and entanglement to reshape matrix multiplication implementations has become a promising entry point for optimising underlying quantum arithmetic logic and improving the operational efficiency of quantum circuits. This paper proposes a universal quantum matrix multiplication (QMM) framework designed to achieve substantial computational acceleration through an optimised quantum arithmetic logic unit. To circumvent the limitations of multi-register and multi-control gates in conventional quantum arithmetic circuits, we encode classical data directly into parameterised RzR_zRz​ rotation gates using the quantum Fourier transform (QFT), thereby reducing the base gate complexity of the quantum adder to O(n)O(n)O(n). In addition, by adopting the column-wise multiplication principle from classical arithmetic, we optimize the gate complexity of the quantum multiplier to O(n2)O(n^2)O(n2). We further extend this approach to a quantum version of the Strassen algorithm, and experimentally quantify the trade-off between reduced multiplication time and increased overhead in addition resources. This work establishes a reliable technical pathway for constructing general-purpose quantum matrix operations, with the potential to unlock substantial computational power for training modern machine learning models.
Matrix multiplication (MatMul) is the computational backbone of modern machine learning, yet its classical complexity remains a bottleneck for large scale data processing. We propose a hybrid quantum classical algorithm for matrix multiplication based on an adaptive configuration of Hadamard tests. By introducing classical memoization that caches state preparation blocks outside the main compilation loop, we reduce the total classical pre processing overhead for all N^2 element circuits to O(N^2). This decouples the heavy gate synthesis overhead from the core quantum processing loop, enabling execution complexities that strictly match classical input/output boundaries. We introduce an "Adaptive Stacking" framework that allows the algorithm to dynamically reconfigure its execution pattern - from sequential horizontal stacking to massive vertical parallelism - based on available qubit resources. This flexibility enables a tunable time complexity range, theoretically reaching O(N^2) on fault tolerant systems while maintaining compatibility with near term hardware. Our core theoretical contribution is the formalization of the "Entropy Dividend": an information theoretic concentration bound proving that the effective measurement variance sigma^2_eff <= (1/S) (1 - (1/2N) e^[H_max - H(psi)]) approaches its maximum. This makes AQ-Stacker uniquely suited for stabilizing the stochastic weight distributions of deep neural networks. We validate the numerical stability of our approach through Quantum Machine Learning (QML) Statevector simulations, achieving 96% accuracy on the MNIST handwritten digit dataset. Our results suggest that entropic noise suppression and parallel Hadamard stacking provide a scalable path toward super-classical efficiency in next-generation quantum-enhanced AI.
Convolution operations are foundational to classical image processing and modern deep learning architectures, yet their extension into the quantum domain has remained algorithmically and physically costly due to inefficient data encoding and prohibitive circuit complexity. In this work, we present a resource-efficient quantum algorithm that reformulates the convolution product as a structured matrix multiplication via a novel sparse reshaping formalism. Leveraging the observation that localized convolutions can be encoded as doubly block-Toeplitz matrix multiplications, we construct a quantum framework wherein sparse input patches are prepared using optimized key-value QRAM state encoding, while convolutional filters are represented as quantum states in superposition. The convolution outputs are computed through inner product estimation using a low-depth SWAP test circuit, which yields probabilistic amplitude information with reduced sampling overhead. Our architecture supports batched convolution across multiple filters using a generalized SWAP circuit. Compared to prior quantum convolutional approaches, our method eliminates redundant preparation costs, scales logarithmically with input size under sparsity, and enables direct integration into hybrid quantum-classical machine learning pipelines. This work provides a scalable and physically realizable pathway toward quantum-enhanced feature extraction, opening up new possibilities for quantum convolutional neural networks and data-driven quantum inference.
This paper explores a novel approach to accelerating matrix multiplication by leveraging the principles of quantum state superposition. Traditional matrix multiplication is computationally intensive, particularly for large matrices, and is a core component of many scientific and engineering applications. We propose a hardware acceleration strategy that maps the matrix multiplication process onto a quantum circuit exploiting the inherent parallelism offered by quantum superposition. The core idea involves representing matrix elements as quantum states and performing the multiplication operations using controlled quantum gates. This approach aims to potentially achieve exponential speedups compared to classical algorithms. We detail the theoretical framework, outlining the quantum circuit design, and discuss the key challenges and potential improvements associated with this methodology. The primary focus is on the algorithmic design and conceptual framework rather than experimental validation, offering a foundational exploration of this concept.
Quantum processors may enhance machine learning by mapping high-dimensional data onto quantum systems for processing. Conventional feature maps, for encoding data onto a quantum circuit are currently impractical, as the number of entangling gates scales quadratically with the dimension of the dataset and the number of qubits. In this work, we introduce a quantum feature map designed to handle high-dimensional data with a significantly reduced number of qubits and entangling operations. Our approach preserves essential data characteristics while promoting computational efficiency, as evidenced by extensive experiments on benchmark datasets that demonstrate a marked improvement in both accuracy and resource utilization when using our feature map as a kernel for characterization, as compared to state-of-the-art quantum feature maps. Our noisy simulation results, combined with lower resource requirements, highlight our map's ability to function within the constraints of noisy intermediate-scale quantum devices. Through numerical simulations and small-scale implementation on a superconducting circuit quantum computing platform, we demonstrate that our scheme performs on par or better than a set of classical algorithms for classification. While quantum kernels are typically stymied by exponential concentration, our approach is affected with a slower rate with respect to both the number of qubits and features, which allows practical applications to remain within reach. Our findings herald a promising avenue for the practical implementation of quantum machine learning algorithms on near future quantum computing platforms.
This chapter examines quantum linear algebra as a foundational framework for quantum machine learning. Because many core learning tasks, including regression, dimensionality reduction, kernel evaluation, recommendation systems, and representation learning, depend on linear algebraic operations, this chapter explores how these operations can be reformulated in the quantum setting. Emphasis is placed on the shift from explicit numerical computation to coherent manipulation of quantum states and measurement-based access to information. This chapter introduces quantum inner product estimation as a primitive for similarity and kernel evaluation, highlighting the swap test and related overlap-estimation methods. It then develops quantum matrix inversion and the HHL algorithm, emphasizing the preparation of solution states rather than explicit solution vectors and discussing the importance of conditioning and regularization. Quantum singular value decomposition is presented through Hermitian embeddings, phase estimation, block encoding, and quantum singular value transformation, providing a unified framework for spectral filtering and low-rank approximation. This chapter concludes with quantum principal component analysis, in which covariance structure is represented by a density matrix and accessed through quantum phase estimation and density matrix exponentiation. Throughout, practical demonstrations in Qiskit and PennyLane illustrate the algorithms, while careful attention is given to the limitations imposed by state preparation, measurement, noise, and classical data loading.