⚛️ quantum physics

The Practicality of Randomized Quantum Linear Systems Solvers

This paper demonstrates that randomized quantum linear systems solvers, despite offering shallower circuits than block-encoding methods, remain practically infeasible for early fault-tolerant devices due to prohibitive non-Clifford gate requirements, even though random Taylor expansion kernels are significantly more efficient than product formulas.

Original authors: Siddharth Hariprakash, Roel Van Beeumen, Katherine Klymko, Daan Camps

Published 2026-07-29

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Siddharth Hariprakash, Roel Van Beeumen, Katherine Klymko, Daan Camps

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 you are trying to solve a massive, tangled knot of math problems that are too big for any regular computer to untangle in a reasonable amount of time. This is the world of quantum computing, a field where scientists build machines that use the weird rules of tiny particles to solve these impossible puzzles. One of the most famous types of puzzles they want to solve is called a "linear system," which is essentially a giant grid of numbers where you need to find a specific answer hidden inside. To crack these codes, researchers often use a technique called "Hamiltonian simulation," which is like running a movie of how a quantum system changes over time to see what happens. For a long time, the best way to do this required building incredibly deep and complex circuits, like trying to build a skyscraper out of Jenga blocks without it falling over. But recently, a new idea emerged: what if we didn't build the whole skyscraper at once? What if we just took a bunch of random, quick snapshots of the building, averaged them out, and hoped the picture was clear enough? This "randomized" approach promised to be much simpler and easier to build on early quantum computers.

However, a new study by Siddharth Hariprakash and his team at Lawrence Berkeley National Laboratory and BlueQubit Inc. decides to put this promising idea to the ultimate test. They didn't just look at the theory; they did the heavy math to figure out exactly how many resources—like time and computer power—this random snapshot method would actually need to work. Think of it like checking the fuel gauge on a car that everyone claims can drive to the moon. The researchers built a detailed map of the journey, calculating every single step required to get a clear answer. Their findings are a bit of a reality check: while the random method is indeed simpler to build, it turns out to be incredibly inefficient. They found that even for a tiny, simple problem (a 4 by 4 grid of numbers), the method would require a staggering number of operations—about 10 to the power of 15 non-Clifford gates—to get a good answer. To put that in perspective, that's a number so huge it's practically impossible to achieve with current or near-future technology.

The paper compares two different ways to take these "snapshots" of the quantum system. One method is like following a strict recipe (called a Product Formula), and the other is like rolling dice to decide your next move (called a Random Taylor Expansion). The researchers discovered that the "dice-rolling" method is actually the better of the two bad options, requiring about ten times fewer resources than the strict recipe. But here's the kicker: even the better method is still so expensive that it's not practical for solving real-world problems right now. The study concludes that while these randomized schemes are clever and theoretically sound, the sheer amount of work they demand means they might not be the magic bullet we were hoping for in the early days of quantum computing. The authors have provided a clear, non-asymptotic (meaning they didn't just guess at the end; they calculated the exact numbers) proof that for these specific problems, the cost is simply too high.

The Story of the Randomized Solver

Let's dive into the details of what the authors actually did. They were looking at a specific type of quantum algorithm designed to solve linear equations. Imagine you have a giant, complex machine (the matrix) and you want to know what happens when you put a specific input into it. The goal is to find the output, but the machine is so complex that you can't just run it once.

The researchers focused on a "randomized" approach. Instead of running the machine perfectly, this method tries to approximate the answer by taking many random samples. It's like trying to guess the average height of everyone in a stadium. You could measure every single person (which is hard and takes a long time), or you could ask a few random people, guess their height, and average those guesses. The hope was that by taking enough random guesses, you'd get the right answer without needing a super-complex setup.

The paper breaks this process down into three main steps, which they analyzed with extreme precision:

The Recipe (Fourier Series): First, they had to figure out how to turn the math problem into a series of random "times" to sample. They used a mathematical trick called a Fourier series to approximate the inverse of the matrix. Think of this as creating a recipe that tells you exactly which random moments in time to look at. The authors calculated exactly how many ingredients (terms in the series) and how precise the measurements needed to be to get a good approximation. They found that even for small problems, you need a lot of these ingredients.
The Snapshot (Hamiltonian Simulation): Next, for each random time chosen, the quantum computer has to simulate the system. This is the hard part. The authors looked at two ways to do this simulation:
- Product Formula (PF): This is like breaking a long journey into small, fixed steps. You walk a little bit, stop, walk a little more, and so on. It's a very structured way to move.
- Random Taylor Expansion (RTE): This is more chaotic. It's like rolling a die to decide how many steps to take and in what direction. It introduces a second layer of randomness.
The Average (Sampling): Finally, you take all the results from these snapshots and average them out to get the final answer. The more snapshots you take, the closer you get to the true answer.

The Big Reveal: It's Too Expensive

The most important part of the paper is the calculation of the "cost." In the world of quantum computing, cost is measured in "gates," which are the basic operations the computer performs. The authors calculated exactly how many gates are needed to solve a problem with a certain level of accuracy.

They found that the cost scales up incredibly fast. Even for a tiny problem—a 4 by 4 matrix with a condition number (a measure of how hard the problem is) of 100—the method requires about 10^15 (that's a 1 followed by 15 zeros) non-Clifford gates to converge. This is a number that is far beyond what any quantum computer we can build today, or even in the near future, can handle. It's like trying to build a bridge across the ocean using only toothpicks; the math says it's possible in theory, but the materials just aren't there.

The authors also compared the two simulation methods (PF and RTE). They found that the Random Taylor Expansion (RTE) method is significantly better than the Product Formula (PF). Specifically, RTE requires about an order of magnitude (10 times) fewer gates to reach the same level of accuracy. However, even with this 10x improvement, the total number of gates is still astronomically high. The paper explicitly states that neither method is practical for current or near-term hardware.

What This Means for the Future

The paper doesn't just say "this is hard"; it gives us a clear map of why it's hard. The main bottleneck is the "condition number" of the problem. As the problem gets harder (the condition number goes up), the number of gates needed goes up by the fourth power. This means if you double the difficulty of the problem, you need 16 times more resources. This scaling law makes the randomized approach very expensive for the kinds of problems scientists actually want to solve.

The authors are very careful to say that their results are based on explicit calculations and simulations, not just guesses. They tested their math on small, random matrices and found that their predictions matched the reality of the simulations perfectly. This gives us high confidence in their conclusion: while the idea of randomizing quantum algorithms is clever and reduces the complexity of the circuits, the sheer number of samples required makes it impractical for solving linear systems in the near future.

In the end, this paper serves as a crucial reality check. It takes a promising, buzz-worthy idea and measures it against the hard numbers of physics and engineering. The result is that while the randomized approach is a fascinating piece of theoretical work, it's not the silver bullet for early quantum computers. The authors suggest that if we want to make progress, we might need to look at different ways to break down the problem, perhaps by using classical computers to simplify the problem first or finding new mathematical tricks that don't require such a massive number of random samples. But for now, the dream of solving these complex linear systems with a simple, randomized quantum shortcut remains just that—a dream, waiting for a breakthrough in hardware or algorithm design to become a reality.

Technical Summary: The Practicality of Randomized Quantum Linear Systems Solvers

Problem Statement
This work addresses the Quantum Linear Systems (QLS) problem: estimating scalar properties of the form $\langle \phi | A^{-1} | \psi \rangle$ for an $N \times N$ Hermitian operator $A$ , given state preparation oracles for $|\psi\rangle$ and $|\phi\rangle$ . While existing quantum linear algebra approaches often rely on block-encoding and Quantum Singular Value Transformation (QSVT), these methods typically require deep, coherent circuits that are challenging for near-term fault-tolerant hardware. To mitigate this, randomized algorithms have been proposed, which reformulate the problem to use classical sampling combined with shallow Hamiltonian simulation subroutines. However, prior work in this space has largely provided only asymptotic complexity bounds, leaving the explicit, end-to-end resource requirements (including classical pre-processing and sampling overhead) unclear.

Methodology
The authors present a detailed, non-asymptotic analysis of a randomized quantum algorithm that combines Fourier series approximation with Hamiltonian simulation. The workflow consists of three main stages:

Classical Pre-processing (Fourier Series Construction):
The inverse function $f(x) = x^{-1}$ is approximated over a domain $D_\kappa$ (excluding the singularity at zero) using an integral representation. The authors employ a hybrid discretization scheme:
- Truncation: The infinite integration range is truncated to finite bounds $(y_{max}, z_{max})$ .
- Discretization: The truncated integral is discretized using a Gauss-Legendre rule for the oscillatory $y$ -integral and a trapezoidal rule for the rapidly decaying $z$ -integral. This yields a Fourier series $F(A) \approx A^{-1}$ with coefficients $\alpha_s$ and times $t_s$ .
- Sampling: The Fourier coefficients are normalized to form a probability distribution, allowing the algorithm to sample specific Fourier times $t_j$ classically.
Quantum Processing (Hamiltonian Simulation):
For each sampled time $t_j$ , the algorithm estimates $\langle \phi | e^{-iAt_j} | \psi \rangle$ using a Hadamard test. The authors analyze two distinct subroutines for implementing the controlled time-evolution operator $e^{-iAt_j}$ :
- Product Formula (PF): Uses a second-order Trotter-Suzuki decomposition to approximate the evolution.
- Random Taylor Expansion (RTE): Uses a Linear Combination of Unitaries (LCU) approach based on a truncated Taylor series, introducing a second layer of randomization where individual unitaries are sampled.
Classical Post-processing:
The results of the Hadamard tests are averaged over $N_S$ samples to converge to the target scalar value. The total error is decomposed into Fourier approximation error, sampling error, and simulation bias.

Key Contributions
The paper makes four primary contributions, distinguishing itself from prior asymptotic treatments:

Explicit Non-Asymptotic Error Bounds: The authors derive rigorous, non-asymptotic bounds for every algorithmic parameter (truncation limits, discretization nodes, sampling counts) required to achieve a target error $\epsilon$ . This includes explicit formulas for the number of Fourier terms ( $J, K$ ) and the normalization factors ( $N_y, N_z$ ).
Resource Estimates for Two Kernels: The work provides detailed gate-count formulas for both the Product Formula (PF) and Random Taylor Expansion (RTE) subroutines. It analyzes both high-probability convergence (via Hoeffding's inequality) and Root Mean Squared Error (RMSE) convergence.
Trade-off Analysis: The study explicitly characterizes the trade-off between the number of samples ( $N_S$ ) and the per-sample gate depth ( $N_{CP}$ ). It demonstrates how adjusting parameters (e.g., the Trotter number $r$ or the RTE segment count) shifts the burden between sampling complexity and circuit depth.
Numerical Validation: The theoretical bounds are empirically verified on small-scale random Hermitian matrices ( $N=4$ and $N=16$ ), confirming the validity of the error bounds and the convergence rates.

Results

Scalability: Both subroutines exhibit a total non-Clifford gate complexity scaling as $\tilde{O}(\kappa^4 / \epsilon^2)$ (where $\kappa$ is the condition number). This $\kappa^4$ scaling arises from the product of the sample complexity $\tilde{O}(\kappa^2)$ and the per-sample simulation cost $\tilde{O}(\kappa^2)$ .
Practicality: The analysis reveals that even for modest problem sizes, the resource requirements are prohibitive. For a $4 \times 4$ instance with $\kappa = 100$ and target error $\epsilon \sim 10^{-3}$ , the algorithm requires approximately $10^{15}$ controlled Pauli rotations to converge.
PF vs. RTE Comparison:
- RTE Efficiency: The RTE subroutine is found to be more efficient than PF in terms of total gate budget. While RTE requires roughly an order of magnitude more samples due to a larger variance prefactor (scaling as $e^{2/c_{RTE}}$ ), its per-sample gate cost is significantly lower (roughly 85 times lower in the tested instances) because it avoids the linear dependence on Pauli sparsity $L$ inherent in the PF Trotter steps.
- Optimal Configuration: The optimal RTE configuration (with $c_{RTE} \approx 2$ ) yields a total gate budget roughly 6% of that required by PF, though both remain impractical for current hardware.
Dimensional Independence: The Fourier approximation error bounds are shown to be independent of the Hilbert space dimension $N$ , depending only on the condition number and the Pauli weight.

Significance and Claims
The paper claims to bridge the gap between asymptotic proposals and hardware implementation by providing the first explicit, end-to-end resource estimates for randomized QLS solvers. The authors conclude that while randomized schemes offer structural advantages (such as reduced qubit width to $\log(N)+1$ and shallower circuits per sample), the practicality of such schemes is called into question by the explicit resource counts.

The $\kappa^4$ scaling and large prefactors render these methods infeasible for problems of scientific interest on near-term or early fault-tolerant devices, even when compared to block-encoding methods. The authors note that while RTE is relatively more efficient than PF, the absolute gate budgets remain prohibitive. The work suggests that future improvements would require alternative integral representations with weaker $\kappa$ -dependence, classical preconditioning, or lower-variance sampling distributions, but currently, the explicit bounds indicate that these randomized approaches are not yet a viable alternative to coherent block-encoding methods for solving linear systems.

The Story of the Randomized Solver

The Big Reveal: It's Too Expensive

What This Means for the Future

Technical Summary: The Practicality of Randomized Quantum Linear Systems Solvers

More like this