⚛️ quantum physics

Quantum power iterations via tensor networks

This paper proposes a quantum algorithm that implements classical power iterations using unitary matrix product operators and post-selection to overcome the exponential rank growth bottleneck of classical tensor network methods, while explicitly noting that it establishes the construction and operating conditions without yet demonstrating a definitive computational advantage over classical approaches.

Original author: V. Akshay, A. Berezutskii, Ar. Melnikov, A. Termanova, M. R. Perelshtein

Published 2026-11-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: V. Akshay, A. Berezutskii, Ar. Melnikov, A. Termanova, M. R. Perelshtein

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 author. For technical accuracy, refer to the original paper. Read full disclaimer

Optimization is the art of finding the best possible solution to a problem, whether that means designing a more efficient airplane wing, training a computer to recognize faces, or simply finding the highest peak in a vast, foggy landscape. For decades, scientists have relied on a classic mathematical technique called power iteration to solve these problems. Imagine trying to find the tallest mountain in a range by repeatedly multiplying a map of the terrain by itself; with each multiplication, the highest peaks grow taller and more distinct, while the valleys and smaller hills fade away until only the single highest point remains. This method works beautifully on classical computers for simple tasks, but it hits a wall when the maps become too complex. As the calculations repeat, the amount of data required to describe the landscape explodes, growing so fast that even the most powerful supercomputers cannot keep up. This is the bottleneck that researchers have long struggled to overcome.

A team of scientists at Terra Quantum AG has now proposed a way to bypass this data explosion by moving the calculation onto a quantum computer. Instead of trying to store the entire, growing map in memory, they devised a method to encode the landscape into a quantum circuit—a sequence of operations performed on quantum bits, or qubits. Their approach treats the problem not as a massive data storage challenge, but as a physical process. By converting the mathematical description of the landscape into a specific type of quantum circuit, they can perform the repeated "multiplications" that power iteration requires. In this quantum realm, the operation happens naturally as the system evolves, without the need to store exponentially large amounts of data. The researchers demonstrated that this method can successfully identify the highest point on a landscape, even when the landscape is complex and filled with many local peaks and valleys.

The core of their work involves translating a mathematical object known as a matrix product operator into a quantum circuit. In the classical world, performing the necessary steps to find the best solution often causes the complexity of the data to spiral out of control. The researchers found a way to approximate this complex mathematical object with a simpler, "unitary" version that fits inside a quantum computer. They used a technique called variational optimization, which is essentially a trial-and-error process where the computer adjusts the settings of its circuit until it closely matches the target mathematical shape. Once this circuit is built, the researchers can run the power iteration process by simply repeating the same block of quantum operations over and over. To ensure the process works correctly, they must check the result of each step, a process known as post-selection, which acts like a filter to keep only the successful outcomes and discard the rest.

The team tested their method on several different mathematical landscapes, ranging from a simple wave-like curve to more complicated, multi-dimensional shapes known as the Ackley and Rosenbrock functions. For the simple wave, the method worked perfectly, analytically recovering the exact solution. For the more complex Ackley function, which features a rugged terrain with many local peaks, the quantum approach successfully found the global maximum, even when the mathematical approximation used was not perfect. However, the study also revealed a critical limitation. When they applied the method to the Rosenbrock function, which has a very flat, narrow valley leading to the solution, the quantum circuit struggled to distinguish the true peak from its neighbors. The researchers found that the method only works reliably if the difference between the best solution and the next-best solution is large enough to be clearly seen through the noise of the approximation. If the landscape is too flat or the peaks too similar, the quantum computer cannot separate them, no matter how many times the calculation is repeated.

Crucially, the authors are careful to state that this is not yet a proven victory over classical computers for all problems. In the specific examples they tested, the classical method did not actually suffer from the data explosion they hoped to avoid, meaning the quantum approach did not demonstrate a speed advantage in those cases. The true value of their work lies in establishing a new pathway: a way to run these powerful optimization algorithms on quantum hardware without the classical data bottleneck. They showed that the success of the method depends heavily on the specific shape of the problem being solved. If the problem has a clear, distinct peak and can be described with a low-rank approximation, the quantum method is viable. If the landscape is too flat or the approximation too rough, the method fails.

The researchers also discovered a way to significantly improve the efficiency of their quantum circuits. By adjusting how the mathematical scaling was handled during the optimization process, they were able to increase the probability of a successful run by many orders of magnitude. In one instance, this adjustment improved the success rate by twenty-two orders of magnitude, making the difference between a result that is practically impossible to obtain and one that is feasible. This finding suggests that the way the problem is framed mathematically is just as important as the quantum hardware itself. The study concludes that while this is not a magic bullet for every optimization problem, it provides a solid foundation for future work. It identifies the specific conditions under which quantum power iterations can operate reliably and points toward a future where quantum computers might tackle optimization problems that are currently out of reach for classical machines, provided the problems fit the right criteria.

Technical Summary: Quantum Power Iterations via Tensor Networks

Problem Statement
Power iteration is a classical algorithm used to find the dominant eigenvector of a diagonalizable matrix, a task central to many optimization problems formulated as eigenvalue searches. The algorithm operates by repeatedly multiplying a matrix by a vector (MatVec) and renormalizing. When implemented using classical tensor networks (specifically Matrix Product States (MPS) and Matrix Product Operators (MPO)), this approach faces a scalability bottleneck: in the worst case, the tensor ranks grow exponentially with the number of iterations, rendering the method intractable for deep iterations. While quantum computers naturally perform unitary operations regardless of rank, encoding non-unitary operators (like the diagonal matrices used in power iteration) and managing the resulting rank growth without exponential classical overhead remains a challenge.

Methodology
The authors propose a quantum realization of power iterations that circumvents the classical rank-growth bottleneck by casting low-rank tensor network representations into quantum circuits. The methodology proceeds as follows:

Encoding: A target function $f(x)$ is discretized and represented as an MPS. The corresponding diagonal operator $H$ is represented as an MPO.
Variational Unitary Approximation: Since quantum circuits require unitary evolution, the non-unitary target MPO ( $H_{mpo}$ $H_{m p o}$ ) is approximated by a "unitary MPO" ansatz ( $U_{mpo}$ $U_{m p o}$ ). This is achieved by constraining the tensor cores of the MPO to be unitary matrices.
- To accommodate non-unitary targets, the method introduces ancillary qubits. The virtual bonds of the MPO are interpreted as ancillary spaces.
- A variational search is performed using Riemannian optimization to minimize the Frobenius distance between the target $H_{mpo}$ and the scaled unitary approximation $c \cdot \tilde{U}$ , where $\tilde{U}$ is the effective linear operator obtained by initializing and post-selecting the ancillary qubits.
Circuit Implementation: The optimized unitary MPO is compiled into a quantum circuit. A single power iteration is realized by applying this circuit block to an initial state (prepared as $|+\rangle^{\otimes n} \otimes |0\rangle^{\otimes n_a}$ ) and performing post-selection on the ancillary qubits to the all-zero state.
Iteration: To perform $p$ iterations, the circuit block is concatenated $p$ times, with new ancillary qubits initialized at each step. The process concludes by measuring the system qubits; the bit-string with the highest probability corresponds to the candidate optimum.

Key Contributions

Quantum Formulation of Power Iterations: The paper establishes a framework for executing power iterations entirely on a quantum computer using static circuit blocks and post-selection, avoiding the exponential rank growth inherent in classical tensor network simulations of the same process.
Variational Unitary MPO Construction: The authors introduce a method to variationally approximate arbitrary diagonal MPOs with unitary MPOs using Riemannian optimization and cross-approximation techniques, making the approach instance-agnostic and suitable for black-box optimization.
Scalability Analysis: The study demonstrates that while the classical tensor network ranks grow exponentially with iterations, the circuit depth required for $p$ iterations grows only polynomially in the number of qubits ( $n$ ), iterations ( $p$ ), and ansatz rank ( $R$ ). However, the authors explicitly note that this polynomial depth does not guarantee overall scalability, as the post-selection probability decays exponentially with the number of iterations ( $p$ ), leading to an exponential total runtime in the general case.
Critical Conditions for Success: The work explicitly identifies the conditions under which the method operates reliably, emphasizing that success depends on the preservation of the relative gap between the largest and second-largest discretized values of the objective function, rather than just the global fitting error.

Results
The authors validated the methodology on several optimization benchmarks:

Sine Function: An analytically derived unitary MPO was constructed. Quantum power iterations successfully converged to the global maximum, with measurement probabilities aligning with theoretical expectations.
Ackley Function (2D and 4D): The method successfully identified the global minimum for both 2D and 4D instances. The authors demonstrated that even with rank-deficient unitary MPOs (where the global fitting error is non-negligible), the method succeeds if the approximation preserves the ordering of the top function values (i.e., the gap is larger than the approximation error).
Rosenbrock Function (2D): The method converged to the "banana-shaped" valley but failed to identify the exact discretized global optimum. The authors attribute this to the extreme flatness of the transformed objective, where the relative gap between the optimum and the next-best grid point is smaller than the approximation error, preventing the circuit from distinguishing the true maximum.
Scale Factor Optimization: A significant finding was that constraining the scale factor $c$ in the variational search to the operator norm of the target ( $c = \|H_{mpo}\|_2$ ) drastically improved the post-selection probability (by orders of magnitude) without sacrificing accuracy for the Ackley benchmarks.

Significance and Claims
The paper explicitly states that it does not demonstrate an end-to-end computational advantage over classical tensor network optimization for the specific instances studied. In the cases examined (smooth, low-dimensional benchmarks), classical tensor networks did not exhibit rank blow-up, meaning the quantum approach offered no runtime advantage.

Instead, the significance of the work lies in:

Establishing a Construction: Providing a viable route to implement power iterations on quantum hardware using tensor network concepts.
Identifying Open Questions: Highlighting that the central open question is the identification of problem families that simultaneously satisfy four conditions: (i) admitting accurate low-rank MPS/MPO approximations, (ii) allowing encoding into unitary MPOs with small error, (iii) maintaining acceptable post-selection probabilities, and (iv) possessing intermediate iterates that do not admit accurate low-rank classical approximations (the condition that would trigger classical rank explosion).
Black-Box Potential: The method is function-agnostic, suggesting potential for black-box optimization of functions that admit low-rank tensor representations, provided the specific gap and error conditions are met.

The authors conclude that while the circuit resources per iteration scale polynomially, the overall scalability is currently limited by the instance-dependent post-selection probability (which decays exponentially with iterations) and the number of measurements required to resolve the optimum, neither of which are guaranteed to be polynomial in general.

More like this