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

Matrix chain multiplication—computing the product of K distinct matrices—is a fundamental operation in scientific computing and machine learning. Classically, this task requires O(K N^omega) operations. While quantum algorithms offer potential speedups, existing approaches for matrix chains typically suffer from circuit depth that scales with the chain length K, or they require significant ancilla overhead. This paper addresses the challenge of computing these products efficiently in a quantum setting, specifically aiming to decouple circuit depth from the chain length.

The authors introduce the Two-Tower Matrix Multiplication subroutine. The core innovation is a two-layer circuit architecture that interleaves state-preparation operators. By mapping the matrix chain product to a series of contractions between adjacent matrices, the algorithm uses a 'two-tower' structure where even-indexed matrices are processed in one layer and odd-indexed matrices in another. This parallelization allows the circuit to execute in depth that depends only on the dimensions of the individual matrices, not the number of matrices in the chain. The construction relies on the QRAM-based state-preparation model to load matrix entries into quantum states efficiently.

The Two-Tower algorithm successfully encodes the product of K matrices into a quantum state with a circuit depth of O(max_k polylog(P_k P_{k+1})). This is a significant improvement over prior methods where depth scaled with K. The authors provide a formal correctness proof for arbitrary K and demonstrate the algorithm's utility for downstream tasks such as norm estimation, graph-matrix powers, and quantum machine learning kernels. The method is also specialized for the chain-vector case and validated through implementations in Qiskit and QCLAB.

This subroutine provides a scalable way to handle long matrix chains in quantum algorithms. By trading qubit count for circuit depth, it enables the use of matrix chain products in quantum circuits that would otherwise be too deep to execute on near-term or fault-tolerant hardware. It effectively removes the chain length as a bottleneck for circuit depth, making it a versatile tool for any quantum algorithm requiring the manipulation of matrix products.