⚛️ quantum physics

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

This paper introduces "Two-Tower Matrix Multiplication," a quantum subroutine that encodes the product of a chain of $K$ matrices into a quantum state with circuit depth independent of $K$ (achieving polylogarithmic depth in matrix dimensions) by trading increased qubit requirements for parallel execution across two interleaved layers.

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

Published 2026-07-16

📖 8 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers don't just crunch numbers one by one, but dance with probabilities, exploring many paths at once. This is the realm of quantum computing, a field that promises to solve problems too massive for today's supercomputers. At the heart of many scientific challenges—from predicting how a virus spreads to training artificial intelligence—is a task called matrix chain multiplication. Think of matrices as giant, multi-dimensional spreadsheets of numbers. When you multiply them together in a long line (a "chain"), you are essentially performing a complex transformation on data. In the classical world, doing this gets slower and slower the longer the chain gets, like trying to cross a river by stepping on every single stone in a long, winding path. The goal for scientists has always been to find a way to "teleport" across that river, getting the result instantly regardless of how many stones are in the water.

This paper introduces a clever new quantum trick called Two-Tower Matrix Multiplication. It's a method designed to compute the product of a long chain of different matrices much faster than before, specifically by making the "depth" of the calculation (the time it takes) stay short, even as the chain gets longer. The authors, researchers from the University of Pisa, have proven that their method works for any length of chain and have built working versions of it using real quantum software tools. While it doesn't solve every problem (it still needs a lot of "memory" in the form of quantum bits), it offers a fascinating trade-off: you use more quantum memory to save a massive amount of time.

The Problem: The Long Line of Spreadsheets

Imagine you are a chef trying to make a giant, multi-layered sandwich. You have a stack of ingredients: a slice of bread, a slice of cheese, a slice of ham, a slice of bread, and so on. To get the final taste of the sandwich, you have to combine them all in order. In the world of math, these ingredients are matrices, and combining them is multiplication.

If you have a short chain of matrices, a normal computer can handle it easily. But if you have a long chain—say, 100 matrices—the computer has to do the math step-by-step. It's like walking through a long hallway, opening one door, then the next, then the next. The longer the hallway, the longer it takes. In the classical world, the time it takes grows linearly with the number of matrices. If you double the chain, you double the time.

Quantum computers are different. They use qubits, which can be in many states at once (a concept called superposition). This allows them to explore many possibilities simultaneously. However, building a quantum algorithm to multiply a long chain of matrices has been tricky. Previous methods were like trying to build a bridge across that long hallway: they either took too long to build (deep circuits) or required too many materials (too many qubits).

The Solution: The Two-Tower Trick

The authors of this paper propose a new way to build the bridge, which they call the Two-Tower method. To understand it, let's use an analogy of a conveyor belt factory.

Imagine you have a long line of workers (the matrices) who need to pass a package down the line.

The Old Way: In previous quantum methods, you might have to stop the line, reorganize the workers, and pass the package one by one. If there are 100 workers, the package takes 100 steps to get to the end.
The Two-Tower Way: The authors realized they could split the workers into two groups: the "Left" team and the "Right" team.
- The Left Team (matrices at positions 0, 2, 4...) all grab their part of the package and work at the exact same time.
- The Right Team (matrices at positions 1, 3, 5...) also work at the exact same time, but they do something special: they act like a "sieve" or a "filter."

Here is the magic part: The Right Team uses a special quantum move (called an adjoint state preparation) that acts like a magic filter. It checks if the pieces of the package match up correctly. If they do, the pieces combine and pass through. If they don't match, they vanish into a "ghost" state that doesn't count. Because all the Right Team members work in parallel, the whole chain gets processed in just two big steps, no matter how long the line is!

This is why they call it "Two-Tower." The circuit looks like two towers of operations rising up, where one tower handles the even-numbered matrices and the other handles the odd-numbered ones. They meet in the middle, and the result pops out.

What They Found and Proved

The paper makes several specific claims, backed by mathematical proofs and computer simulations:

Speed is Independent of Length: The most exciting finding is that the time (circuit depth) it takes to run this algorithm does not grow with the number of matrices ( $K$ ). Whether you have 2 matrices or 200, the "depth" of the calculation stays roughly the same, scaling only with the size of the individual matrices (specifically, logarithmic of their dimensions). This is a huge improvement over previous methods where the time grew with the chain length.
The Trade-Off: There is a catch. To get this speed, you need more qubits (quantum memory). The number of qubits grows linearly with the chain length ( $K$ ). The authors describe this as "trading qubits for depth." You use more memory to save time.
It Works for Any Chain: The authors provided a rigorous mathematical proof showing that this method works for any length of chain, whether the number of matrices is odd or even. They even handled the tricky case where the last item in the chain is just a single vector (a column of numbers) rather than a full matrix.
Real-World Testing: They didn't just do the math on paper. They built the algorithm using two popular quantum software frameworks, Qiskit and QCLAB, and ran simulations. These simulations confirmed that the algorithm correctly produces the expected results for various test cases.

The "Signal" Problem

There is one subtle detail the paper discusses: the "signal weight." In quantum mechanics, when you run an algorithm, you often get a mix of the "correct" answer and some "noise" or "ghost" answers. The "signal weight" is a measure of how much of the final result is the correct answer versus the noise.

The authors found that for very long chains of "well-behaved" matrices (where the numbers are all roughly the same size), the signal weight can get very small. It's like trying to hear a whisper in a noisy room; the correct answer is there, but it's faint. However, they note that there is a known quantum technique called Amplitude Amplification that can boost this signal, making the correct answer louder, though this requires repeating the process a few times. For matrices with a "peaked" structure (where one number dominates), the signal stays strong naturally.

Why This Matters

This paper doesn't claim to have solved every problem in the universe. It doesn't say this method will instantly cure diseases or build a time machine. Instead, it offers a powerful new tool for scientists who need to perform long chains of matrix multiplications.

This is useful for:

Graph Analysis: Understanding how information flows through massive networks (like social media or the internet).
Machine Learning: Speeding up the training of complex AI models.
Solving Equations: Helping to solve systems of linear equations that are too big for classical computers.

The authors are careful to state that this is a subroutine—a building block. It's a specialized tool designed to be plugged into larger quantum algorithms. While the method requires a lot of qubits (which are currently scarce and hard to build), the fact that it can perform these calculations in a time that doesn't grow with the chain length is a significant theoretical and practical step forward.

In short, the Two-Tower method is like discovering a secret elevator in a skyscraper. You still need to carry your luggage (the qubits), but instead of climbing every single flight of stairs (the time), you can zip straight to the top, no matter how tall the building is. It's a clever, proven, and tested way to make quantum computers faster at one of their most important jobs.

Technical Summary: Two-Tower Quantum Matrix Chain Multiplication

Problem Statement
Matrix chain multiplication, defined as computing $W = M^{(0)} \cdots M^{(K-1)}$ where $M^{(k)} \in \mathbb{R}^{P_k \times P_{k+1}}$ , is a fundamental operation in scientific computing, machine learning, and graph analysis. Classically, computing the product of $K$ distinct matrices requires $O(KN^\omega)$ arithmetic operations (where $\omega < 2.372$ ), and even with unbounded parallelism, the circuit depth grows as $O(\log K \cdot \log N)$ .

In the quantum domain, existing linear algebra subroutines typically rely on block-encoding, where the matrix is embedded as a sub-block of a unitary. For chains of distinct matrices, block-encoding approaches generally suffer from a circuit depth that scales linearly with $K$ ( $O(K \cdot \text{polylog}(N))$ ) and an ancilla qubit count that also grows with $K$ . Furthermore, the overall subnormalization factor in block-encoding approaches is the product of individual factors ( $\prod \alpha_k$ ), which can lead to exponentially small success probabilities as $K$ increases. While Quantum Singular Value Transformation (QSVT) offers speedups for powers of a single matrix ( $A^K$ ), no analogous depth-independent speedup is known for chains of distinct matrices using current methods.

Methodology: The Two-Tower Construction
The authors propose "Two-Tower Matrix Multiplication," a quantum subroutine that encodes the product $W$ into the amplitudes of a quantum state. The construction relies on two primary insights:

State Preparation as Vectorization: Encoding matrix entries as amplitudes is equivalent to row-wise vectorization.
Kronecker Product Identity: The vectorization of a product $AXB$ satisfies $\text{vec}(AXB) = (B^T \otimes A)\text{vec}(X)$ .

The algorithm generalizes a two-matrix product subroutine (from Bernasconi et al. [15]) to arbitrary chain lengths $K$ by interleaving state-preparation operators across two parallel layers, avoiding register swaps and sequential dependencies.

Register Allocation: The circuit uses $K+1$ registers. For a chain of matrices $M^{(0)}, \dots, M^{(K-1)}$ , registers are allocated to hold row and column indices. Adjacent matrices share registers, meaning the total qubit count is $\Theta(\sum_{k=0}^K \log P_k)$ .
The Two Layers:
- Layer 1 (OP(L)): Applies the state-preparation operator $SP(M^{(k)})$ to all even-indexed matrices ( $M^{(0)}, M^{(2)}, \dots$ ). These operators act on disjoint register pairs and execute in parallel.
- Layer 2 (OP(R)): Applies the adjoint operator $SP(M^{(k)})^\dagger$ to all odd-indexed matrices ( $M^{(1)}, M^{(3)}, \dots$ ). These operators also act on disjoint pairs (specifically the shared boundaries between even-indexed registers) and execute in parallel.
- Special Case for Even $K$ : If $K$ is even, the final matrix $M^{(K-1)}$ has no right neighbor. Instead of $SP^\dagger$ , the algorithm uses a Modular State-Preparation (MSP) operator. This operator contracts the shared index to $|0\rangle$ while preserving the output column register, which would otherwise be lost.
Contraction Mechanism: The core mechanism relies on the property that $SP(M)^\dagger |i, j\rangle$ projects the state onto $|0, 0\rangle$ with an amplitude proportional to the matrix entry $m_{i,j}$ . By applying $SP$ to one matrix and $SP^\dagger$ to its neighbor on shared registers, the circuit simultaneously sums over all shared indices (inner products) via quantum superposition, effectively performing the matrix multiplication.

Key Results and Complexity

Circuit Depth: The total circuit depth is $O(\max_k \text{polylog}(P_k P_{k+1}))$ . Crucially, this depth is independent of the chain length $K$ . This assumes that each matrix $M^{(k)}$ can be loaded into a quantum state in polylogarithmic time (e.g., via QRAM).
Qubit Count: The algorithm requires $O(\sum_{k=0}^K \log P_k)$ qubits. For $K$ square $N \times N$ matrices, this is $\Theta(K \log N)$ . This represents an exponential compression over classical memory ( $O(KN^2)$ ) but is not $K$ -free; the algorithm trades qubit count for depth.
Gate Count: The total gate count remains linear in $K$ , specifically $\Theta(K \cdot \text{polylog}(N))$ , as $K$ state-preparation operators are applied in total.
Signal Weight ( $\Omega_W$ ): The output state contains the desired product $W$ $W$ scaled by a normalization factor $N = 1/\prod \|M^{(k)}\|_F$ $N = 1/ \prod ∥ M^{(k)} ∥_{F}$ . The "signal weight" is defined as $\Omega_W = \|W\|_F^2 / \prod \|M^{(k)}\|_F^2$ $Ω_{W} = ∥ W ∥_{F}^{2} / \prod ∥ M^{(k)} ∥_{F}^{2}$ .
- $\Omega_W \leq 1$ .
- For well-conditioned matrices (flat spectrum), $\Omega_W$ decays exponentially with $K$ .
- For matrices with peaked spectral structure (near rank-1), $\Omega_W$ remains close to unity.
- The authors note that Amplitude Amplification can boost $\Omega_W$ to a constant, at the cost of $O(1/\sqrt{\Omega_W})$ repetitions, which reintroduces a dependence on $K$ .

Contributions

Depth-Independent Subroutine: A quantum subroutine for matrix chain multiplication with circuit depth independent of $K$ , improving upon all prior methods where depth scales with $K$ .
Correctness Proof: A formal proof of correctness for arbitrary chain lengths $K$ (both odd and even).
Chain-Vector Specialization: A specialized version for computing $Wv$ (matrix chain applied to a vector), relevant for iterative solvers and power methods.
Open-Source Implementation: Public implementations in Qiskit and QCLAB frameworks.

Significance and Claims
The paper positions the Two-Tower algorithm as a depth-efficient building block for downstream quantum algorithms that operate on matrix-encoded states. The authors explicitly state that the advantage is realized when the downstream computation requires only aggregate quantities (such as norms, traces, inner products, or spectral properties) extractable via Amplitude Estimation, rather than full tomography of the matrix entries.

Specific applications identified include:

Norm estimation and variance estimation.
Graph spectral analysis (computing powers $A^K$ for walk counting or mixing estimation).
Solving linear systems with chain-structured operators (via HHL or Neumann-series LCU).
Quantum machine learning kernel evaluation.
Iterative numerical methods (e.g., power method, Krylov subspace construction).

The authors maintain a modest stance regarding the signal weight issue, acknowledging that while the depth is independent of $K$ , the signal weight may decay, requiring Amplitude Amplification which adds a $K$ -dependent cost. They do not claim a universal exponential speedup for all matrix chain tasks but rather a specific trade-off: trading qubit resources (linear in $K$ ) for circuit depth (constant in $K$ ).

Future Work
The paper identifies three specific directions for future research:

Hybrid Strategies: Alternating between Two-Tower (constant depth, growing qubits) and block-encoding (growing depth, fewer qubits) to manage signal weight decay.
Complex Matrices: Extending the construction to complex-valued matrices.
Unitary Chains: Generalizing the method to chains of unitary operators for quantum simulation and process tomography.