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:2607.13191

Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth

Giacomo Antonioli, Anna Bernasconi, Alessandro Berti, Gianna M. Del Corso, Alessandro Poggiali

quant-phSubmitted Jul 14, 2026• Announced Jul 16, 2026• 0 citations
arXivHTMLPDF

Abstract

Matrix chain multiplication -- computing $\mathcal{W} = M^{(0)}\cdots M^{(K-1)}$ where $M^{(k)} \in \mathbb{R}^{P_k \times P_{k+1}}$ -- arises in scientific computing, machine learning, and graph analysis. Despite the importance of this problem, for chains of distinct matrices, the classical number of operations grows linearly with the chain length $K$ and polynomially in the matrix dimensions. We present \emph{Two-Tower Matrix Multiplication}, a quantum subroutine that encodes the product $\mathcal{W}$ of the $K$ matrices into a quantum state in circuit depth $\mathcal{O}(\max_{k} \mathrm{polylog} (P_k P_{k+1}))$, which is independent of~$K$ within the QRAM-based state-preparation model, whereas the qubit count is $\mathcal{O}\bigl(\sum_{k} \log P_k \bigr)$; the total gate count remains linear in $K$, so the gain is in the circuit depth. The construction interleaves state-preparation operators across two layers; within each layer, all operators act on disjoint registers and execute in parallel. This subroutine can be specialized for the chain-vector case, which computes the product of $K-1$ matrices applied to a vector. We prove the correctness of the subroutine for all $K$ and provide two implementations using the Qiskit and QCLAB frameworks. The subroutine is applicable to any downstream quantum algorithm that operates on a matrix encoded in the statevector, including norm estimation, graph-matrix powers, linear system solving, and quantum machine learning kernels.

Related papers

Quantum Subroutine for Efficient Matrix Multiplication

Anna Bernasconi, Alessandro Berti, Gianna M. Del Corso +1 more

We propose an efficient quantum subroutine for matrix multiplication that computes a state vector encoding the entries of the product of two matrices in superposition. The subroutine exploits efficient state preparation techniques and shows a potential speed-up with respect to classical methods. The most important benefit of our subroutine is that it encodes the entries of the matrix product directly in the state vector, which can be used for further computations within the same quantum circuit. All scenarios involving the computation of non-homomorphic functions of the product of two matrices can benefit from our technique. As a possible application, we discuss the computation of the variance of the entries of a matrix product, which can be a useful tool for some machine learning algorithms.

IEEE Access•Jan 1, 2024•9 citations

Reducing the Complexity of Matrix Multiplication by Quantum Computing

Jiaqi Yao, Tianjian Huang, Tonghe Zhang +1 more

Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of \(O(N^2\log_2N)\), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm \(O(N^{2.371339})\). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V${\scriptstyle 2}$V), Quantum Vector-Matrix Multiplication (V${\scriptstyle 2}$M), QKMM (M${\scriptstyle 2}$M), Quantum One-to-Many Matrix Multiplication(O${\scriptstyle 2}$M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.

quant-pharXiv:2602.05541•Feb 6, 2026•0 citations

Advancing Quantum Matrix Computations: Integrating Geometric Means and Chain Multiplications for Nonlinear and Iterative Challenges in Machine Learning and Quantum Information

Syed Muntasir Mamun

Quantum computing has emerged as a transformative paradigm for tackling complex matrix operations that underpin applications in machine learning and quantum information. In this paper, we synthesize recent advancements in quantum computing by integrating the quantum subroutines for matrix geometric means from Liu et al. (2025), which enable efficient solutions to nonlinear matrix equations like algebraic Riccati equations, with the Chebyshev-accelerated quantum matrix multiplication framework from Li et al. (2025), offering quadratic speedups for iterative chain operations on complex matrices. Through detailed reviews of each approach, we highlight shared primitives such as block-encoding, quantum singular value transformation, Hermitianization, and polynomial approximations, demonstrating their complementarity in constructing hybrid algorithms for nonlinear iterative problems. These hybrids achieve polylogarithmic complexities in matrix dimensions while optimizing precision and conditioning dependencies, exemplified in frameworks for Riccati iterations and kernel enhancements. Applications are explored in machine learning, including geometric mean metric learning for anomaly detection in classical and quantum data, and in quantum information, such as optimal fidelity and Rényi entropy estimation with accelerated power computations for error correction. Also available on Academia.edu: https://www.academia.edu/attachments/125700844/download_file?s=portfolio

•Dec 11, 2025•0 citations

Quantum Linear System Algorithm for Dense Matrices

Leonard Wossnig, Zhikuan Zhao, Anupam Prakash

Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix $A$ and a vector $\mathbf{b}$ the task is to find the vector $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional $A$ with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of $A$, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of $A$ is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of $A$ and the vector of Euclidean norms of the rows of $A$.

arXiv:1704.06174•Physical Review Letters•Jan 31, 2018•222 citations

Exact log-depth preparation of highly entangled matrix product states

Keisuke Murota, Frédéric Sauvage, Marco Ballarin +2 more

Preparing matrix product states (MPS) on a quantum device is a key subroutine in many quantum algorithms. The most competitive methods, based on the renormalisation group, prepare translationally invariant MPS of size $L$ and bond dimension $χ$, up to an error $\varepsilon$, in circuit depth $\tilde O(χ^{4}\log(L/\varepsilon))$ or $\tilde O(χ^{6}\log\log(L/\varepsilon))$. We improve multiple aspects of these methods. First, using block-encoded correction maps, whose post-selection succeeds with constant probability, we render the preparation exact without sacrificing the scaling in $L$. Second, through a generalisation of oblivious amplitude amplification to isometries, we reduce the bond-dimension dependence, improving the depth to $\tilde O(χ^{2}\log L + χ^{4})$ or $\tilde O(χ^{2}\log\log L + χ^{4})$, and even to $\tilde O(χ^{3}\log L)$ for incoherent preparations. Finally, we extend the framework to non-translationally invariant MPS and prove logarithmic-depth exact preparation for independent and identically distributed random tensor sequences. Confirmed by numerical studies, these results constitute, to the best of our knowledge, the most efficient exact MPS preparation protocols in the relevant parameter regimes.

quant-pharXiv:2606.24475•Jun 24, 2026•0 citations

Quantum machine learning with subspace states

Iordanis Kerenidis, Anupam Prakash

We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$. The state of art classical algorithm for the task requires $O(d^{3})$ operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices $\mathcal{A}^{k}$, the speedup for this algorithm is potentially exponential. It decomposes a $\binom{n}{k}$ dimensional vector of order-$k$ correlations into a linear combination of subspace states corresponding to $k$-tuples of singular vectors of $A$. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$. Our basic tool are quantum subspace states, defined as $|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in \mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$, that encode $d$-dimensional subspaces of $\mathbb{R}^{n}$. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries $Γ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}$ with $O(\log n)$ depth circuits that we term Clifford loaders.

arXiv:2202.00054•Jan 31, 2022•10 citations
Matrix chain multiplication -- computing W=M(0)⋯M(K−1)\mathcal{W} = M^{(0)}\cdots M^{(K-1)}W=M(0)⋯M(K−1) where M(k)∈RPk×Pk+1M^{(k)} \in \mathbb{R}^{P_k \times P_{k+1}}M(k)∈RPk​×Pk+1​ -- arises in scientific computing, machine learning, and graph analysis. Despite the importance of this problem, for chains of distinct matrices, the classical number of operations grows linearly with the chain length KKK and polynomially in the matrix dimensions. We present \emph{Two-Tower Matrix Multiplication}, a quantum subroutine that encodes the product W\mathcal{W}W of the KKK matrices into a quantum state in circuit depth O(max⁡kpolylog(PkPk+1))\mathcal{O}(\max_{k} \mathrm{polylog} (P_k P_{k+1}))O(maxk​polylog(Pk​Pk+1​)), which is independent of~KKK within the QRAM-based state-preparation model, whereas the qubit count is O(∑klog⁡Pk)\mathcal{O}\bigl(\sum_{k} \log P_k \bigr)O(∑k​logPk​); the total gate count remains linear in KKK, so the gain is in the circuit depth. The construction interleaves state-preparation operators across two layers; within each layer, all operators act on disjoint registers and execute in parallel. This subroutine can be specialized for the chain-vector case, which computes the product of K−1K-1K−1 matrices applied to a vector. We prove the correctness of the subroutine for all KKK and provide two implementations using the Qiskit and QCLAB frameworks. The subroutine is applicable to any downstream quantum algorithm that operates on a matrix encoded in the statevector, including norm estimation, graph-matrix powers, linear system solving, and quantum machine learning kernels.
We propose an efficient quantum subroutine for matrix multiplication that computes a state vector encoding the entries of the product of two matrices in superposition. The subroutine exploits efficient state preparation techniques and shows a potential speed-up with respect to classical methods. The most important benefit of our subroutine is that it encodes the entries of the matrix product directly in the state vector, which can be used for further computations within the same quantum circuit. All scenarios involving the computation of non-homomorphic functions of the product of two matrices can benefit from our technique. As a possible application, we discuss the computation of the variance of the entries of a matrix product, which can be a useful tool for some machine learning algorithms.
Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of O(N2log⁡2N)O(N^2\log_2N)O(N2log2​N), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm O(N2.371339)O(N^{2.371339})O(N2.371339). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V2{\scriptstyle 2}2V), Quantum Vector-Matrix Multiplication (V2{\scriptstyle 2}2M), QKMM (M2{\scriptstyle 2}2M), Quantum One-to-Many Matrix Multiplication(O2{\scriptstyle 2}2M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.
Quantum computing has emerged as a transformative paradigm for tackling complex matrix operations that underpin applications in machine learning and quantum information. In this paper, we synthesize recent advancements in quantum computing by integrating the quantum subroutines for matrix geometric means from Liu et al. (2025), which enable efficient solutions to nonlinear matrix equations like algebraic Riccati equations, with the Chebyshev-accelerated quantum matrix multiplication framework from Li et al. (2025), offering quadratic speedups for iterative chain operations on complex matrices. Through detailed reviews of each approach, we highlight shared primitives such as block-encoding, quantum singular value transformation, Hermitianization, and polynomial approximations, demonstrating their complementarity in constructing hybrid algorithms for nonlinear iterative problems. These hybrids achieve polylogarithmic complexities in matrix dimensions while optimizing precision and conditioning dependencies, exemplified in frameworks for Riccati iterations and kernel enhancements. Applications are explored in machine learning, including geometric mean metric learning for anomaly detection in classical and quantum data, and in quantum information, such as optimal fidelity and Rényi entropy estimation with accelerated power computations for error correction. Also available on Academia.edu: https://www.academia.edu/attachments/125700844/download_file?s=portfolio
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix AAA and a vector b\mathbf{b}b the task is to find the vector x\mathbf{x}x such that Ax=bA\mathbf{x}=\mathbf{b}Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional AAA with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of AAA, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of AAA is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of AAA and the vector of Euclidean norms of the rows of AAA.
Preparing matrix product states (MPS) on a quantum device is a key subroutine in many quantum algorithms. The most competitive methods, based on the renormalisation group, prepare translationally invariant MPS of size LLL and bond dimension χχχ, up to an error ε\varepsilonε, in circuit depth O~(χ4log⁡(L/ε))\tilde O(χ^{4}\log(L/\varepsilon))O~(χ4log(L/ε)) or O~(χ6log⁡log⁡(L/ε))\tilde O(χ^{6}\log\log(L/\varepsilon))O~(χ6loglog(L/ε)). We improve multiple aspects of these methods. First, using block-encoded correction maps, whose post-selection succeeds with constant probability, we render the preparation exact without sacrificing the scaling in LLL. Second, through a generalisation of oblivious amplitude amplification to isometries, we reduce the bond-dimension dependence, improving the depth to O~(χ2log⁡L+χ4)\tilde O(χ^{2}\log L + χ^{4})O~(χ2logL+χ4) or O~(χ2log⁡log⁡L+χ4)\tilde O(χ^{2}\log\log L + χ^{4})O~(χ2loglogL+χ4), and even to O~(χ3log⁡L)\tilde O(χ^{3}\log L)O~(χ3logL) for incoherent preparations. Finally, we extend the framework to non-translationally invariant MPS and prove logarithmic-depth exact preparation for independent and identically distributed random tensor sequences. Confirmed by numerical studies, these results constitute, to the best of our knowledge, the most efficient exact MPS preparation protocols in the relevant parameter regimes.
We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution Pr⁡[S]=det(XSXST)\Pr[S]= det(X_{S}X_{S}^{T})Pr[S]=det(XS​XST​) for ∣S∣=d|S|=d∣S∣=d using O(nd)O(nd)O(nd) gates and with circuit depth O(dlog⁡n)O(d\log n)O(dlogn). The state of art classical algorithm for the task requires O(d3)O(d^{3})O(d3) operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices Ak\mathcal{A}^{k}Ak, the speedup for this algorithm is potentially exponential. It decomposes a (nk)\binom{n}{k}(kn​) dimensional vector of order-kkk correlations into a linear combination of subspace states corresponding to kkk-tuples of singular vectors of AAA. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from O(n)O(n)O(n) to O(log⁡n)O(\log n)O(logn). Our basic tool are quantum subspace states, defined as ∣Col(X)⟩=∑S⊂[n],∣S∣=ddet(XS)∣S⟩|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle∣Col(X)⟩=∑S⊂[n],∣S∣=d​det(XS​)∣S⟩ for matrices X∈Rn×dX \in \mathbb{R}^{n \times d}X∈Rn×d such that XTX=IdX^{T} X = I_{d}XTX=Id​, that encode ddd-dimensional subspaces of Rn\mathbb{R}^{n}Rn. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries Γ(x)=∑ixiZ⊗(i−1)⊗X⊗In−iΓ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}Γ(x)=∑i​xi​Z⊗(i−1)⊗X⊗In−i with O(log⁡n)O(\log n)O(logn) depth circuits that we term Clifford loaders.