← Latest papers
⚛️ quantum physics

Success Probability of Block-Encoding Methods

This paper analyzes the often-overlooked success probability and associated shot overhead of three block-encoding methods (LCU, qubitization, and QSVT) using the Hubbard model, demonstrating that these probabilities vary significantly with system size and spectral properties, and arguing that they must be included in accurate resource estimates for quantum algorithms.

Original author: Oumaya Ladhari, Matthieu Saubanère, Jérémie Messud

Published 2026-11-17
📖 6 min read🧠 Deep dive

Original author: Oumaya Ladhari, Matthieu Saubanère, Jérémie Messud

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

Quantum computers promise to solve problems that are currently impossible for classical machines, from designing new drugs to modeling complex materials. To do this, they must manipulate information using the strange rules of quantum mechanics. A major hurdle in this field is that many useful mathematical operations are not "reversible" in the way quantum computers naturally work. Imagine trying to run a movie backward; if the original scene involved a glass shattering, you cannot simply reverse the film to get the glass back together because the information about where the shards went is lost. Similarly, quantum computers struggle with operations that lose information. To get around this, scientists use a clever trick called block-encoding. This method wraps a difficult, one-way operation inside a larger, reversible quantum process. However, this trick comes with a catch: the computer only produces the correct result if a specific, random measurement outcome occurs. If the measurement fails, the entire attempt is discarded, and the process must be started over. This means that the efficiency of these powerful algorithms depends heavily on how often they succeed on the first try.

A team of researchers from TotalEnergies and the University of Bordeaux has taken a close look at this success rate. They investigated three different ways scientists currently build these block-encoding tricks to see how often they actually work and what factors cause them to fail. Using a standard test model known as the Hubbard model, which simulates how electrons interact in a material, they ran simulations on systems ranging from very small to quite large, involving up to thirty-five quantum bits. Their goal was to move beyond simple estimates of how many quantum bits or gates an algorithm needs, and instead calculate the "shot overhead"—the extra number of times a computer must run a circuit just to get a single valid result. They found that the success rate is not a fixed number; it changes dramatically depending on the specific mathematical method used, the size of the system, and the initial state of the quantum computer.

The researchers examined three distinct approaches. The first, known as the linear combination of unitaries, is a straightforward way to build these operations. They discovered that for this method, the success rate is limited by a specific ratio between the total strength of the interactions in the system and the sum of the individual parts used to describe them. Surprisingly, they found that as the system grew larger, the success rate did not crash toward zero as one might fear. Instead, it settled into a stable, predictable level. This is good news for scaling up, but it also revealed a subtle trap: the success rate does not tell you how close your starting guess is to the true answer. A computer could have a decent success rate even if its initial guess was very poor, meaning researchers cannot rely on this number alone to judge the quality of their input.

The second method, called qubitization, uses a more complex sequence of steps that can be repeated to refine the result. Here, the success rate behaves like a wave, rising and falling as the number of steps increases. The researchers found that this oscillation is not random noise but a predictable pattern driven by the specific energy levels of the system. This means that by choosing the right number of steps, one can hit a "sweet spot" where the success rate is very high, or accidentally land on a "dead zone" where it is nearly zero. They showed that it is possible to predict these favorable steps using only a small amount of preliminary data, without needing to know the full, complex solution in advance. This insight is crucial for algorithms that build a library of solutions, as it allows scientists to pick the most efficient steps and avoid wasting time on those that will almost certainly fail.

The third approach, quantum singular value transformation, offers the most flexibility, allowing for a wide variety of mathematical shapes to be applied to the data. However, this flexibility introduces a new challenge: a scaling factor that must be chosen carefully. If this factor is chosen too loosely, the success rate drops significantly, wasting computational resources. If it is chosen too tightly, the mathematical process used to find the solution becomes unstable and may fail to converge. The team developed a new way to calculate this factor that guarantees the process will work while keeping the success rate as high as possible. They found that this "certified" bound provides a safe middle ground, ensuring the algorithm is both robust and efficient.

Perhaps the most significant finding of the study concerns how these success rates behave as systems get larger. In many quantum algorithms, the difficulty increases exponentially with size, making large systems impossible to simulate. However, for the methods tested here, the success rate remained surprisingly stable as the number of simulated sites grew from two to fourteen. The probability of success did not vanish; it plateaued. This suggests that the "shot overhead" does not necessarily explode as we move to larger, more realistic problems. Furthermore, the researchers applied these findings to a technique called quantum Krylov methods, which builds a subspace of solutions to find the lowest energy state of a system. They showed that the number of shots required to get a precise answer varies wildly depending on which steps are chosen. By selecting only the steps with high success rates, the algorithm becomes much more efficient, even though it requires slightly deeper circuits.

The study concludes that the success probability is a critical, yet often overlooked, component of resource estimation. When planning a quantum experiment, scientists cannot just count the number of gates or the depth of the circuit; they must also account for how often the machine will need to restart. Ignoring this factor can lead to a massive underestimation of the time and resources required. The researchers demonstrated that by understanding the specific behavior of the success rate for each method, one can make informed choices to minimize waste. Whether it is picking the right number of steps in a qubitization sequence or choosing the correct scaling factor for a transformation, these small adjustments can mean the difference between a feasible experiment and one that is hopelessly inefficient. The work provides a clear roadmap for evaluating the true cost of running these advanced algorithms, ensuring that the path toward practical quantum computing is built on accurate and realistic expectations.

Drowning in papers in your field?

Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.

Try Digest →