Researchers at TotalEnergies and Université de Bordeaux have identified a hidden factor impacting the efficiency of block-encoding methods, a technique for applying complex operations on quantum computers. Their analysis reveals the success probability of these methods, the chance a quantum calculation yields a valid result, is often overlooked in resource estimations.
The work demonstrates that for Linear Combination of Unitaries (LCU), the success probability is bounded by the squared ratio between the spectral norm and the 1-norm of the Pauli decomposition, a previously unquantified limit. This finding suggests the success probability should be a key consideration when evaluating the feasibility of block-encoding algorithms.
LCU Success Probability Limited by Spectral and 1-Norm Ratios
Researchers found that this ratio, represented as (Ω_s/λ_s)^2, directly bounds the achievable success probability of LCU. Using the one-dimensional Hubbard model with up to 14 sites, requiring 35 qubits, the team demonstrated a counterintuitive behavior for LCU: while the overlap with the ground state decreases as system size increases, the success probability plateaus. For qubitization, the success probability oscillates with the Chebyshev degree, denoted as k.
Hartree-Fock Input Impacts LCU Success Probability Plateauing
63 for systems with 14 sites, before tending towards 0. Researchers found this relationship holds true for the Hubbard model systems and structured input states they investigated, revealing a fundamental constraint on LCU efficiency.
Counterintuitively, the team’s analysis of LCU and Quantum Singular Value Transformation (QSVT) block-encodings showed no systematic decay in success probability with increasing system size, a result that challenges the assumption that larger simulations automatically yield more reliable outcomes. For QSVT, the polynomial normalization constant, C, directly dictates the success probability, with a tight certified bound ensuring feasibility and balancing success against robustness.
Qubitization Success Oscillates with Chebyshev Degree
The success probability of qubitization isn’t fixed, but rather fluctuates depending on the chosen Chebyshev degree, a previously unquantified aspect of this block-encoding method. Different degrees of the same quantum walk can therefore yield substantially different shot overheads, a finding with implications for accurate quantum simulation. Researchers found that selecting an appropriate Chebyshev degree is important, as a poorly chosen value can lead to a significant drop in success probability, even approaching a node in the oscillation.
This degree-dependent behavior allows for identification of favorable values by analyzing a few dominant spectral components or predicting them from shallow-degree data, offering a pathway to optimize performance. While the success probability doesn’t penalize the use of a simple Hartree-Fock (HF) input state in larger systems, it cannot be used as a measure of input state fidelity, which requires separate assessment. An application of these methods to quantum Krylov methods revealed a nonuniform shot overhead across different Krylov moments, further highlighting the importance of considering success probability in resource estimation.
QSVT Polynomial Normalization Directly Determines Success Probability
For Quantum Singular Value Transformation (QSVT), the scaling factor used to normalize the polynomial transformation directly dictates the probability of a successful quantum calculation, a relationship not previously quantified for this block-encoding method. Unlike Linear Combination of Unitaries (LCU) and qubitization, where scaling is inherited from the LCU 1-norm, QSVT introduces an additional factor that must be carefully managed to maximize efficiency. The success probability is maximized by choosing this normalization constant, denoted as C, as close as possible to the optimal value, Copt, while maintaining feasibility.
A certified normalization approach consistently converges with a small positive margin across all tested degrees, offering a more reliable pathway to maximizing success probability. Data presented in the paper shows that for a degree of 2, the residual error after 20 iterations using the certified method reached 5.5 x 10-13, while the grid-based method exhibited a larger error of 5.9 x 10-2. This demonstrates a substantial improvement in precision with the certified approach. The success probability of QSVT is also intrinsically linked to the degree of the polynomial used.
Block-Encoding Success Probability Introduces Quantum Shot Overhead
The efficiency of common quantum computation techniques, specifically block-encoding methods, may be limited by a previously overlooked factor: the probability of a successful calculation. This introduces a “shot overhead” that accumulates when these methods are applied repeatedly, such as in building up a Krylov subspace. 25 and 0. 26 for systems with four or more sites. Qubitization, another block-encoding technique, introduces further complexity with its reliance on the Chebyshev degree, k. The resulting success probability oscillates with changes to k, meaning different degrees can lead to “substantially different shot overheads,” according to the researchers.
The paper states, demonstrating a quantifiable limit on performance. These findings emphasise the importance of incorporating success probability into the resource estimation of block-encoding-based algorithms, ensuring more accurate predictions of quantum computational cost.
Success Probability Depends on Hamiltonian Spectral Properties
This constraint arises from the need for a unitary preparatory operator, impacting the achievable success rate even with optimal input states. The work demonstrates that for a half-filled ground state, the LCU method nearly saturates this bound, while Hartree-Fock inputs typically fall short, suggesting input state selection is critical.
Analysis reveals that the success probability isn’t solely determined by scaling up quantum simulations; for LCU, the probability plateaus with system size even as the overlap with the true ground state diminishes. This counterintuitive finding suggests that simply increasing the number of qubits doesn’t guarantee a higher chance of obtaining a valid result, and that other factors must be optimized alongside system size.
Quantum Krylov Methods Exhibit Nonuniform Shot Overhead
The success probability introduces a shot overhead often overlooked in resource estimations for quantum algorithms. They found that favorable degrees, minimizing the required quantum shots, can be predicted by analyzing only a few dominant spectral components or using data from shallow-degree simulations. This offers a pathway to optimize performance without exhaustive calculations. This nonuniformity highlights the need to consider success probability when estimating resources for block-encoding-based algorithms.
But this benefit comes at the cost of increased circuit complexity. This finding suggests that a comprehensive approach, balancing success probability with circuit depth, is essential for realizing practical quantum advantage.
Block-Encoding Functions: LCU, Qubitization, and QSVT
The efficiency of three common block-encoding constructions, Linear Combination of Unitaries (LCU), qubitization, and Quantum Singular Value Transformation (QSVT), is intrinsically linked to their success probabilities, a factor often overlooked in resource estimation. These methods apply functions of a Hermitian operator on a quantum computer, but only after a successful postselection process, introducing an overhead in required quantum “shots”. Researchers have detailed how this success probability varies between the three approaches, and is dependent on the input state and system size.
This establishes a quantifiable limit on LCU’s efficiency, suggesting that increasing the system size does not guarantee improved results. “λ ≥ Ω,” where λ represents the LCU 1-norm and Ω the spectral norm of the operator, defines this relationship.
The study highlights that the success probability is not uniform across Krylov moments in quantum Krylov methods, further emphasizing the need to incorporate it into resource estimation for block-encoding-based algorithms. The team’s analysis, summarized in a comparative table, shows that each construction, LCU, qubitization and QSVT, has a unique success probability equation dependent on the encoded function, implementation primitive and normalization. Understanding these dependencies is important for optimizing performance and accurately assessing the feasibility of quantum simulations.
Renormalization Factor Impacts LCU Unitarity and Success
Researchers found that replacing the LCU 1-norm with the tighter spectral norm provides an upper benchmark for achievable success probability, directly impacting the efficiency of quantum simulations. Specifically, the success probabilities using the 1-norm and spectral norm are mathematically defined as p^(I)_(success, 1-norm) = 1/λ^ and p^(I)_(success, spectral) = 1/Ω^, where represents the eigenvalues of the Hamiltonian before renormalization. Qubitization, another block-encoding construction, also reveals a relationship between renormalization and success, though less direct than with LCU.
The analysis demonstrates that the polynomial normalization constant used in Quantum Singular Value Transformation (QSVT) directly sets the success probability, offering a pathway to balance success against phase-finding robustness. This balance is achieved through a “tight certified bound” requiring the scaling factor C to be greater than or equal to the supremum of the absolute value of the target polynomial, C ≥ = sup_(x ∈ [-1,1])|P(x)|.
Any looser bound reduces the success probability as 1/C^2, highlighting the sensitivity of QSVT to this parameter. The resulting success probability is defined as = = 1/C^ |P(E_n)|^2, where ‘d’ is the polynomial’s degree and ‘’ are its coefficients. “The scaling factor C directly controls the QSVT success probability,” the paper states, emphasizing the importance of this parameter in practical applications.
👉 More information
🗞 Success Probability of Block-Encoding Methods
✍️ Oumaya Ladhari and Jérémie Messud (TotalEnergies, Paris La Défense Cedex, France); Matthieu Saubanère (Université de Bordeaux, CNRS, LOMA, UMR, Talence, France)
🧠 ArXiv: https://arxiv.org/abs/2611.21080v1




See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
