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

Abstract

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 leveraging Quantum Random Access Memory (QRAM) for state preparation, we demonstrate that the complexity of computing the inner product of two vectors can be reduced to $O(\log N)$. 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. We validate the numerical stability of our approach through a Quantum Machine Learning (QML) simulation, achieving 96% accuracy on the MNIST handwritten digit dataset. Our results suggest that adaptive quantum MatMul provides a viable path toward super-classical efficiency in high-dimensional linear algebra operations.