WorksPhysics and Astronomy
Success Probability of Block-Encoding Methods
Abstract
Block-encoding methods apply nonunitary functions of a normalized Hermitian operator on a quantum computer, but only upon a successful postselection, which introduces a shot overhead rarely included in resource estimates. We analyze the success probability of three constructions, namely linear combination of unitaries (LCU), qubitization and quantum singular value transformation (QSVT), where are the weights of the input state on the eigenstates of . Using the one-dimensional Hubbard model with up to 14 sites (35 qubits), we show that for LCU, the success probability is bounded by the squared ratio between the spectral norm and the -norm of the Pauli decomposition, and that for a Hartree–Fock input it plateaus with system size while the ground-state overlap keeps decreasing. For qubitization, it oscillates with the Chebyshev degree, and favorable degrees can be identified from a few dominant spectral components or predicted from shallow-degree data. For QSVT, the polynomial normalization constant directly sets the success probability, and a tight certified bound balances it against phase-finding robustness. An application to quantum Krylov methods shows a nonuniform shot overhead across Krylov moments. The success probability should therefore be part of the resource estimation of block-encoding-based algorithms.
Introduction
Block-encoding methods provide a general route for applying nonunitary transformations of an operator on quantum computers. Such transformations are needed in many applications, such as solving linear systems of equations [1, 2, 3], solving partial differential equations [4], or solving the Schrödinger equation for strongly correlated many-electron systems, e.g., using quantum Krylov subspace methods [5, 6, 7, 8, 9, 10, 11, 12]. In the latter case, the task is to determine the low-energy spectrum of the Hamiltonian of the electronic system, in particular its ground-state energy, which can also be targeted by block-encoding-based ground-state preparation and energy estimation [13, 14, 15]. Quantum Krylov subspace methods address this problem by constructing a subspace from repeated applications of to an input state. Because the Hamiltonian is not unitary, these applications cannot be realized directly on a quantum computer.
Let us first consider a block-encoding of a general Hermitian operator . One constructs a unitary acting on the system together with an ancilla register , such that a designated block of (the top-left block, selected by projecting the ancilla onto ) satisfies [16]
where
is a renormalized version of such that its spectral norm is less than or equal to one. can also include, when necessary, a shift. The application of to an input state is recovered when the ancilla register is measured in the state. The probability of obtaining this outcome, which we refer to as the success probability, is a central feature investigated in this work.
The Linear Combination of Unitaries (LCU) framework [16, 17, 18] provides a constructive way to build such a block-encoding. Writing the Hermitian operator as a weighted sum of Pauli strings ,
the LCU block-encoding is assembled from two operations acting on an ancilla register of qubits. A “prepare” operator creates a coefficient-weighted superposition on the ancilla,
and a “select” operator applies each Pauli string unitary conditioned on the ancilla index,
where we write for the measurement outcome in which all ancilla qubits are found in . Together, these operations directly give a block-encoding satisfying Eq. (1) through
An important point is that the necessary unitarity of the preparation operator in Eq. (4) imposes that the renormalization factor equals the so-called “LCU 1-norm”
Further refinements of the block-encoding construction give access to increasingly general functions of the Hermitian operator . For instance, qubitization builds on this same prepare and select pair: combining SELECT with a reflection about the state, , gives the quantum walk operator used here [16]. Powers of generate Chebyshev polynomials of ,
so that a single block-encoding form gives access to an entire family of transformations indexed by a degree . The LCU case is recovered at , since . Finally, Quantum Singular Value Transformation (QSVT) [3, 19, 20] generalizes this construction to a broad class of polynomial transformations of definite parity, renormalized by a factor so that on . For a polynomial of degree and a phase sequence , we define the phase-modulated walk-operator product
where the walk operator is applied times and is the reflection introduced above. Considering real polynomials, so that is Hermitian, QSVT guarantees that there exists a phase sequence such that [3]
The phases are determined classically beforehand from the coefficients of [21, 22, 23]. Qubitization and QSVT block-encodings thus give access to different encoded functions .
The three constructions discussed above, i.e., LCU, qubitization, and QSVT block-encodings, form the scope of this work. They correspond to (the identity, ) for LCU, for qubitization, and for QSVT. An important shared property of these three constructions is that the desired application of to an input state is obtained only upon a successful postselection of the ancilla register. The corresponding success probabilities are denoted by
and refers to a generic encoded function. Throughout, lowercase denotes a success probability, while denotes a polynomial and a Pauli string. For a direct postselection protocol, a success probability implies on average an overhead of in the number of circuit repetitions, or shots.
Understanding the success probability in detail is not straightforward, since it is determined by more than the operator itself. Indeed, it depends on the spectral properties of the renormalized operator, the considered function , and also the renormalization used to construct the block-encoding and the input state to which the is applied. We write the spectral decomposition of the Hamiltonian, of its normalized form and of the input state as
where are the eigenvalues of , ordered so that is the ground-state energy in the half-filled sector to which all input states considered here belong. We denote by and the extremal eigenvalues of over the full Fock space of the system qubits, on which the block-encoding acts. corresponds to normalized eigenvalues of (, or if a shift is introduced, with the 1-norm of the shifted decomposition). Interestingly, the block-encoding implementing an encoded function succeeds with probability
Equation (13) provides the common spectral framework used throughout this work: for a given encoded function , the success probability is determined jointly by the spectral weights of the input state, the spectrum of the normalized Hamiltonian, and the normalization required to implement .
Resource estimates for block-encodings of electronic Hamiltonians have focused on reducing the coefficient 1-norm , through factorized decompositions [24, 25, 26, 27, 28], orbital transformations [29] or Hamiltonian partitionings [30], in order to reduce the circuit depth; to our knowledge, the shot overhead due to the success probability has usually not been reported. In this article, we analyze this success probability for the three constructions above, using the one-dimensional Hubbard model as a controlled testbed, with the Hartree–Fock (HF) state as main input state, compared with the exact ground state and random states. To reach system sizes beyond those accessible with a dense Hamiltonian, we evaluate the action of on state vectors directly from its Pauli decomposition, which reduces the memory scaling from to and allows us to study up to 14 sites (28 system qubits, 35 qubits including the LCU ancilla register). For each construction we address one question: for LCU, how much the 1-norm limits the success probability; for qubitization, whose success probability oscillates with the degree , whether favorable degrees can be identified without computing the full spectrum, with an application to quantum Krylov methods; and for QSVT, how the polynomial scaling factor trades success probability against the robustness of phase finding. For the latter, we use a certified upper bound on the supremum of the target polynomial, obtained from grid samples through the Markov inequality; to our knowledge, such a certificate has not previously been used to normalize QSVT targets.
The article is structured as follows. Section II summarizes how the LCU 1-norm, the features of and the input state determine the success probability. Section III presents the numerical results on the Hubbard model: the computational setup (Sec. III A), LCU (Sec. III B), qubitization, including degree selection and the application to quantum Krylov (Sec. III C), and QSVT (Sec. III D). We conclude in the last section.
Summary of main findings
This section collects the analytical results that organize our findings; the numerical evidence is given in Sec. III. The three constructions differ in encoded function, implementation primitive and normalization (Table I). Within Eq. (13), the success probability then depends on the normalization (Sec. II A), on the features of and the system size (Sec. II B), and on the input state (Sec. II C).
Dependence of the success probability on the LCU 1-norm
We consider a Pauli decomposition as in Eq. (3), and use the notations above, together with the spectral norm of (shifted if necessary),
For a fixed input state as in Eq. (12), the success probability of a general block-encoding [Eq. (1)] increases as the renormalization factor (which in this general setting is not necessarily the LCU 1-norm) approaches the spectral norm of [Eq. (14)]. Replacing the LCU 1-norm [Eq. (7)] by the tighter therefore provides an upper benchmark for the achievable success probability [24]. The corresponding success probabilities under the two renormalization choices are
where are the eigenvalues of before renormalization. This leads to:
A standard technique is to pin the spectral maximum to zero [16]:
After this shift all eigenvalues lie in and , the spectral norm of over the full Fock space. For the Hubbard model, at weak coupling, but beyond a crossover ( for , between and for ) the global minimum lies in a sector with fewer electrons, which avoids the double-occupancy cost, so that . Since all input states belong to a single particle-number sector, the normalization could in principle be tightened by symmetry-adapted shifts that leave this sector unchanged, such as the block-invariant symmetry shift of Ref. [31]. The spectral norm is the smallest normalization compatible with , leading to . We thus have and iff (up to a phase).
The PREP-SELECT construction [Eq. (6)] related to the LCU block-encoding specific form, however, constrains the usage of the LCU 1-norm, i.e., of the shifted decomposition, because the PREP operator must be unitary. The physically realized success probability is therefore always
where the first factor, , is the loss due to the LCU 1-norm, and the second, , is the success probability that a block-encoding normalized by the spectral norm would reach; it depends only on the input state. Improving the success probability can only be achieved by reducing or by the choice of .
For qubitization [Eq. (8)], the realized value uses the LCU 1-norm, ,
Unlike the LCU case, the LCU 1-norm does not affect the qubitization success probability in a clearly predictable way because is nonlinear. The same holds for the QSVT success probability. For QSVT, with target polynomial and scaling factor , the implemented polynomial is , giving
As with qubitization, is nonlinear, so the renormalization does not affect the QSVT success probability in a clearly predictable way. In addition, QSVT introduces its own scaling factor
| Property | LCU | Qubitization | QSVT |
| Encoded function | ( real, definite parity) | ||
| Primitive | PREP-SELECT | Walk operator | QSVT phase sequence |
| Main control parameter | LCU 1-norm | Degree | Polynomial and scaling |
| Success probability |
Table 1. Comparison of the block-encoding constructions considered in this work.
required for on ; any bound looser than the supremum reduces the success probability as (Sec. III D).
In most of the remaining analysis, we work with the shifted and normalized Hamiltonian, whose eigenvalues lie in . This one-sided spectrum simplifies the analysis of the Chebyshev transformations and provides a convenient setting in which to derive bounds of the success probability.
Dependence of the success probability on system features
Beyond the choice of normalization, the features of and the system size affect both the spectral distribution and the normalization itself.
In the Hubbard model, the important feature of is the interaction strength. When it grows, the coefficient 1-norm accumulates contributions from every term that the interaction activates, whereas the spectral norm tracks only the largest spectral gap. The bound of Eq. (18) therefore decreases with , from its free-fermion value (1 for , for , tending to at large ) to for every : at large , while (Sec. III B). A central and initially counterintuitive finding concerns the dependence on system size: for the Hubbard systems and structured input states considered, the success probability shows no systematic decay with system size, both for LCU (Sec. III B) and QSVT (Sec. III D 4) block-encodings. Although increases with system size, the spectral distribution of the input state changes with it, and these two effects compensate: for the HF input state, settles onto a plateau rather than decaying toward zero. In the Hubbard model this plateau is reached already at : the success probability separates most sharply between and in the intermediate-correlation crossover, while the curves for are nearly indistinguishable and converge to the same large- value (Figure 1(b)).
Figure 1. LCU success probability versus (axis scaled as ). (a) , for the half-filled ground state (green) and the HF state (red): exact value (lines) and compiled PREP-SELECT circuit sampled with (open markers). The dashed line is , reached by only for , where the global minimum of lies at half filling. Blue: random input states (mean standard deviation over 200 states, individual states shown as dots). In the circuit simulations the input state is injected directly as the initial statevector of the simulator. (b) HF input state for – (color): (solid, left axis) and HF–ground-state (GS) overlap (dashed, right axis, log scale). The dash-dotted line marks the large- limit .
Dependence of the success probability on the input state and ground-state overlap
The input state itself plays a role that differs between the LCU and qubitization block-encodings. For the LCU block-encoding, the success probability is maximized by the eigenvector , which after the spectral shift carries the eigenvalue of largest magnitude: for every normalized . Within the half-filled sector the maximizer is the ground state , which reaches the bound when and lies slightly below it otherwise (Sec. III B). For qubitization, the state dependence is qualitatively richer. Writing , so that , and using , the qubitization success probability becomes
Its average over degrees is therefore
since unless is a multiple of ([32, 33]). The input state controls the fluctuations around this average. Writing , the variance over is for distinct , so the inverse participation ratio directly sets the amplitude of the oscillations. A state with broad spectral support, e.g., a random state, for which , remains close to , whereas a state concentrated on a few eigenstates (large ) explores a much broader range of values even at large . This oscillation makes the degree an additional lever: for concentrated input states, favorable degrees can be identified from a few dominant spectral components, or predicted from shallow-degree data without classical diagonalization (Sec. III C 1). In the Hubbard model, the HF input state exhibits such a concentrated spectral structure across the system sizes studied, whereas a random state has broad spectral support.
The success probability should also be distinguished from the fidelity of the input state, i.e., its overlap with the ground state. The fidelity measures alignment with a single eigenvector, whereas is a weighted average over the whole spectrum. As a result, is quasi-independent of the fidelity of the HF input: it plateaus with system size while the overlap keeps falling (Sec. III B). This differs from filtering-based ground-state preparation, where the success probability is set by the ground-state overlap [13].
| Quantity | Setting |
| Model | 1D Hubbard chain at half filling |
| Hopping | |
| Interaction | varied through |
| System size | –14 sites |
| System qubits | |
| LCU terms | |
| Spectral shift | |
| LCU normalization coefficient | 1-norm |
| Input states | HF, ground state, random |
| Qubitization | |
| QSVT | definite-parity Chebyshev targets |
| Largest system | 28 system qubits + 7 ancilla = 35 qubits |
| Validation | Dense matrix for ; matrix-free beyond |
Table 2. Summary of the numerical setup used throughout the study.
Success probability in resource estimation
In a direct postselection protocol, the shot overhead per accepted outcome is , and when the block-encoding is applied repeatedly, e.g., to the states spanning a Krylov subspace, this overhead accumulates over the course of the algorithm [34, 35, 36]. Amplitude amplification and its oblivious and fixed-point variants reduce the number of repetitions to [37, 38, 39], at the cost of deeper circuits. A method with shallower circuits but a lower success probability may therefore be more costly overall than a deeper one with a higher acceptance probability, so the success probability should be reported alongside circuit depth, gate count and qubit count, which are the quantities usually estimated [27, 40, 41].
Numerical results
We now turn to the numerical characterization of the success probability for the three methods considered here: LCU, qubitization and QSVT. As a controlled testbed, we use the one-dimensional Hubbard model. This model is well suited for this analysis: it is amenable to exact diagonalization for validation, its correlation strength is tunable through a single ratio, and it admits known analytic limits against which the success probability can be checked.
The Hubbard model and computational setup
We study the one-dimensional Hubbard model on a chain of sites at half filling [42, 43, 44, 45],
where is the nearest-neighbor hopping amplitude, is the on-site interaction strength, and are fermionic creation and annihilation operators, and
is the occupation operator. The ratio controls the crossover from the weakly interacting regime () to the strongly correlated Mott insulating regime with localized electrons (). Throughout this work, we set and vary .
We map the fermionic operators to qubits using the Jordan–Wigner transformation [46], with the spin-up orbitals ordered first. For the nearest-neighbor hopping terms, the Jordan–Wigner strings cancel between adjacent sites, yielding
This decomposition contains Pauli strings, from which the LCU 1-norm is obtained directly. We use the spectral shift of Eq. (17), so that the normalized eigenvalues lie in .
The PREP operator loads the amplitudes onto an ancilla register of width using a Grover–Rudolph binary tree of rotation angles constructed from partial sums of the coefficient distribution [47]. The sign factors are incorporated into SELECT rather than PREP. SELECT applies each signed Pauli string controlled on the ancilla index . Each term is implemented as a multicontrolled Pauli controlled by the ancilla index, with the control complexity determined by the ancilla width . The compiled PREP-SELECT-PREP circuit is validated at two levels. First, for , where the dense Hamiltonian remains computationally accessible, the projected circuit block-encodes with the explicitly constructed to machine precision (). Second, beyond this range, the exact HF success probability, evaluated matrix-free by applying term by term to , is compared with the shot-based estimate , i.e., the fraction of shots in which the ancilla register is measured in when the compiled circuit is applied to ; the two agree within the binomial standard error , with , which validates the matrix-free implementation used for . The numerical setup is summarized in Table II.
LCU success probability
Ground state as input state
The LCU block-encoding success probability obeys the state-independent upper bound in Eq. (18), which is controlled entirely by the ratio with , and two limits fix its range. At , the spectrum is symmetric and the hopping strings contribute to the 1-norm, while the constant introduced by the shift contributes :
For the two scales coincide () and , but for larger chains the hopping strings do not all saturate the operator norm simultaneously and the bound falls below unity: and for and . These values converge to a constant at large : at , with , so that , and , giving
In the strong-coupling limit the two scales separate. For , the highest-energy configuration is the fully doubly occupied state, which gives , while is negligible on the scale of . For the shifted Pauli decomposition of Eq. (26), the coefficients are:
and therefore
Here the and terms contribute and respectively, while the constant term, before shifting, contributes in magnitude after the spectral shift, since sends it to . The limit is therefore independent of both and . The decrease of the bound with , from its free-fermion value to , is the decomposition overhead of the 1-norm: the Pauli strings per site partially cancel in the operator norm but count additively in . Unlike the spectral norm, the 1-norm depends on the orbital representation used for the Pauli decomposition, so that can be increased a priori by optimizing this representation [29]; the site and molecular-orbital bases are compared below. After the spectral shift, the state of lowest energy carries the eigenvalue of largest magnitude of , , and therefore saturates the bound. The half-filled ground state saturates it only when , i.e., for () and (). Beyond, falls slightly below , by at most for (minimum at for ), and returns to it at large , where and are both against . As a consistency check, Figure 1(a) compares, for , the success probability computed from with the one measured on the compiled PREP-SELECT circuit, for the half-filled ground state and for the HF state; the two agree, confirming that the circuit realizes the 1-norm normalization.
HF as input state
We use the HF input state , taken here as the single Slater determinant minimizing the energy for the noninteracting problem [48]. In the site basis it is a superposition of computational basis states. At the HF approximation is exact (), so , which equals 1 only for (Eq. (27)). For , the exact ground state acquires correlations beyond a single Slater determinant [43]. Expanding in the exact eigenbasis of Eq. (12) (with for once correlations make the HF input state different from the exact ground state):
The difference therefore reflects electron correlation, but it is not identical to the loss of ground-state overlap: it is a spectrally weighted measure of how the HF spectral weight is distributed away from the extremal eigenvalue.
In order to study the effect of the basis on the success probability, we also computed the same metric after a change of basis from the site basis to the molecular-orbital (MO) basis. In the MO basis, the HF state is represented as a single computational-basis occupation string (e.g., for ), requiring only single-qubit gates for state preparation. However, this simplification does not improve LCU success probability, because the relevant cost is controlled by the Hamiltonian decomposition rather than by state-preparation complexity alone. In the site basis the interaction is local, with fewer Pauli strings contributing to the 1-norm. The orbital rotation to the MO basis introduces additional nonlocal terms with no site-basis counterpart, so the MO interaction has more terms and we have , consistent with the observation that localized orbitals reduce the 1-norm of molecular Hamiltonians [29]. Since is basis independent:
Thus, for the success probability considered here, the optimal basis is not necessarily the one that minimizes state-preparation complexity, but rather one that minimizes the ratio .
Overlap between the ground state and the HF state
Unlike the overlap , which depends only on the ground-state component of , of Eq. (30) is a second moment over the whole HF spectral distribution. As increases, the interaction inflates relative to : decreases, compressing all normalized eigenvalues uniformly. The success probability is therefore affected not only by the loss of ground-state weight but also by the rescaling of the entire spectrum induced by the normalization. The two quantities can therefore differ substantially: in Figure 1(b) we can see that already at , the HF state retains a substantial overlap with the exact ground state, yet has dropped to .
Since the shot overhead scales as , this is a more severe requirement than the overlap alone would suggest. More generally, the success probability is quasi-independent of the fidelity of the input state: at large , plateaus at – for , while the HF–GS overlap keeps falling with (Figure 1(b)). For our purposes, this means that the shot overhead of the LCU block-encoding with a HF input remains bounded, over all system sizes studied (), even in the strongly correlated regime where the HF state becomes a poor approximation of the ground state, while the bound itself stays bounded away from zero in both limits, tending to at for large and to for every as . The success probability therefore does not penalize the use of a simple HF input state in larger systems; conversely, it cannot serve as a proxy for the fidelity of the input state, which must be assessed separately.
Qubitization success probability
Whereas LCU block-encoding applies directly, qubitization realizes the Chebyshev transformation . The corresponding success probability is therefore degree dependent:
Writing each eigenvalue as thus
the Chebyshev identity turns Eq. (32) into a weighted sum of oscillating terms,
Two features of Eq. (34) are particularly relevant to the analysis that follows. First, as increases, the LCU 1-norm grows faster than the spectral norm, compressing the normalized spectrum into , which tends to at large (Sec. III B). Second, at fixed the probability oscillates with : a single term of Eq. (34) vanishes when
so can become small when the dominant spectral components lie near such nodes. It is this second feature that might make the choice of degree an operational lever. At the Chebyshev transformation is the identity, , so
for every input state and every : the LCU success probability is the slice of the qubitization framework. The features specific to qubitization (oscillation with , nodes, and the resulting freedom in choosing the degree) emerge for , and make an additional feature that affects resource estimation: different degrees of the same walk can have substantially different shot overheads.
Selecting the Chebyshev polynomial degree
Because oscillates with , a blindly chosen degree can fall near a node, as expressed in Eq. (35), where the success probability can become very small. For the HF input state, whose spectral weight is concentrated on a small number of eigenstates, this raises a practical question: can a favorable degree with respect to the success probability be selected in advance, without having to scan many degrees and retain the best one? This question is relevant whenever the degree is not fixed by the algorithm. The most direct application arises when the target accuracy only imposes a minimum degree , as is generic for polynomial methods whose degree is set by the spectral gap and the required precision [13], while the Chebyshev degree itself remains free above this threshold:
since varies strongly between neighboring degrees, a slightly deeper circuit can reduce the shot overhead substantially. For instance, for at (Figure 2), increasing the degree from to raises from to , i.e., a fourfold reduction in shot overhead at the cost of a single additional walk step. A second, more specific application is the construction of a Krylov space from a noncontiguous set of degrees, where the degrees themselves are free parameters; we illustrate it in detail in Sec. III C.2. In both cases, identifying favorable degrees without scanning them all, which would itself cost shots at every degree, is operationally useful. To this end, we propose below two inexpensive strategies to identify, a priori, Chebyshev degrees with a high success probability.
Figure 2. Qubitization success probability as a function of the Chebyshev degree at for the HF input state and – sites (color as in Figure 1(b) and Figure 10). Lines and dots show exact values, computed without sampling from the matrix-free action of (Sec. III A). Open triangles show sampled-circuit estimates with , available for () and (); their binomial standard deviations () are smaller than the markers. The sampled estimates agree with the exact values within two binomial standard deviations (rms deviation ). The dotted black line marks the long-degree average . The oscillatory dependence on produces degrees with both high and near-vanishing success probabilities.
We quantify the effective number of eigenstates contributing to the input state through the participation ratio
Recall from Eq. (12) that while , so that . The participation ratio is close to 1 when the weight is concentrated on a few eigenstates, giving a few dominant frequencies and strong coherent oscillations in , and large when the weight is spread over the spectrum, in which case the oscillations average out over . Once the dominant pairs are known, Eq. (34) determines for every degree, allowing the optimal degree to be identified without executing the corresponding deep circuits. Writing for the selected degree and for the median of over the considered degree window, we use as the figure of merit. The median represents the success probability expected from a degree chosen without spectral information, so the ratio measures the gain brought by the selection strategy. The largest achievable value of this ratio is , with over the same window; we call the oracle optimum, since reaching it requires knowing at every degree. All results below use the window and the HF input state for and , i.e., 12 cases.
The spectrum-informed strategy keeps only the eigenstates with the largest weights , whose index set we denote , and optimizes the resulting partial sum,
It requires the full eigendecomposition and therefore serves as a spectrum-informed benchmark rather than a practical spectrum-free protocol. With , the selected degree lies within 5% of the oracle optimum in 11 of the 12 cases and reaches on average 98% of , showing that a small number of spectral components captures most of the relevant -dependence.
The spectrum-free strategy uses no spectral input. It requires only at shallow degrees , fits weights and angles to those points by nonlinear least squares against the model in Eq. (34), and extrapolates the fitted sum to select
Because is a weighted sum of a small number of squared oscillatory components, a window of shallow circuits can constrain their frequencies and amplitudes, and the fitted model can predict a favorable deeper degree without classical diagonalization. We use and , so that the fitted parameters are fewer than the data points. In the results below, the shallow values of are computed exactly; the effect of shot noise on the fit is not assessed here.
For the HF input state, the median-degree baseline is (between 0.49 and 0.51) in all cases. The spectrum-informed strategy raises the per-circuit success probability to 98% of the oracle optimum on average, corresponding to a gain of 1.7–2.0, nearly independently of the participation ratio over the range studied (PR –14). The spectrum-free strategy reaches 91% of the oracle optimum on average, with gains of 1.4–2.0, and never selects a degree below the median (Figure 3). Its performance depends on the length of the shallow window and on the number of fitted components. With , which allows at most components, the gain ranges from 0.84 to 2.0: when nearby frequencies are not resolved, the extrapolation identifies the wrong revival and can select a degree below the median. The required number of components also grows with the fitting window, since a longer window resolves more of the beating between frequencies: at , gives a minimum gain of only 0.46, whereas gives 1.4.
Figure 3. Degree-selection performance for HF input states at and , over the window . (a) Success probability at the degree selected by the spectrum-informed strategy (blue, Eq. (38), ) and the spectrum-free strategy (red, Eq. (39), , ), compared with the median-degree baseline (grey) and the oracle optimum (black horizontal lines). Vertical lines separate the three values of . (b) Gain as a function of the participation ratio for the spectrum-informed (blue circles) and spectrum-free (red triangles) strategies; the dashed line marks no gain.
In the two settings identified at the beginning of this section, degree selection can therefore be useful. The tests above select the best degree over the full window ; restricting the search to , or ranking degrees to build a noncontiguous Krylov space (Sec. III C 2), applies the same predicted to a subwindow and was not tested separately. The spectrum-informed strategy reliably locates near-optimal degrees but requires the dominant eigenpairs. The spectrum-free strategy requires only shallow-degree data and, with and , consistently improves on a blind choice for the HF states studied here; its main benefit is to avoid near-node degrees at which a full circuit execution would have a near-vanishing acceptance probability.
Application to quantum Krylov method
The success-probability analysis becomes operationally concrete when the qubitized walk is used as the primitive of a quantum Krylov method. The Krylov subspace is spanned by the vectors
and the ground-state energy is estimated from the regularized generalized eigenvalue problem , with the Gram (overlap) matrix and the Hamiltonian projected onto the -dimensional Krylov subspace.
The Krylov vectors of Eq. (40) are not normalized and thus cannot be prepared directly as quantum states. Applying after walk steps and postselecting the ancilla register on would leave in the system register with probability . Instead, Kirby et al. estimate only the Chebyshev moments [34, 49],
each as the expectation value of an observable, and and are then assembled classically [34] as
A Krylov space of dimension therefore requires the moments up to . In such a moment-based scheme no postselection is required. However, the success probability directly affects the resources (number of shots) needed to reach a given precision, as we now show.
The qubitization success probability of Eq. (32) can be rewritten, using Eq. (42) with , as
Degrees with small produce Krylov vectors of small norm, whose moments are also small, . As is estimated from binary outcomes (Appendix A), its standard deviation is , and that of is . Resolving the squared norm of to a relative precision thus requires
so that the overhead remains even without postselection: not as discarded shots, but as the shots needed to resolve a Krylov vector of small norm with a controlled precision.
The scheme of Kirby et al. [34] is based on moment measurements, each moment being estimated without a control qubit, by preparing the walk state and measuring for even and for odd .
Our scheme is also based on moment measurements, rather than on postselection as in the previous sections, which makes it directly comparable with that of Kirby et al. [34]. The only difference is that we measure each moment with a Hadamard test [50, 51], as commonly done for overlaps in quantum subspace methods [8, 9, 10, 11]; the circuit is shown in Figure 4 and its readout is derived in Appendix A.

Figure 4. Hadamard-test circuit for the Chebyshev moment . The test qubit controls applications of the walk operator on ; only the test qubit is measured, and from the probabilities of its two outcomes, the sign coming from the reflection convention of our implementation. The block-encoding ancillas are never measured, so no shot is discarded.
The two schemes offer different trade-offs between circuit depth and readout cost (Table III). In terms of depth, the scheme of Kirby et al. requires only uncontrolled walk steps, i.e., a maximum depth of instead of controlled steps for our Hadamard test scheme.
Table III. Readouts of the Chebyshev moment : number of walk steps, counted outcome, its probability, and number of shots carrying information, out of shots in total ( for term ). The probabilities of the two readouts of Kirby et al. are derived in Appendix A.
In our Hadamard-test scheme, every shot contributes to the estimate of , for even and odd alike, with standard deviation and without any discard. We prefer this trade-off here. The number of shots is already set by the success probability through Eq. (44), which can be large for degrees with small . The term-by-term readout of the odd moments, which make up half of the moments required, never needs fewer shots than the Hadamard test for the same error, and needs at least times more when is spread evenly over the terms (Appendix A, Eq. (58)); this cost comes on top of Eq. (44). The Hadamard test avoids this additional cost at the price of a controlled walk and twice the circuit depth.
The results of Figure 5 and Figure 6 use four shot budgets per moment. For and , the Hadamard-test circuits are sampled. The larger budgets, and , are too costly to sample in simulation; for these, the exact moments are perturbed by Gaussian noise of standard deviation . In the regularized solution of the generalized eigenvalue problem, directions of with eigenvalue below a threshold are discarded [6, 34, 35]. Without noise we use a fixed threshold . With noise, is selected for each among 40 logarithmically spaced values between and , restricted to , as the smallest value within the widest plateau of the extracted energy, which makes the result insensitive to the exact cut. Krylov vectors with therefore cannot be resolved and contribute to the ill-conditioning of the overlap matrix. For the present calculation, the energy error decreases rapidly with Krylov dimension until statistical uncertainty becomes dominant, after which the convergence reaches a shot-limited plateau. The plateau level tracks the nominal moment-noise scale , and increasing the shot budget lowers this plateau, as shown in the upper panel of Figure 5.
Figure 5. Finite-shot convergence and success-probability variation in the quantum Krylov calculation for the , Hubbard model with a HF input state. Upper panel: Ground-state energy error versus Krylov dimension for and (sampled Hadamard-test circuits) and and (Gaussian moment noise ), together with the noiseless curve. Dotted lines mark , in the color of the corresponding curve. Lower panel: Success probability of the highest-degree moment required at each Krylov dimension.
Figure 6. A priori construction of the Krylov space from degrees with high success probability (), for , , compared with the standard contiguous construction. (a) Ground-state energy error versus Krylov dimension , where is the Krylov estimate with basis vectors and the exact ground-state energy, for the contiguous (blue) and selected-degree (green) constructions, noiseless (dashed) and with finite-shot noise for , emulated by Gaussian noise of standard deviation on the moments (solid); the dotted line marks . (b) Condition number of the overlap matrix versus for each construction (noiseless). The dash-dotted lines, nearly coincident for the two constructions, mark with : above them, the smallest eigenvalue of falls below the threshold and the corresponding direction is discarded. The dotted line marks the inverse of the double-precision machine accuracy, , beyond which the smallest eigenvalue of is at the level of round-off.
This motivates asking whether the Krylov space can be constructed using degrees with sufficiently large success probability. In Figure 6, we therefore construct the Krylov space a priori from degrees satisfying . The selected-degree construction keeps the condition number below that of the standard contiguous construction for , before both reach the round-off limit, and the improvement in convergence is already visible in the noiseless calculation. The corresponding finite-shot calculations retain the same trend. This improvement comes at the cost of a larger maximum Chebyshev degree and therefore deeper circuits. Thus, the success probability is not only a shot-overhead indicator for individual moments; it also provides a direct diagnostic for identifying Chebyshev degrees whose corresponding Krylov vectors may contribute to poor conditioning.
QSVT success probability
QSVT generalizes the qubitized walk from a single Chebyshev polynomial to a broad class of polynomial transformations satisfying the required parity and boundedness conditions [3, 20], implemented by the phase sequence of Eqs. (9) and (10). QSVT introduces a qualitatively different normalization problem: unlike LCU and qubitization block-encodings, where the scaling is inherited from the LCU 1-norm, the polynomial transformation introduces an additional scaling factor that directly affects both the success probability and the feasibility of phase synthesis.
We write the target polynomial, before scaling, in the Chebyshev basis,
where is its degree () and the real coefficients vanish whenever and have different parity, so that has the definite parity of . Let denote the scaling factor used to obtain the QSVT-feasible polynomial . The resulting success probability is
For a given target polynomial and input state, the numerator is fixed, so the scaling factor directly controls the QSVT success probability. It is constrained by the feasibility condition [3, 20], which
requires
For a fixed target polynomial, the success probability is therefore maximized by choosing as close as possible to from above, so that feasibility is maintained. Estimating or certifying is thus central to the analysis below. Unless stated otherwise, the target polynomials are randomly generated in the Chebyshev basis with definite parity.
Choice of the polynomial scaling factor
Several constants bound from above, and they form an ordered chain
where and are the maxima of sampled on a coarse (4000 points) and a fine (200000 points) grid, denotes a numerical evaluation of , obtained by solving and evaluating at the resulting stationary points and the interval endpoints, is a certified bound derived below, is the sup norm of the coefficient series on the unit circle, and is the coefficient -norm. The inequalities involving and are empirical properties of the sampled grids, not certified bounds: they provide lower estimates of the supremum because they only evaluate at discrete points. Consequently, normalizing with an undershooting grid estimate can produce a polynomial that exceeds unit magnitude between grid points. The three quantities to the right of provide valid upper bounds.
The maximum of on the closed interval is attained either at a critical point, where , or at an endpoint . Using Eq. (45) and with the second-kind Chebyshev polynomials, the derivative is
The stationary points of in are obtained numerically as the real roots of , computed as the eigenvalues of its companion matrix. Evaluating at these points and at the endpoints gives the numerical estimate of without requiring a dense grid. Unlike the Markov construction below, this critical-point procedure is not a certified upper bound.
Normalization by the infinity norm is standard in QSVT, and the numerical practice is to estimate it by grid sampling. A grid maximum undershoots the true supremum, however, and so gives no guarantee of the feasibility condition . The grid estimate can be corrected upward into a certified bound by accounting for the largest rise the polynomial can hide between two nodes. Let be the true maximizer, . With nodes spaced apart, lies within of some node , and by the mean value theorem [52], there is a between and with
where we used the triangle inequality, , which holds because is itself one of the nodes over which is taken (the grid includes both endpoints ), and . The derivative is bounded by the Markov inequality [53, 54], which holds for any polynomial of degree on , with the degree of the target polynomial of Eq. (45):
Substituting into Eq. (50) and solving for gives
valid whenever , which requires a grid sufficiently fine relative to the polynomial degree. Unlike , Eq. (52) provides a provable upper bound and therefore guarantees feasibility.
Since the numerator of Eq. (46) is fixed by the target, the choice among the constants of Eq. (48) directly sets , as illustrated in Figure 7(a) for a fixed degree-7 target. The certified Markov bound gives , only slightly below the tight value , whereas the loose bound reduces the success probability to . Therefore, for this example, a looser normalization alone produces a increase in the shot overhead. This ordering persists across the correlation-strength sweep considered here: Figure 7(b) shows the same separation between , , and the looser and choices across the full range studied. The gap between the tight and loose constants is expected to widen with the polynomial degree. and depend only on the Chebyshev coefficients of the target and accumulate their magnitudes, e.g., for constant coefficients, whereas can remain much smaller owing to cancellations between Chebyshev terms of different order at each (Sec. III D 3). In contrast, the classical cost of a tight estimate is independent of the system size: requires the roots of , i.e., the eigenvalues of a companion matrix, at cost , and requires evaluating on a grid with , i.e., nodes at cost each, hence . This one-time classical cost is negligible compared with the shot overhead incurred at every execution of the circuit with a loose normalization, so the certified bound should be preferred in practice.
Figure 7. QSVT success probability and the cost of the normalization constant, for the fixed degree-7 target and an HF input state. (a) Success probability at for each normalization choice, with the value of under each label. The unscaled numerator is ; , and (equal to for this target) give , and , respectively. (b) Success probability as a function of (horizontal axis scaled as ; dotted line: , the value used in (a)). The curves for (dashed) and (dotted) coincide with , and the curve for (dashed) coincides with . The tight estimates and form the upper group, while the looser bounds and give success probabilities smaller by a factor across the range studied.
Effect on angle finding
The choice of represents a success probability trade-off, and it also determines whether phase finding is feasible and how robustly the numerical solver converges. The QSVT phase factors implementing the scaled operator are found by the Newton iteration of the sym_qsp solver of pyqsp, following the phase-factor evaluation approach of [22, 23], whose numerical conditioning depends on the distance between the normalized target and the feasibility boundary . Three regimes emerge, separated by the sign and size of the margin .
When , the scaled polynomial violates the necessary boundedness condition , so it is not a feasible QSVT target on the full interval. In the numerical solver, this manifests as failure to converge to the required residual; we therefore reject phase sequences whose residual exceeds . This is the case for , about 5% below the supremum: phase finding does not converge at any tested degree (–, Table IV), and for the degree-5 target the realized state keeps an infidelity whatever the solver tolerance (Figure 8). When is obtained from a grid estimate and chosen with only a grid-scale margin relative to , phase finding can be fragile. The grid estimates and are not certified: although they often lie extremely close to the true supremum, they can undershoot it when a polynomial maximum falls between sampled nodes. In such cases, the nominal margin becomes negative and the solver can stall or converge to an inaccurate transformation.
| iter | residual | iter | residual | iter | residual | iter | residual | |
| 2 | – | 20 | 20 | 9 | ||||
| 3 | – | – | 20 | 8 | ||||
| 4 | – | 20 | 20 | 8 | ||||
| 5 | – | – | 20 | 7 | ||||
| 6 | – | 20 | 20 | 7 | ||||
| 7 | – | 20 | 20 | 7 | ||||
| 8 | – | – | 20 | 7 |
Table IV. Phase-finding iterations and final residual errors of sym_qsp as a function of target degree for the normalization constants considered (same targets as Figure 8 for ). The infeasible never reaches the required residual. The grid-based normalization fails to reach it at , and , reflecting its lack of a certified margin above . The certified converges at all tested degrees with a small positive margin.
Figure 8. State infidelity of the realized QSVT circuit versus the tolerance requested from the pyqsp phase solver, for the normalization constants , , and (the last two curves coincide). Degree-5 target , , , HF input state. The dashed curve () is infeasible. The horizontal dotted line marks the acceptance threshold on the state infidelity.
If the margin is small but positive, phase finding is both fast and accurate. The certified clears the supremum by about one percent and converges in 7–9 Newton iterations to a residual of order or below at every degree tested; the numerical estimate converges in a fixed 20 iterations to . Figure 8 shows how the choice of sets the precision of the realized state as the tolerance requested from the phase solver is tightened. Down to a tolerance of , , and , which all round to 0.79, give the same state infidelity. Beyond this point the two grid estimates saturate, at for and for , consistent with a slight undershoot of , whereas keeps improving and reaches at a tolerance of . The margined constants reach a higher precision at much looser tolerances: once the tolerance reaches –, and machine precision () from , for , and . With an acceptance threshold of on the state infidelity, the two grid estimates never qualify but already qualifies from . A smaller scaling factor therefore gives a higher success probability at the cost of precision on the phases, and hence on the prepared state. resolves this trade-off favorably: for this target, its success probability is only a factor below that of , against for and , while it reaches the same machine-precision fidelity as the looser bounds. For the targets studied here, is therefore the operationally preferred choice: it is the tightest certified bound considered, preserving a high success probability while providing a small positive feasibility margin that ensures both the convergence of phase finding and an accurate state preparation. This result applies to the compilation of any QSVT circuit, since normalizing the target polynomial is a compilation step common to all QSVT applications. The Markov certificate turns a cheap grid estimate into a provable bound that guarantees the compiled phase sequence implements the intended polynomial, at a cost of a few percent in success probability for the targets studied here, while reaching machine-precision fidelity at solver tolerances several orders of magnitude looser than the tight numerical estimate.
Dependence on polynomial degree and coefficient growth
The QSVT success probability depends on the polynomial degree through the interplay between the normalization , which enters as , and the spectral response . We index the target by its degree , since we study how the success probability depends on , and write Eq. (45) as
The way scales with is then governed by how fast the coefficients grow. In Krylov-type applications, the Lanczos polynomials expressed in the Chebyshev basis have coefficients that grow with degree [7]; we therefore consider polynomial and exponential growth laws to bracket this behavior. Consider first coefficients that are constant or grow polynomially, with . Two sums then control the success probability. Since and , the normalization is reached at , where for every , so that all terms of add coherently: . For a spectral weight spread uniformly over the angles , the Chebyshev polynomials are orthogonal on average [55], so the cross terms of cancel and only the squared coefficients remain: . The terms of thus add coherently in the normalization but
incoherently in the numerator, so that
independently of : polynomial coefficient growth changes the normalization but not the envelope of the success probability. For the concentrated HF input state the decay is faster than this flat-spectrum estimate: in Figure 9(a) and 9(b) (, ), a power-law fit for shows that the upper envelope of decays as , with for constant coefficients and for both linear (not shown) and quadratic growth. The exponent thus depends only weakly on the coefficient profile, indicating that the decay is set by the input-state spectrum. For exponentially growing coefficients, $a_k=r^k with , the highest-degree terms dominate both the normalization, , and the polynomial itself: the normalized polynomial is a combination of its last few Chebyshev terms, with weights decaying as . As a result, the success probability oscillates with around an approximately constant level, of order for (Figure 9(c)), even though grows by about 8 orders of magnitude. Exponential coefficient growth alone thus does not drive the success probability to zero. For generic random coefficient profiles, both the normalization and the spectral response fluctuate between realizations. The median success probability over draws decreases over the first degrees and then remains nearly constant at (Figure 9(d)).
Figure 9. QSVT success probability versus polynomial degree for four coefficient profiles, , , HF input state. Upper panels: , split by the parity of ; lower panels: normalization . All targets have the parity of , . (a) Constant () and (b) quadratically growing () coefficients: the upper envelope decays as , with and (dashed lines, fit for ). (c) Exponential coefficients (): grows by about 8 orders of magnitude, while oscillates without decaying. (d) Random targets: median over 40 draws (line) and interquartile range (band).
These observations bear on Krylov and Lanczos-based transformations, where high-degree polynomials can entail rapidly growing normalization [7]. A large normalization alone does not determine the success probability: the spectral response of the polynomial on the input-state spectrum matters equally. The precise interplay of coefficient growth, spectral structure, and Krylov convergence is problem dependent, so the success probability should be monitored alongside the Krylov dimension and polynomial degree.
Dependence on system size
The system-size dependence differs between the even and odd target families. Figure 10(a) and Figure 10(b) show the success probability across for system sizes to 10 at fixed odd- and even-degree targets. For the odd target the success probability rises with and orders regularly with system size, the curves bunching for ; for the even target it falls with and the curve sits above the rest. As for LCU (Sec. III B), the largest finite-size changes occur between the smallest systems, with no systematic decay of for . At small , the HF state is close to the ground state (participation ratio ), so that is set by the position of the normalized ground-state energy relative to the zeros of . At , , which equals for but for (Sec. III B). As increases, moves away from ; for it crosses the zero of the even target at between and , which produces the isolated low value of the curve at in Figure 10(b). For larger , starts beyond this zero and the dip is absent. The same mechanism, with the zero of the odd target at , produces the low value at in Figure 10(a).
Figure 10. System-size and interaction-strength dependence of the QSVT success probability for fixed target polynomials of odd and even parity, HF input state, – (color as in Figure 1(b)). (a) Odd-degree target . (b) Even-degree target ; the isolated low value of the curve at is discussed in the text. Lines show exact (matrix-free) values computed without sampling; triangles show sampled-circuit estimates (), which agree with them to within 0.01. The horizontal axis is scaled as . The two target families exhibit opposite trends.
Conclusion
We have investigated the success probability of block-encoding-based quantum algorithms and shown that, for a given encoded function of a Hermitian operator , it is jointly determined by the spectral distribution of the input state, the spectrum of , and the normalization. All numerical tests have been done on the Hubbard model at half filling, in which the spectral structure can be validated and the relevant quantities can be computed over a broad range of system sizes; we expect the mechanisms identified here to hold beyond this case, while the specific values are model dependent. This provides a common perspective on LCU, qubitization and QSVT block-encodings, in which the success probability can be written as , a quantity that can be analyzed independently and included in resource estimation.
For LCU, the success probability is constrained by the squared ratio between the spectral norm of the shifted Hamiltonian and the LCU 1-norm of its Pauli decomposition. Within this bound, the success probability depends strongly on the input state: the half-filled ground state nearly saturates it, whereas the HF input state generally does not.
Qubitization introduces the Chebyshev degree as an additional control parameter, and the resulting success probability oscillates with . For a fixed block-encoding and input state, different degrees can therefore give substantially different shot overheads. For the HF input state, this degree dependence is largely captured by a small number of dominant spectral components: a spectrum-informed truncation identifies favorable degrees from a few dominant eigenstates, while a spectrum-free model fitted to shallow-degree data predicts favorable deeper degrees without classical diagonalization.
For QSVT, the polynomial scaling factor provides a different form of control. For a fixed target polynomial and input state, the success probability scales as , so tighter normalization directly improves it. However, choosing close to the true supremum introduces a practical trade-off: an undershooting value is infeasible, while a barely feasible value places phase finding close to an ill-conditioned boundary. Among the estimates and bounds of compared here, the certified bound that we introduce for QSVT normalization, obtained from grid samples through the Markov inequality, provides the best compromise: it stays within about one percent of the tight value while leaving a positive feasibility margin for robust phase synthesis. For the Hubbard chain studied, the QSVT success probability decays with polynomial degree (upper envelope – for the HF input state), nearly independently of the coefficient growth for constant and polynomially growing coefficients, while exponentially growing coefficients prevent it from decaying despite a normalization that grows by orders of magnitude.
Across the three methods, the numerical results show that success probability does not have a single universal dependence on system size, interaction strength, or transformation degree. Instead, for each construction, its behavior reflects the combined effect of spectral structure, normalization and input state. In particular, for the Hubbard systems studied here, no systematic decay of the success probability toward zero is observed with system size (up to 35 qubits for LCU block-encoding), and for the HF input it is quasi-independent of the input state’s fidelity to the ground state.
Finally, the application to quantum Krylov illustrates why these observations matter. The moments required by a Krylov calculation are associated with different Chebyshev degrees and therefore with different values of . Even when the moments are measured without postselection, is the squared norm of the corresponding Krylov vector, so degrees with small require substantially more shots to be resolved to a given relative precision. Beyond this per-degree shot overhead, the success probability also serves as a construction criterion: selecting the Krylov space from degrees with high success probability improves the conditioning of the overlap matrix and the resulting convergence, at the cost of deeper circuits. The success probability therefore adds a cost that is not captured by gate count, circuit depth or qubit count alone, and should be reported as part of the resource estimation of block-encoding-based algorithms. Amplitude amplification [37] can reduce the number of repetitions from to , at the cost of additional applications of the block-encoding per run; the success probability therefore remains the quantity that sets the overhead, now in circuit depth as well as in repetitions.
Extending our numerical analysis beyond the one-dimensional Hubbard model, e.g., to molecules and larger many-electron systems, represents a natural way forward. Another important outlook is the application to quantum Krylov subspace methods, and in particular to our recent formulation [7], which requires a QSVT polynomial transformation without definite parity. Such a polynomial is typically implemented as a linear combination of its even and odd parts, at the cost of an additional normalization factor that can reduce the success probability by up to a factor of 4; the framework developed here directly quantifies this cost. Finally, the success probability of block-encodings used for solving linear systems [1, 2] and partial differential equations [4] remains to be evaluated.
Acknowledgments
We thank TotalEnergies for permission to publish this work, Keith Gray, Donny Cooper and Harry Zong for providing and maintaining the CPU and GPU computing resources used for the simulations, Henri Calandra and Jean-Patrick Mascomère for insightful discussions and comments, and Hadi Rammal for fruitful discussions and collaboration. This work was supported in part by the Maison du Quantique de Nouvelle-Aquitaine “HybQuant”, as part of the HQI initiative and France 2030, under the French National Research Agency (ANR) grant ANR-22-PNCQ-0002, by the PEPR Quantique under Grant No. ANR-23-PETQ-0006, and by the EUR Light S&T (PIA3 Program, Grant No. ANR-17-EURE-0027). Circuit simulations were performed with the Quantum Learning Machine (myQLM) software [56]. The authors used a large language model as an assistant for proofreading and editing parts of the text.
Readout statistics of the Chebyshev moments
This appendix derives the statistics of the three readouts of the Chebyshev moments compared in Sec. III C 2 and Table III: the Hadamard test used in this work and the two readouts of Kirby et al. [34]. Throughout, an outcome of probability occurs about times in shots, with a fluctuation of about , so that estimating itself to a relative precision requires shots; whether this cost appears depends on what is counted.
a. Hadamard test. A test qubit prepared in controls applications of on , and after a second Hadamard gate, its outcome probabilities satisfy
by Eq. (8), being real since is Hermitian. The projection onto that defines the block-encoding is therefore contained in the overlap with the initial state: the ancilla register is never measured, and every shot, with outcome , contributes to the estimate of .
b. Readouts of Kirby et al. Both start from the walk state
and use and [34].
c. Even . is measured by applying and recording if and otherwise. The probability of the outcome is
i.e., exactly the block-encoding success probability of the half-degree walk, using . Since , failures are not discarded but carry information on , and the error is , the same as for the Hadamard test.
d. Odd . is measured term by term [34]: for term , a layer of single-qubit Clifford gates maps to a diagonal operator, the ancilla and system registers are measured in the computational basis, and the shot returns the measured eigenvalue of if , and otherwise. Only the shots with , which occur with probability , carry information on term , so the relative error on its contribution scales as , where is the number of shots spent on that term. With the optimal allocation , the total cost for a given error on exceeds that of the even readout, in the worst case, by a factor , which lies between (a single dominant term) and (equal weights); grouping qubitwise commuting Pauli strings reduces to the number of groups. This overhead is not an artifact of the bounds. Writing for the mean outcome of a shot on term , with and , the variance per shot on term is , whereas that of the Hadamard test and of the even readout is , and
since, after expanding both squares, each cross term satisfies , which follows from and . The odd readout therefore never requires fewer shots than the Hadamard test for the same error on , and, since , it requires at least times more when for all .
The probability follows from the branch structure preserved by the walk, in which each ancilla state carries its own system state. As in , the signs of the coefficients are absorbed into the Pauli strings, so that with and . Suppose
which holds at . applies in branch , and projecting onto recombines the branches,
Applying restores the form of Eq. (59), with
By the Born rule, the probability of reading the ancilla in for odd is
Using , and , Eq. (61) is solved by
where , and are the Chebyshev polynomials of the second kind, as in Eq. (49). For , exactly. For ,
and, using , . For the illustrative case and , the probability of the branch decreases from 0.80 to 0.42 and 0.14 for , while that of the branch increases accordingly.
References
References
- [1]A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103, 150502 (2009).pubmed.ncbi.nlm.nih.gov/19905613
- [2]A. M. Childs, R. Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM Journal on Computing 46, 1920 (2017).DOI
- [3]A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2019) pp. 193–204.DOI
- [4]A. M. Childs, J.-P. Liu, and A. Ostrander, High-precision quantum algorithms for partial differential equations, Quantum 5, 574 (2021).DOI
- [5]M. Motta, W. Kirby, I. Liepuoniute, K. J. Sung, J. Cohn, A. Mezzacapo, K. Klymko, N. Nguyen, N. Yoshioka, and J. E. Rice, Subspace methods for electronic structure simulations on quantum computers, Electronic Structure 6, 013001 (2024).arxiv.org/abs/2312.00178
- [6]E. N. Epperly, L. Lin, and Y. Nakatsukasa, A theory of quantum subspace diagonalization, SIAM Journal on Matrix Analysis and Applications 43, 1263 (2022).
- [7]H. Rammal, A. Perrin, O. Ladhari, C. Dutreix, J. Messud, and M. Saubanère, Orthogonal quantum Krylov diagonalisation (2026), arXiv:2607.09476 [quant-ph].arxiv.org/abs/2607.09476
- [8]R. M. Parrish and P. L. McMahon, Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation (2019), arXiv:1909.08925 [quant-ph].arxiv.org/abs/1909.08925
- [9]N. H. Stair, R. Huang, and F. A. Evangelista, A multireference quantum Krylov algorithm for strongly correlated electrons, Journal of Chemical Theory and Computation 16, 2236 (2020).DOI
- [10]C. L. Cortes and S. K. Gray, Quantum Krylov subspace algorithms for ground and excited-state energy estimation, Physical Review A 105, 022417 (2022).DOI
- [11]K. Klymko, C. Mejuto-Zaera, S. J. Cotton, F. Wudarski, M. Urbanek, D. Hait, M. Head-Gordon, K. B. Whaley, J. Moussa, N. Wiebe, W. A. de Jong, and N. M. Tubman, Real-time evolution for ultracompact Hamiltonian eigenstates on quantum hardware, PRX Quantum 3, 020323 (2022).DOI
- [12]N. Yoshioka, M. Amico, W. Kirby, P. Jurcevic, A. Dutt, B. Fuller, S. Garion, H. Haas, I. Hamamura, A. Ivrii, R. Majumdar, Z. Minev, M. Motta, B. Pokharel, P. Rivero, K. Sharma, C. J. Wood, A. Javadi-Abhari, and A. Mezzacapo, Krylov diagonalization of large many-body Hamiltonians on a quantum processor, Nature Communications 16, 5014 (2025).DOI
- [13]L. Lin and Y. Tong, Near-optimal ground state preparation, Quantum 4, 372 (2020).
- [14]Y. Ge, J. Tura, and J. I. Cirac, Faster ground state preparation and high-precision ground energy estimation with fewer qubits, Journal of Mathematical Physics 60, 022202 (2019).arxiv.org/abs/1712.03193
- [15]Y. Dong, L. Lin, and Y. Tong, Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices, PRX Quantum 3, 040305 (2022).DOI
- [16]G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
- [17]A. M. Childs, R. Kothari, and R. D. Somma, Simulating sparse Hamiltonians with star decompositions, in Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science, Vol. 6519 (Springer, 2011) pp. 94–103.DOI
- [18]A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information & Computation 12, 901 (2012).
- [19]G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Physical Review Letters 118, 010501 (2017).DOI
- [20]J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021).DOI
- [21]J. Haah, Product decomposition of periodic functions in quantum signal processing, Quantum 3, 190 (2019).DOI
- [22]Y. Dong, X. Meng, K. B. Whaley, and L. Lin, Efficient phase-factor evaluation in quantum signal processing, Physical Review A 103, 024219 (2021).DOI
- [23]Y. Dong, L. Lin, H. Ni, and J. Wang, Robust iterative method for symmetric quantum signal processing in all parameter regimes, SIAM Journal on Scientific Computing 46, A2951 (2024).arxiv.org/abs/2307.12468
- [24]R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Physical Review X 8, 041015 (2018).DOI
- [25]V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Reiher, M. Roetteler, and M. Troyer, Quantum computing enhanced computational catalysis, Physical Review Research 3, 033055 (2021).DOI
- [26]J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R. McClean, N. Wiebe, and R. Babbush, Even more efficient quantum computations of chemistry through tensor hypercontraction, PRX Quantum 2, 030305 (2021).DOI
- [27]M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, Proceedings of the National Academy of Sciences 114, 7555 (2017).
- [28]D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization, Quantum 3, 208 (2019).DOI
- [29]E. Koridon, S. Yalouz, B. Senjean, F. Buda, T. E. O’Brien, and L. Visscher, Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum applications, Physical Review Research 3, 033127 (2021).DOI
- [30]I. Loaiza, A. Marefat Kham, N. Wiebe, and A. F. Izmaylov, Reducing molecular electronic Hamiltonian simu lation cost for linear combination of unitaries approaches, Quantum Science and Technology 8, 035019 (2023).
- [32]H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins, Mathematische Annalen 77, 313 (1916).
- [33]L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences (Wiley-Interscience, 1974).
- [34]W. Kirby, M. Motta, and A. Mezzacapo, Exact and efficient Lanczos method on a quantum computer, Quantum 7, 1018 (2023).DOI
- [35]G. Lee, D. D. Lee, and J. Huh, Sampling error analysis in quantum Krylov subspace diagonalization, Quantum 8, 1477 (2024).DOI
- [36]Z. Zhang, A. Wang, X. Xu, and Y. Li, Measurement-efficient quantum Krylov subspace diagonalisation, Quantum 8, 1438 (2024).DOI
- [37]G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum Computation and Information, Contemporary Mathematics, Vol. 305 (American Mathematical Society, 2002) pp. 53–74.DOI
- [38]D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating Hamiltonian dynamics with a truncated Taylor series, Physical Review Letters 114, 090502 (2015).pubmed.ncbi.nlm.nih.gov/25793789
- [39]T. J. Yoder, G. H. Low, and I. L. Chuang, Fixed-point quantum search with an optimal number of queries, Physical Review Letters 113, 210501 (2014).DOI
- [40]I. D. Kivlichan, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, W. Sun, Z. Jiang, N. Rubin, A. Fowler, A. Aspuru-Guzik, H. Neven, and R. Babbush, Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via Trotterization, Quantum 4, 296 (2020).
- [41]E. T. Campbell, Early fault-tolerant simulations of the Hubbard model, Quantum Science and Technology 7, 015007 (2022).DOI
- [42]J. Hubbard, Electron correlations in narrow energy bands, Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 276, 238 (1963).
- [43]E. Dagotto, Correlated electrons in high-temperature superconductors, Reviews of Modern Physics 66, 763 (1994).DOI
- [44]E. H. Lieb and F. Y. Wu, Absence of Mott transition in an exact solution of the short-range, one-band model in one dimension, Physical Review Letters 20, 1445 (1968).
- [45]F. H. L. Essler, H. Frahm, F. Göhmann, A. Klümper, and V. E. Korepin, The One-Dimensional Hubbard Model (Cambridge University Press, 2005).
- [46]P. Jordan and E. Wigner, Über das Paulische Äquivalenzverbot, Zeitschrift für Physik 47, 631 (1928).
- [47]L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions (2002), arXiv:quant-ph/0208112.DOI
- [48]A. Szabo and N. S. Ostlund, Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory (Dover Publications, Mineola, New York, 1996).
- [49]A. Weiße, G. Wellein, A. Alvermann, and H. Fehske, The kernel polynomial method, Reviews of Modern Physics 78, 275 (2006).
- [50]A. Y. Kitaev, Quantum measurements and the Abelian stabilizer problem (1995), arXiv:quant-ph/9511026 [quant-ph].
- [51]D. Aharonov, V. Jones, and Z. Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Algorithmica 55, 395 (2009).
- [52]J. Stewart, D. K. Clegg, and S. Watson, Calculus: Early Transcendentals, 9th ed. (Cengage Learning, 2020).
- [53]E. W. Cheney, Introduction to Approximation Theory, 2nd ed. (AMS Chelsea Publishing, 1982).
- [54]P. Borwein and T. Erdélyi, Polynomials and Polynomial Inequalities, Graduate Texts in Mathematics, Vol. 161 (Springer, 1995).DOI
- [55]J. C. Mason and D. C. Handscomb, Chebyshev Polynomials (Chapman and Hall/CRC, 2002).
- [56]Eviden, Quantum learning machine (QLM) and pyAQASM documentation (2024), https://myqlm.github.io.








