Introduction
Quantum minimum finding extends the quadratic advantage of quantum search [1 , 2 , 3 ] to finding the smallest of N N N arbitrary values using O ( N ) O(\sqrt{N}) O ( N ) evaluations [4 ] . In numerical applications, the objective value may not be available directly, and each evaluation may itself involve an estimation procedure. For example, coherent simulation can be used to estimate an expected loss, while phase estimation can be used to estimate the energy of a quantum state. In this work, we consider estimators that, for every candidate, return a value within additive error ε \varepsilon ε of the objective with probability at least 2/3.
To avoid biasing the search towards poor candidates with low estimated values, a standard approach applies the estimator several times and takes the median of the outputs. Implemented coherently, this procedure can reduce the estimator’s failure probability to O ( 1 / N ) O(1/N) O ( 1/ N ) using O ( log N ) O(\log N) O ( log N ) repetitions. For bounded-error Boolean search, Høyer, Mosca, and de Wolf [5 ] showed that this logarithmic overhead can be avoided by interleaving amplitude amplification with error reduction. In case of numerical estimation, however, the probability of obtaining an accurate estimate may be distributed among many accurate output values, such that no individual value has probability greater than 1 / 2 1/2 1/2 . Moreover, accurate estimates may give different orderings of candidates with similar objective values, or place the same candidate on opposite sides of a threshold. The probability that a candidate passes a threshold comparison depends on how often its estimates fall below the threshold. Lowering the threshold can reduce the acceptance probability by different amounts for different candidates and consequently change their relative probabilities of being selected.
Generalized minimum finding considers the problem of selecting a candidate with a low encoded score from an arbitrary prepared distribution, without requiring knowledge of the qualifying threshold [6 ] . The procedure requires O ( p − 1 / 2 ) O(p^{-1/2}) O ( p − 1/2 ) queries to the score-preparation unitary and its inverse to succeed with constant confidence, where p p p is a known lower bound on the prepared probability mass of scores at most this threshold. When objective values are available only through numerical estimators, a standard approach is to first amplify the confidence of the estimator. More specifically, its failure probability is reduced to a sufficiently small constant multiple of p p p , resulting in a total cost of O ( p − 1 / 2 log ( 2 / p ) ) O(p^{-1/2}\log(2/p)) O ( p − 1/2 log ( 2/ p )) base-estimator queries. Chen and de Wolf [7 ] use this approach to derive their approximate-unitary minimum-finding theorem from the generalized procedure, with a uniform preparation over N N N labels and p = 1 / N p = 1/N p = 1/ N . The same reduction is also used in the k = 1 k = 1 k = 1 special case of Gao, Ji, and Wang [8 ] . With confidence amplification, both these approaches therefore use O ( N log ( 2 N ) ) O(\sqrt{N}\log(2N)) O ( N log ( 2 N )) base-estimator queries and give an additive selection error of 2 ε 2\varepsilon 2 ε . The factor 2 2 2 in this error bound cannot in general be improved, as we prove in Proposition 2.4 .
We propose a quantum minimum-finding algorithm for general objectives accessed through numerical estimators that avoids the logarithmic overhead and attains the optimal additive selection error of 2 ε 2\varepsilon 2 ε . For arbitrary prepared distributions, the algorithm achieves simultaneous O ( p − 1 / 2 ) O(p^{-1/2}) O ( p − 1/2 ) bounds on preparation and base-estimator queries at constant confidence. It returns a candidate together with an accurate estimate of its objective value. The selected candidate can be returned as a classical label or as a quantum state.
Main results
Consider first the special case of N N N classical labels and a coherent estimator that is ε \varepsilon ε -accurate with probability at least 2 / 3 2/3 2/3 on every label. The objective values can be arbitrarily close and there can be arbitrarily many ties. We propose an algorithm that with constant confidence returns a label s s s such that
f ( s ) ≤ min i f ( i ) + 2 ε . f(s) \le\min_i f(i) + 2\varepsilon. f ( s ) ≤ i min f ( i ) + 2 ε .
The algorithm requires O ( N ) O(\sqrt{N}) O ( N ) queries to the base estimator and its inverse. The query scaling and the additive-error constant are individually worst-case optimal for 0 < ε < 1 / 2 0 < \varepsilon< 1/2 0 < ε < 1/2 .
In the general setting, assume that the estimator has the full unitary form A = ∑ i Π i ⊗ A i A = \sum_i \Pi_i \otimes A_i A = ∑ i Π i ⊗ A i , where Π i \Pi_i Π i are projectors onto objective sectors with corresponding objective values f i f_i f i . Within each sector, all input states give the same distribution of estimates, including states entangled with other registers. This form of A A A is stronger than preserving sector probabilities alone, as explained in § 2 .
Let P P P be a state preparation unitary and assume access to P P P , A A A , and their inverses. Write μ { f ≤ a } \mu\{f \le a\} μ { f ≤ a } for the probability that a measurement of the prepared state would yield an objective value at most a a a . Assume that p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] is known, and define
a p = min { a : μ { f ≤ a } ≥ p } . a_p = \min\{a : \mu\{f \le a\} \ge p\}. a p = min { a : μ { f ≤ a } ≥ p } .
The value of a p a_p a p is used only in the analysis and is not needed by the algorithm. Theorem 2.2 shows that, with probability at least 1 − δ 1-\delta 1 − δ , the algorithm returns a candidate together with an estimate v v v of its objective value such that
∣ v − X o u t ∣ ≤ ε , v ≤ a p + ε , \lvert v-X_{\mathrm{out}}\rvert\le\varepsilon,\qquad v\le a_p+\varepsilon, ∣ v − X out ∣ ≤ ε , v ≤ a p + ε ,
for any fixed 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 . Here X o u t X_{\mathrm{out}} X out denotes the objective value that would be obtained if the returned candidate had been measured. Writing u = log ( 2 / δ ) u=\log(2/\delta) u = log ( 2/ δ ) , the worst-case bounds on the preparation query count Q P Q_P Q P , estimator query count Q A Q_A Q A , and number of qubits S Q S_Q S Q are
Q P = O ( p − 1 / 2 u ) , Q A = O ( p − 1 / 2 u + u 2 ) , S Q = O ( s P + w + log log ( 4 / p ) ) , Q_P=O(p^{-1/2}u),\qquad Q_A=O(p^{-1/2}u+u^2),\qquad S_Q=O(s_P+w+\log\log(4/p)), Q P = O ( p − 1/2 u ) , Q A = O ( p − 1/2 u + u 2 ) , S Q = O ( s P + w + log log ( 4/ p )) ,
where s P s_P s P and w w w are the number of qubits used for preparation and for the estimator workspace, respectively. The result applies to both classical labels and unknown energy eigenspaces.
The algorithm is applied to bounded-expectation selection and ground-energy estimation. Combined with amplitude estimation, it gives the worst-case optimal bound of Θ ( N / η ) \Theta(\sqrt{N}/\eta) Θ ( N / η ) queries to the underlying coherent sampling oracle for selecting an η \eta η -optimal bounded expectation at constant confidence. For ground-energy estimation, the algorithm uses phase estimation and a guiding state with ground-space amplitude overlap at least ω \omega ω . An additive-η \eta η estimate can then be obtained using O ( ω − 1 u ) O(\omega^{-1}u) O ( ω − 1 u ) preparation queries and O ( ( ω η ) − 1 u ) O((\omega\eta)^{-1}u) O (( ω η ) − 1 u ) elementary controlled-evolution queries. No initial energy estimate is needed, and neither application requires a gap assumption.
Proof overview
The algorithm runs a sequence of trials to improve a current candidate (incumbent). Each trial seeks a new candidate with estimated value y y y below the estimate τ \tau τ of the incumbent. The new candidate is accepted if additional estimates of its value pass validation, otherwise it is rejected. The same estimate y y y can pass validation more often in one sector than in another. We therefore analyze the probability that a trial proposes a candidate from sector i i i with estimate y y y .
Let Y i Y_i Y i be a new estimate in sector i i i , and write q i − ( y ) = Pr { Y i ≤ y } q_i^{-}(y)=\Pr\{Y_i\le y\} q i − ( y ) = Pr { Y i ≤ y } and q i + ( y ) = Pr { Y i ≥ y } q_i^{+}(y)=\Pr\{Y_i\ge y\} q i + ( y ) = Pr { Y i ≥ y } . Let α \alpha α and β \beta β be constants satisfying 1 / 3 < α < β < 1 / 2 1/3<\alpha<\beta<1/2 1/3 < α < β < 1/2 . If both the probabilities exceed α \alpha α for a pair ( i , y ) (i,y) ( i , y ) , then y y y must differ from the objective value in sector i i i by at most ε \varepsilon ε . Such a pair ( i , y ) (i,y) ( i , y ) is called acceptable. A pair is called good if both probabilities are at least β \beta β . In every sector, an estimate gives a good pair with probability at least 1 − 2 β 1-2\beta 1 − 2 β .
The recursion follows Høyer et al. [5 ] by interleaving amplitude amplification with error reduction. In our construction, error reduction is performed by two coherent polynomial filters that suppress unacceptable pairs while preserving the weight of good pairs. The filters are constructed using linear-combination block encodings and singular value transformation with real polynomials [9 ] . If π i , y \pi_{i,y} π i , y is the initial probability of ( i , y ) (i,y) ( i , y ) and e ℓ ( i , y ) e_\ell(i,y) e ℓ ( i , y ) its probability of passing the filters at level ℓ \ell ℓ , the probability that a depth-j j j trial produces the pair ( i , y ) (i,y) ( i , y ) without recording a rejection is
c j ( τ ) 2 ω j ( i , y ) 1 { y < τ } , ω j ( i , y ) = π i , y ∏ ℓ = 0 j − 1 e ℓ ( i , y ) . c_j(\tau)^2\omega_j(i,y)\mathbf{1}_{\{y<\tau\}},\qquad\omega_j(i,y)=\pi_{i,y}\prod_{\ell=0}^{j-1}e_\ell(i,y). c j ( τ ) 2 ω j ( i , y ) 1 { y < τ } , ω j ( i , y ) = π i , y ℓ = 0 ∏ j − 1 e ℓ ( i , y ) .
Since the weights ω j ( i , y ) \omega_j(i,y) ω j ( i , y ) are independent of τ \tau τ , and the amplification factor c j ( τ ) c_j(\tau) c j ( τ ) is common to all pairs, the relative proposal probabilities of the pairs with estimates below the threshold τ \tau τ are preserved when it is lowered. This allows us to analyze the progress of the algorithm using weights that do not depend on the previously accepted estimates.
At depth j j j , we define the rank R j ( τ ) R_j(\tau) R j ( τ ) as the total ω j \omega_j ω j -weight of acceptable pairs with y < τ y < \tau y < τ , and aim to reduce it below a prescribed upper bound, called the rank cap. Rank bounds established at earlier depths, together with the suppression of unacceptable pairs, give a lower bound on the amplification factor. If the current rank exceeds its cap, there is a smallest estimated value y ∗ y_* y ∗ such that the total weight of acceptable pairs with estimates at most y ∗ y_* y ∗ reaches the cap. Accepting a proposal with estimate y ≤ y ∗ y \le y_* y ≤ y ∗ lowers the threshold to y y y , bringing the rank below the cap since only pairs with strictly smaller estimates are counted. The acceptable pairs with estimates at most y ∗ y_* y ∗ have total weight at least the cap, so the proposal formula and validation completeness give a lower bound on the probability of such an update in every trial. Repetition therefore brings the rank below each cap with high probability, even when thresholds depend on previous trials or estimated values have ties.
Since the filters retain a fixed proportion of the initial weight of good pairs from sectors with objective value at most a p a_p a p , a threshold τ > a p + ε \tau> a_p + \varepsilon τ > a p + ε gives a final rank of at least a constant times p p p . Choosing the final rank cap below this amount therefore implies τ ≤ a p + ε \tau\le a_p + \varepsilon τ ≤ a p + ε . With high probability, validation also ensures that the stored estimate differs from the objective value by at most ε \varepsilon ε , giving a final objective value of at most a p + 2 ε a_p + 2\varepsilon a p + 2 ε .
The filters require O ( j + 1 ) O(j+1) O ( j + 1 ) estimator queries at level j j j . Each recursive amplification step applies the preceding circuit twice and its inverse once, followed by a new filter. Consequently, the query cost of a depth-j j j trial is O ( 3 j − 1 ) O(3^{j-1}) O ( 3 j − 1 ) . We choose the maximum depth K K K such that 9 K − 1 = Θ ( 1 / p ) 9^{K-1} = \Theta(1/p) 9 K − 1 = Θ ( 1/ p ) , giving a maximum trial cost of O ( 3 K − 1 ) = O ( p − 1 / 2 ) O(3^{K-1}) = O(p^{-1/2}) O ( 3 K − 1 ) = O ( p − 1/2 ) . The number of repetitions increases geometrically toward the cheaper lower depths, but at a rate that keeps the total query cost within the same bound. The query cost of validation is of lower order.
A reversible counter records the level of the first rejection, requiring only O ( log ( K + 1 ) ) O(\log(K+1)) O ( log ( K + 1 )) qubits. On branches where no rejection has been recorded, the filter workspace is zero and can be reused. Since K = O ( log ( 2 / p ) ) K = O(\log(2/p)) K = O ( log ( 2/ p )) , this gives a total space bound of O ( s P + w + log log ( 4 / p ) ) O(s_P + w + \log\log(4/p)) O ( s P + w + log log ( 4/ p )) .
Related work
Table 1 compares our algorithm with the previously discussed constructions of AGGW [6 ] and Chen and de Wolf [7 ] . Gao et al. [8 ] extend approximate minimum finding to the selection of k k k distinct labels. In the special case k = 1 k = 1 k = 1 , their Algorithm 1 reduces to a single call to AGGW’s generalized minimum finder, using uniform preparation over labels followed by the numerical estimator. Appendix § 10 derives their query bounds under our oracle assumptions (Definition 2.1 ), using confidence amplification before search.
Optimal minimum finding with bounded-error comparisons was obtained by Wang and Ying [11 ] . Allcock et al. [12 ] give query and time bounds for search and minimization with subroutines that return a specified integer answer for each input with bounded error. The non-Boolean purification result of Belovs and Jeffery [13 Section 7] also assumes that one particular output occurs with probability greater than 1 / 2 1/2 1/2 . A numerical estimator may instead distribute its success probability among several values within ε \varepsilon ε of the objective, with no individual value occurring with probability greater than 1 / 2 1/2 1/2 . Quek et al. [14 ] consider comparisons that may be unreliable when the values being compared are close. Their result requires a local-density assumption, while our result allows arbitrarily close objective values and arbitrary ties.
Search with neutral inputs [15 Section 3.2] allows threshold decisions to be ambiguous. Its witness guarantee, however, does not specify how the probability of success is distributed among valid witnesses. For example, an algorithm satisfying this guarantee could always return the largest score below the incumbent. Each update would then reduce the rank only by the weight assigned to that score.
Comparisons with related work on bounded-expectation selection [16 , 17 ] and ground-energy estimation [18 , 19 , 20 ] are given in § 6 .
Organization
§ 2 formalizes the oracle model and the main results. The proof is developed in § 3 –§ 5 through validation tests, coherent trials and the adaptive selection procedure. § 6 presents the applications and comparisons with existing methods. § 7 concludes the paper. The appendices contain supplementary proofs, implementation details and query comparisons for concrete constants.
Model and main results
We give a more formal statement of the oracle model and main results, and prove lower bounds on the number of estimator queries and the additive selection error. All systems are assumed to be finite-dimensional. We use the Euclidean norm for vectors and the spectral norm for operators. Logarithms are assumed to be natural unless a base is specified. The main parameters used throughout the paper are listed in Table 2 .
Table 2. Parameters used throughout the paper.
Oracle model
Let C \mathcal{C} C be the candidate register and R \mathcal{R} R the auxiliary registers of the preparation unitary P P P . We consider a target of the form
F = ∑ i ∈ I f i Π i , 0 ≤ f i ≤ 1 , F = \sum_{i \in I} f_i \Pi_i, \qquad0 \leq f_i \leq1, F = i ∈ I ∑ f i Π i , 0 ≤ f i ≤ 1 ,
where I I I is finite and { Π i } \{\Pi_i\} { Π i } is a family of mutually orthogonal projectors summing to the identity on C \mathcal{C} C . Projectors can have rank greater than one. Classical labels correspond to the special case where Π i = ∣ i ⟩ ⟨ i ∣ \Pi_i = |i\rangle\langle i| Π i = ∣ i ⟩ ⟨ i ∣ . We assume access to the objective via the estimator below. We are not given the projectors, a method for preparation of states in different sectors, or an independent oracle for evaluation or measurement of F F F .
Let P P P be a unitary that prepares the state
∣ Ω ⟩ C R = P ∣ 0 ⟩ . |\Omega\rangle_{CR} = P|0\rangle. ∣Ω ⟩ C R = P ∣0 ⟩ .
We denote by μ i \mu_i μ i the probability of obtaining sector i i i in a hypothetical measurement of this state with the projectors { Π i } \{\Pi_i\} { Π i } , so that
μ i = ∥ ( Π i ⊗ I R ) ∣ Ω ⟩ ∥ 2 . \mu_i = \lVert(\Pi_i \otimes I_R)|\Omega\rangle\rVert^2. μ i = ∥( Π i ⊗ I R ) ∣Ω ⟩ ∥ 2 .
For a set E E E of objective values, we write μ { f ∈ E } = ∑ i : f i ∈ E μ i \mu\{f \in E\} = \sum_{i:f_i\in E}\mu_i μ { f ∈ E } = ∑ i : f i ∈ E μ i for the probability that the measured value belongs to E E E .
Definition 2.1. A coherent numerical estimator , also called a base estimator , is a unitary on the candidate register C C C and a work register W W W of the form
A = ∑ i ∈ I Π i ⊗ A i . (1) A = \sum_{i\in I} \Pi_i \otimes A_i. \tag*{(1)} A = i ∈ I ∑ Π i ⊗ A i . (1) It acts as the identity on R R R and on all previously retained work registers.
The estimator has a designated output register and a known decoding function. For each i i i , measuring this register in the computational basis in the state A i ∣ 0 ⟩ W A_i|0\rangle_W A i ∣0 ⟩ W and decoding the outcome gives a finite-valued random variable Y i ∈ [ 0 , 1 ] Y_i \in[0,1] Y i ∈ [ 0 , 1 ] satisfying
Pr { ∣ Y i − f i ∣ ≤ ε } ≥ 2 / 3 for every i . (2) \Pr\{|Y_i-f_i|\le\varepsilon\}\ge2/3 \quad\text{for every } i. \tag*{(2)} Pr { ∣ Y i − f i ∣ ≤ ε } ≥ 2/3 for every i . (2)
The decoded estimates can be clipped to [ 0 , 1 ] [0,1] [ 0 , 1 ] without increasing their error, because the objective values lie in this interval.
If the candidate is in sector i i i , A A A acts only on the estimator workspace. For any state ∣ ψ i ⟩ C R |\psi_i\rangle_{CR} ∣ ψ i ⟩ C R supported in sector i i i ,
A ( ∣ ψ i ⟩ C R ∣ 0 ⟩ W ) = ∣ ψ i ⟩ C R ⊗ A i ∣ 0 ⟩ W . A(|\psi_i\rangle_{CR}|0\rangle_W) = |\psi_i\rangle_{CR} \otimes A_i|0\rangle_W. A ( ∣ ψ i ⟩ C R ∣0 ⟩ W ) = ∣ ψ i ⟩ C R ⊗ A i ∣0 ⟩ W .
Since A i ∣ 0 ⟩ W A_i|0\rangle_W A i ∣0 ⟩ W does not depend on the candidate state within sector i i i , the estimate has the distribution of Y i Y_i Y i for every such state. For a fixed sector i i i , independent estimates are obtained by resetting the workspace to ∣ 0 ⟩ W |0\rangle_{W} ∣0 ⟩ W between successive applications of A A A . In case of phase estimation, the evolution multiplies all states in a given energy eigenspace by the same phase. The energy eigenspaces can therefore be used as the sectors in (1) .
We assume that P P P , A A A and their inverses are available. The preparation query count Q P Q_{P} Q P is the total number of applications of P P P and P † P^{\dagger} P † , and the base-estimator query count Q A Q_{A} Q A is the total number of applications of A A A and A † A^{\dagger} A † . Let s P s_{P} s P denote the number of qubits in the preparation register C R \mathcal{CR} C R , and let w w w denote the number of qubits in the estimator workspace W \mathcal{W} W , including the numerical output register and all registers used for coherent decoding. Known rotations are treated as exact in the main proof. Gate approximations are treated in Appendix B.3, where it is shown that the change in success probability is bounded by the sum of their operator-norm errors.
In case the output is a retained candidate, let X o u t X_{\mathrm{out}} X out denote the objective value that would have been obtained by a final measurement of F F F . Probabilities involving X o u t X_{\mathrm{out}} X out refer to the hypothetical experiment of running the algorithm and then making this measurement.
Main theorem
For analysis define
a p = min { a : μ { f ≤ a } ≥ p } . (3) a_{p}=\min\{a:\mu\{f\leq a\}\geq p\}. \tag*{(3)} a p = min { a : μ { f ≤ a } ≥ p } . (3)
Finiteness implies μ { f < a p } < p \mu\{f<a_{p}\}<p μ { f < a p } < p . The algorithm is not given a p a_{p} a p .
Theorem 2.2. Under Definition 2.1 , for every known 0 < p ≤ 1 0<p\leq1 0 < p ≤ 1 , ε > 0 \varepsilon>0 ε > 0 , and 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 , an algorithm returns a candidate and real numbers v , L , U v,L,U v , L , U , with L = v − ε L=v-\varepsilon L = v − ε and U = v + ε U=v+\varepsilon U = v + ε on every execution, such that jointly with probability at least 1 − δ 1-\delta 1 − δ ,
∣ v − X o u t ∣ ≤ ε , v ≤ a p + ε . (4) |v-X_{\mathrm{out}}|\leq\varepsilon,\qquad v\leq a_{p}+\varepsilon. \tag*{(4)} ∣ v − X out ∣ ≤ ε , v ≤ a p + ε . (4) Writing u = log ( 2 / δ ) u=\log(2/\delta) u = log ( 2/ δ ) , its worst-case resource bounds are
Q P = O ( p − 1 / 2 u ) , Q A = O ( p − 1 / 2 u + u 2 ) , S Q = O ( s P + w + log log ( 4 / p ) ) . (5) Q_{P}=O(p^{-1/2}u),\qquad Q_{A}=O(p^{-1/2}u+u^{2}),\qquad S_{Q}=O(s_{P}+w+\log\log(4/p)). \tag*{(5)} Q P = O ( p − 1/2 u ) , Q A = O ( p − 1/2 u + u 2 ) , S Q = O ( s P + w + log log ( 4/ p )) . (5) The constants are universal and independent of the number of possible estimator outputs. The algorithm knows neither μ \mu μ nor a qualifying objective threshold. It uses no controlled P P P or controlled A A A .
Theorem 2.2 gives
X o u t ∈ [ L , U ] , μ { f < L } < p , U − L = 2 ε (6) X_{\mathrm{out}}\in[L,U],\qquad\mu\{f<L\}<p,\qquad U-L=2\varepsilon \tag*{(6)} X out ∈ [ L , U ] , μ { f < L } < p , U − L = 2 ε (6)
with probability at least 1 − δ 1-\delta 1 − δ , where L ≤ a p L\leq a_{p} L ≤ a p gives a bound on the probability mass below L L L . For every a a a with μ { f ≤ a } ≥ p \mu\{f\leq a\}\geq p μ { f ≤ a } ≥ p , the selected objective value therefore satisfies
X o u t ≤ a + 2 ε . (7) X_{\mathrm{out}}\leq a+2\varepsilon. \tag*{(7)} X out ≤ a + 2 ε . (7)
Let ρ ˉ \bar{\rho} ρ ˉ denote the density matrix of the returned candidate register C \mathcal{C} C , averaged over the algorithm’s measurement outcomes and classical random choices. For every a a a with μ { f ≤ a } ≥ p \mu\{f\leq a\}\geq p μ { f ≤ a } ≥ p , measuring F F F on this register gives
Pr { X o u t ≤ a + 2 ε } = Tr ( ρ ˉ ∑ i : f i ≤ a + 2 ε Π i ) ≥ 1 − δ . \Pr\{X_{\mathrm{out}}\leq a+2\varepsilon\}=\operatorname{Tr}\left(\bar{\rho}\sum_{i:f_i\leq a+2\varepsilon}\Pi_i\right)\geq1-\delta. Pr { X out ≤ a + 2 ε } = Tr ρ ˉ i : f i ≤ a + 2 ε ∑ Π i ≥ 1 − δ .
The selection and validation procedures do not use ε \varepsilon ε , assuming that the base estimator is given. Its value is needed only to form L L L and U U U .
For uniform preparation over N N N classical labels, choosing p = 1 / N p=1/N p = 1/ N gives the following corollary.
Corollary 2.3. For N N N classical labels with known uniform preparation, let A A A be a label-preserving estimator satisfying Definition 2.1. With probability at least 1 − δ 1-\delta 1 − δ , an algorithm returns a label s s s and numbers v v v , L L L , U U U satisfying the output guarantee of Theorem 2.2 with p = 1 / N p=1/N p = 1/ N ; in particular,
f ( s ) ≤ min i f ( i ) + 2 ε . f(s) \le\min_i f(i) + 2\varepsilon. f ( s ) ≤ i min f ( i ) + 2 ε . It uses O ( N u + u 2 ) O(\sqrt{N}u+u^2) O ( N u + u 2 ) base-estimator queries and O ( w + log ( 2 N ) ) O(w+\log(2N)) O ( w + log ( 2 N )) live quantum qubits, where u = log ( 2 / δ ) u=\log(2/\delta) u = log ( 2/ δ ) .
Proof. With uniform preparation, each label has probability 1 / N 1/N 1/ N , so every minimum-value block has prior mass at least 1 / N 1/N 1/ N . The query bound follows by applying Theorem 2.2 with p = 1 / N p=1/N p = 1/ N . Uniform preparation requires O ( log ( 2 N ) ) O(\log(2N)) O ( log ( 2 N )) qubits. Since p = 1 / N p=1/N p = 1/ N , the additional term log log ( 4 / p ) = log log ( 4 N ) \log\log(4/p)=\log\log(4N) log log ( 4/ p ) = log log ( 4 N ) is also bounded by O ( log ( 2 N ) ) O(\log(2N)) O ( log ( 2 N )) . The classical output is obtained by measuring the candidate register in the label basis.
Lower bounds
The next two propositions show that both the additive-error constant 2 and the base-estimator query scaling in Theorem 2.2 are individually optimal.
Proposition 2.4. Let 0 < ε ≤ 1 / 2 0<\varepsilon\le1/2 0 < ε ≤ 1/2 . Under the numerical-estimation promise alone, no algorithm can guarantee additive selection error below 2 ε 2\varepsilon 2 ε with success probability greater than 1 / 2 1/2 1/2 on every instance, regardless of the number of queries.
Proof. Take two labels with uniform preparation, and fix an estimator unitary that returns 1 / 2 1/2 1/2 on both labels. This estimator satisfies the numerical promise for either of the objectives
( f ( 0 ) , f ( 1 ) ) = ( 1 2 − ε , 1 2 + ε ) (f(0),f(1))=\left(\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon\right) ( f ( 0 ) , f ( 1 )) = ( 2 1 − ε , 2 1 + ε )
and
( f ( 0 ) , f ( 1 ) ) = ( 1 2 + ε , 1 2 − ε ) . (f(0),f(1))=\left(\frac{1}{2}+\varepsilon,\frac{1}{2}-\varepsilon\right). ( f ( 0 ) , f ( 1 )) = ( 2 1 + ε , 2 1 − ε ) .
Since the algorithm has no other access to f f f , its output distribution is the same in both cases.
For p = 1 / 2 p=1/2 p = 1/2 and a = 1 / 2 − ε a=1/2-\varepsilon a = 1/2 − ε , selection error below 2 ε 2\varepsilon 2 ε requires label 0 in the first case and label 1 in the second. Let r r r be the probability of obtaining label 0 from the output, measuring in the label basis if necessary. The two success probabilities are therefore r r r and 1 − r 1-r 1 − r , so at least one is at most 1 / 2 1/2 1/2 .
Proposition 2.5. Suppose 2 ε < 1 2\varepsilon<1 2 ε < 1 . At constant confidence, the Θ ( p − 1 / 2 ) \Theta(p^{-1/2}) Θ ( p − 1/2 ) dependence of the base-estimator query count is optimal in the worst case. This holds even for p = 1 / N p=1/N p = 1/ N with classical labels and free, known uniform preparation.
Proof. Consider unstructured search on N N N labels with a unique marked label z z z . Set f ( z ) = 0 f(z)=0 f ( z ) = 0 and f ( i ) = 1 f(i)=1 f ( i ) = 1 for i ≠ z i\ne z i = z , and use the exact value oracle for f f f as the numerical estimator. Each estimator query can be simulated with a constant number of search-oracle queries.
With p = 1 / N p=1/N p = 1/ N and a = 0 a=0 a = 0 , a successful output must satisfy f ( s ) ≤ 2 ε < 1 f(s)\le2\varepsilon<1 f ( s ) ≤ 2 ε < 1 , so s = z s=z s = z . The algorithm therefore finds the marked label with the same success probability, measuring its output in the label basis if necessary.
The quantum search lower bound [2 , 3 ] then implies Ω ( N ) = Ω ( p − 1 / 2 ) \Omega(\sqrt{N})=\Omega(p^{-1/2}) Ω ( N ) = Ω ( p − 1/2 ) base-estimator queries. Corollary 2.3 gives the matching upper bound at constant confidence.
:::
Validation of numerical estimates
To validate an estimate y y y , the algorithm uses new estimates obtained from the same candidate. For a fixed sector i i i , the estimate y y y must be ε \varepsilon ε -accurate if both Pr { Y i ≤ y } \Pr\{Y_i \le y\} Pr { Y i ≤ y } and Pr { Y i ≥ y } \Pr\{Y_i \ge y\} Pr { Y i ≥ y } exceed 1 / 3 1/3 1/3 . This section develops validation tests based on these two probabilities.
Accuracy criteria
Let A s a m p l e A_{\mathrm{sample}} A sample denote an application of A A A to a fresh estimator workspace. Preparing a candidate and estimating its value gives
B p r e p = A s a m p l e ( P ⊗ I ) , π i , y = μ i Pr { Y i = y } , B_{\mathrm{prep}} = A_{\mathrm{sample}}(P \otimes I), \qquad\pi_{i,y} = \mu_i \Pr\{Y_i = y\}, B prep = A sample ( P ⊗ I ) , π i , y = μ i Pr { Y i = y } ,
where π i , y \pi_{i,y} π i , y is the joint probability of sector i i i and decoded estimate y y y . We call the stored numerical estimate y y y the score.
For a pair z = ( i , y ) z=(i,y) z = ( i , y ) , the probabilities that a new estimate is at most or at least y y y are
q i − ( y ) = Pr { Y i ≤ y } , q i + ( y ) = Pr { Y i ≥ y } . (8) q_i^{-}(y) = \Pr\{Y_i \le y\}, \qquad q_i^{+}(y) = \Pr\{Y_i \ge y\}. \tag*{(8)} q i − ( y ) = Pr { Y i ≤ y } , q i + ( y ) = Pr { Y i ≥ y } . (8)
Choose thresholds satisfying
1 3 < γ < α < β < 1 2 , (9) \frac{1}{3} < \gamma< \alpha< \beta< \frac{1}{2}, \tag*{(9)} 3 1 < γ < α < β < 2 1 , (9)
and keep them fixed throughout each run. Define the good, bad, and acceptable pairs, respectively, by
G = { z : q i − ( y ) , q i + ( y ) ≥ β } , B = { z : min ( q i − ( y ) , q i + ( y ) ) ≤ α } , S = B c . (10) G = \{z : q_i^{-}(y),q_i^{+}(y) \ge\beta\}, \qquad B = \{z : \min(q_i^{-}(y),q_i^{+}(y)) \le\alpha\}, \qquad S = B^{c}. \tag*{(10)} G = { z : q i − ( y ) , q i + ( y ) ≥ β } , B = { z : min ( q i − ( y ) , q i + ( y )) ≤ α } , S = B c . (10)
It follows that every good pair is acceptable. Furthermore, every acceptable pair must satisfy ∣ y − f i ∣ ≤ ε |y-f_i| \le\varepsilon ∣ y − f i ∣ ≤ ε . To see this, observe that if y < f i − ε y < f_i-\varepsilon y < f i − ε , then Y i ≤ y Y_i \le y Y i ≤ y can occur only when the new estimate is inaccurate, so q i − ( y ) ≤ 1 / 3 q_i^{-}(y) \le1/3 q i − ( y ) ≤ 1/3 . Similarly, y > f i + ε y > f_i+\varepsilon y > f i + ε implies that q i + ( y ) ≤ 1 / 3 q_i^{+}(y) \le1/3 q i + ( y ) ≤ 1/3 . Neither of these cases can occur for a pair in S S S , because α > 1 / 3 \alpha> 1/3 α > 1/3 .
The restriction β < 1 / 2 \beta< 1/2 β < 1/2 ensures that good pairs have probability at least 1 − 2 β > 0 1-2\beta> 0 1 − 2 β > 0 in every sector.
The thresholds α \alpha α and β \beta β are fixed constants independent of p p p and δ \delta δ .
Lemma 3.1. The probability of preparing a good pair with score at most a p + ε a_p+\varepsilon a p + ε is at least ( 1 − 2 β ) p (1-2\beta)p ( 1 − 2 β ) p :
π { z ∈ G : y ≤ a p + ε } ≥ ( 1 − 2 β ) p . \pi\{z \in G : y \le a_p+\varepsilon\} \ge(1-2\beta)p. π { z ∈ G : y ≤ a p + ε } ≥ ( 1 − 2 β ) p . Proof. Fix a sector i i i , and let F i F_i F i be the CDF of Y i Y_i Y i . After sampling Y i = y Y_i=y Y i = y , sample U U U uniformly from [ F i ( y − ) , F i ( y ) ] [F_i(y^-),F_i(y)] [ F i ( y − ) , F i ( y )] . The resulting random variable U U U is uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and
q i − ( Y i ) = F i ( Y i ) ≥ U , q i + ( Y i ) = 1 − F i ( Y i − ) ≥ 1 − U . q_i^{-}(Y_i) = F_i(Y_i) \ge U, \qquad q_i^{+}(Y_i) = 1-F_i(Y_i^-) \ge1-U. q i − ( Y i ) = F i ( Y i ) ≥ U , q i + ( Y i ) = 1 − F i ( Y i − ) ≥ 1 − U . Since U U U is uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] , it lies in [ β , 1 − β ] [\beta,1-\beta] [ β , 1 − β ] with probability 1 − 2 β 1-2\beta 1 − 2 β . In that interval, q i − ( Y i ) ≥ U ≥ β q_i^{-}(Y_i) \ge U \ge\beta q i − ( Y i ) ≥ U ≥ β and q i + ( Y i ) ≥ 1 − U ≥ β q_i^{+}(Y_i) \ge1-U \ge\beta q i + ( Y i ) ≥ 1 − U ≥ β , so ( i , Y i ) (i,Y_i) ( i , Y i ) is a good pair.
Therefore, since every good pair is accurate, if f i ≤ a p f_i \le a_p f i ≤ a p , the same event also gives
Y i ≤ f i + ε ≤ a p + ε . Y_i \le f_i+\varepsilon\le a_p+\varepsilon. Y i ≤ f i + ε ≤ a p + ε . The preparation assigns total mass at least p p p to sectors with f i ≤ a p f_i \le a_p f i ≤ a p . Hence
π { z ∈ G : y ≤ a p + ε } ≥ ( 1 − 2 β ) ∑ i : f i ≤ a p μ i ≥ ( 1 − 2 β ) p . \pi\{z \in G : y \le a_p+\varepsilon\} \ge(1-2\beta)\sum_{i:f_i\le a_p}\mu_i \ge(1-2\beta)p. π { z ∈ G : y ≤ a p + ε } ≥ ( 1 − 2 β ) i : f i ≤ a p ∑ μ i ≥ ( 1 − 2 β ) p .
Validation by repeated estimation
Lemma 3.2. For fixed 0 < l < h < 1 0<l<h<1 0 < l < h < 1 and 0 < ζ < 1 / 2 0<\zeta<1/2 0 < ζ < 1/2 , there is a validation procedure Val l , h ( y , ζ ) \operatorname{Val}_{l,h}(y,\zeta) Val l , h ( y , ζ ) that uses
n l , h ( ζ ) = ⌈ 2 ( h − l ) 2 log 2 ζ ⌉ (11) n_{l,h}(\zeta)=\left\lceil\frac{2}{(h-l)^2}\log\frac{2}{\zeta}\right\rceil \tag*{(11)} n l , h ( ζ ) = ⌈ ( h − l ) 2 2 log ζ 2 ⌉ (11) forward base-estimator queries and one reusable estimator workspace. For every sector i i i and stored score y y y , it satisfies
q i − ( y ) , q i + ( y ) ≥ h ⟹ Pr { accept ∣ i , y } ≥ 1 − ζ , (12) q_i^{-}(y),q_i^{+}(y)\ge h\Longrightarrow\Pr\{\operatorname{accept}\mid i,y\}\ge1-\zeta, \tag*{(12)} q i − ( y ) , q i + ( y ) ≥ h ⟹ Pr { accept ∣ i , y } ≥ 1 − ζ , (12) min ( q i − ( y ) , q i + ( y ) ) ≤ l ⟹ Pr { accept ∣ i , y } ≤ ζ . (13) \min(q_i^{-}(y),q_i^{+}(y))\le l\Longrightarrow\Pr\{\operatorname{accept}\mid i,y\}\le\zeta. \tag*{(13)} min ( q i − ( y ) , q i + ( y )) ≤ l ⟹ Pr { accept ∣ i , y } ≤ ζ . (13) These bounds also hold conditional on earlier classical history of non-zero probability.
Proof. Run the estimator n = n l , h ( ζ ) n=n_{l,h}(\zeta) n = n l , h ( ζ ) times to obtain independent estimates Y i ( 1 ) , … , Y i ( n ) Y_i^{(1)},\ldots,Y_i^{(n)} Y i ( 1 ) , … , Y i ( n ) . Define
q ^ − = 1 n ∑ j = 1 n 1 { Y i ( j ) ≤ y } , q ^ + = 1 n ∑ j = 1 n 1 { Y i ( j ) ≥ y } . \widehat{q}^{-}=\frac{1}{n}\sum_{j=1}^{n}\mathbf{1}_{\{Y_i^{(j)}\le y\}},\qquad
\widehat{q}^{+}=\frac{1}{n}\sum_{j=1}^{n}\mathbf{1}_{\{Y_i^{(j)}\ge y\}}. q − = n 1 j = 1 ∑ n 1 { Y i ( j ) ≤ y } , q + = n 1 j = 1 ∑ n 1 { Y i ( j ) ≥ y } .
The procedure Val l , h ( y , ζ ) \operatorname{Val}_{l,h}(y,\zeta) Val l , h ( y , ζ ) accepts the stored score y y y if both q ^ − \widehat{q}^{-} q − and q ^ + \widehat{q}^{+} q + are at least ( l + h ) / 2 (l+h)/2 ( l + h ) /2 , and rejects it otherwise.
By Definition 2.1 , repeated calls to the estimator produce independent outputs with the same distribution as Y i Y_i Y i , conditional on the sector and earlier classical history. If both q i − ( y ) q_i^{-}(y) q i − ( y ) and q i + ( y ) q_i^{+}(y) q i + ( y ) are at least h h h , Hoeffding’s inequality gives
Pr { q ^ + < l + h 2 | i , y } ≤ exp ( − n ( h − l ) 2 2 ) ≤ ζ 2 . \Pr\left\{\widehat{q}^{+}<\frac{l+h}{2}\,\middle|\,i,y\right\}\le\exp\left(-\frac{n(h-l)^2}{2}\right)\le\frac{\zeta}{2}. Pr { q + < 2 l + h i , y } ≤ exp ( − 2 n ( h − l ) 2 ) ≤ 2 ζ .
Rejection requires at least one of these two events to occur, therefore its probability is at most ζ \zeta ζ .
For soundness, suppose first that q i − ( y ) ≤ l q_i^{-}(y)\le l q i − ( y ) ≤ l . Acceptance requires q ^ − ≥ ( l + h ) / 2 \widehat{q}^{-}\ge(l+h)/2 q − ≥ ( l + h ) /2 , and hence
q ^ − − q i − ( y ) ≥ l + h 2 − q i − ( y ) ≥ h − l 2 . \widehat{q}^{-}-q_i^{-}(y)\ge\frac{l+h}{2}-q_i^{-}(y)\ge\frac{h-l}{2}. q − − q i − ( y ) ≥ 2 l + h − q i − ( y ) ≥ 2 h − l .
The indicators defining q ^ − \widehat{q}^{-} q − are independent Bernoulli random variables with mean q i − ( y ) q_i^{-}(y) q i − ( y ) . Hoeffding’s inequality therefore gives
Pr { accept ∣ i , y } ≤ Pr { q ^ − − q i − ( y ) ≥ h − l 2 | i , y } ≤ exp ( − n ( h − l ) 2 2 ) ≤ ζ 2 ≤ ζ . \Pr\{\operatorname{accept}\mid i,y\}\le\Pr\left\{\widehat{q}^{-}-q_i^{-}(y)\ge\frac{h-l}{2}\,\middle|\,i,y\right\}\le\exp\left(-\frac{n(h-l)^2}{2}\right)\le\frac{\zeta}{2}\le\zeta. Pr { accept ∣ i , y } ≤ Pr { q − − q i − ( y ) ≥ 2 h − l i , y } ≤ exp ( − 2 n ( h − l ) 2 ) ≤ 2 ζ ≤ ζ .
Here the earlier classical history is fixed and suppressed in the conditioning notation. If q i + ( y ) ≤ l q_i^{+}(y)\le l q i + ( y ) ≤ l , the same argument applies to q ^ + \widehat{q}^{+} q + . Since min ( q i − ( y ) , q i + ( y ) ) ≤ l \min(q_i^{-}(y),q_i^{+}(y))\le l min ( q i − ( y ) , q i + ( y )) ≤ l implies that at least one of these two cases holds, this proves (13) , also conditional on any earlier classical history of positive probability.
The union bound on rejection holds when q ^ − \widehat{q}^{-} q − and q ^ + \widehat{q}^{+} q + are computed from the same estimates. The numbers of outputs at most y y y and at least y y y are stored classically. After each query, the estimator workspace is measured and reset so that it can be reused.
During selection, inner validation checks proposed replacements, using thresholds ( l , h ) = ( γ , α ) (l,h)=(\gamma,\alpha) ( l , h ) = ( γ , α ) . During confidence amplification, outer validation checks candidates returned by selection runs, using thresholds ( l , h ) = ( 1 / 3 , γ ) (l,h)=(1/3,\gamma) ( l , h ) = ( 1/3 , γ ) .
Inner validation accepts a pair with min ( q ˉ i ( y ) , q i + ( y ) ) ≤ γ \min(\bar{q}_i(y),q_i^+(y)) \le\gamma min ( q ˉ i ( y ) , q i + ( y )) ≤ γ with probability at most ζ \zeta ζ . For every remaining pair, both probabilities exceed γ > 1 / 3 \gamma> 1/3 γ > 1/3 , which implies ∣ y − f i ∣ ≤ ϵ |y-f_i| \le\epsilon ∣ y − f i ∣ ≤ ϵ . These pairs also satisfy the condition under which outer validation accepts with probability at least 1 − ζ 1-\zeta 1 − ζ .
The preceding lemma bounded the probabilities of false acceptance and false rejection by the same parameter ζ \zeta ζ . The following lemma allows these probabilities to be bounded separately, which can reduce the number of estimator queries needed for validation.
Lemma 3.3. Let 0 < l < h < 1 0 < l < h < 1 0 < l < h < 1 , 0 < ζ < 1 0 < \zeta< 1 0 < ζ < 1 , and 0 < v a c c < 1 0 < v_{\mathrm{acc}} < 1 0 < v acc < 1 . Run the estimator n n n times. Accept the stored score y y y if at least k k k outputs are at most y y y and at least k k k outputs are at least y y y .
If
Pr { Bin ( n , l ) ≥ k } ≤ ζ , Pr { Bin ( n , h ) < k } ≤ 1 − v a c c 2 , (14) \Pr\{\operatorname{Bin}(n,l) \ge k\} \le\zeta,\qquad\Pr\{\operatorname{Bin}(n,h) < k\} \le\frac{1-v_{\mathrm{acc}}}{2}, \tag*{(14)} Pr { Bin ( n , l ) ≥ k } ≤ ζ , Pr { Bin ( n , h ) < k } ≤ 2 1 − v acc , (14) then the procedure accepts with probability at most ζ \zeta ζ when min ( q ˉ i ( y ) , q i + ( y ) ) ≤ l \min(\bar{q}_i(y),q_i^+(y)) \le l min ( q ˉ i ( y ) , q i + ( y )) ≤ l , and with probability at least v a c c v_{\mathrm{acc}} v acc when both probabilities are at least h h h . These bounds hold in every sector after conditioning on the measurement outcomes and classical random choices before validation.
Proof. Fix the sector i i i and the stored score y y y . By Definition 2.1 , the estimates collected during validation are independent with distribution Y i Y_i Y i , regardless of the measurement outcomes and classical random choices before validation.
Let N − N^- N − be the number of the estimator outputs at most y y y , and let N + N^+ N + be the number of estimator outputs at least y y y . By Definition 2.1 ,
N − ∼ Bin ( n , q ˉ i ( y ) ) , N + ∼ Bin ( n , q i + ( y ) ) . N^- \sim\operatorname{Bin}(n,\bar{q}_i(y)),\qquad N^+ \sim\operatorname{Bin}(n,q_i^+(y)). N − ∼ Bin ( n , q ˉ i ( y )) , N + ∼ Bin ( n , q i + ( y )) .
If q ˉ i ( y ) ≤ l \bar{q}_i(y) \le l q ˉ i ( y ) ≤ l , then
Pr { a c c e p t } ≤ Pr { N − ≥ k } ≤ Pr { Bin ( n , l ) ≥ k } ≤ ζ . \Pr\{\mathrm{accept}\} \le\Pr\{N^- \ge k\} \le\Pr\{\operatorname{Bin}(n,l) \ge k\} \le\zeta. Pr { accept } ≤ Pr { N − ≥ k } ≤ Pr { Bin ( n , l ) ≥ k } ≤ ζ .
The second inequality holds because the probability of at least k k k successes increases with the success probability. The same argument applies if q i + ( y ) ≤ l q_i^+(y) \le l q i + ( y ) ≤ l .
If both probabilities are at least h h h , then
Pr { r e j e c t } ≤ Pr { N − < k } + Pr { N + < k } ≤ 2 Pr { Bin ( n , h ) < k } ≤ 1 − v a c c . \Pr\{\mathrm{reject}\} \le\Pr\{N^- < k\}+\Pr\{N^+ < k\} \le2\Pr\{\operatorname{Bin}(n,h) < k\} \le1-v_{\mathrm{acc}}. Pr { reject } ≤ Pr { N − < k } + Pr { N + < k } ≤ 2 Pr { Bin ( n , h ) < k } ≤ 1 − v acc .
Both counts use the same estimator outputs. They are not required to be independent, since the bound on the rejection probability follows from a union bound.
The same guarantees follow from Lemma 3.2 by choosing its error parameter η \eta η so that
0 < η < 1 2 , η ≤ min { ζ , 1 − v a c c } . 0 < \eta< \frac{1}{2},\qquad\eta\le\min\{\zeta,1-v_{\mathrm{acc}}\}. 0 < η < 2 1 , η ≤ min { ζ , 1 − v acc } .
Choosing n n n and k k k directly from the two binomial inequalities in (14) can reduce the number of estimator queries, as illustrated in Appendix § 13 .§ 2 .
Coherent proposal generation
Given a threshold τ \tau τ , we construct a trial that seeks a candidate with a stored estimate y < τ y < \tau y < τ . The trial uses coherent filters based on the probabilities in (8) to suppress bad pairs and interleaves these filters with amplitude amplification to increase the probability of obtaining an acceptable pair. We also derive bounds on the number of queries and qubits used by each trial.
Polynomial filters
For each filter, we give a lower bound on the probability of accepting a good pair and an upper bound on the probability of accepting a bad pair. These bounds depend on the thresholds α , β \alpha,\beta α , β in (9) and on an error parameter for each filter.
The initialized block of a unitary is obtained by projecting its work registers onto the all-zero state at both the input and output. We also call this the clean block.
The estimator workspace containing the stored estimate is written Y G 0 YG_0 Y G 0 , where Y Y Y contains the encoded estimate and G 0 G_0 G 0 the remaining work registers. These registers are kept coherent during the trials. Let Q y Q_y Q y project onto the basis states of Y Y Y that decode to y y y , and define
Π ~ i , y = Π i ⊗ Q y . \widetilde{\Pi}_{i,y}=\Pi_i\otimes Q_y. Π i , y = Π i ⊗ Q y .
For either comparison Y i ≤ y Y_i\leq y Y i ≤ y or Y i ≥ y Y_i\geq y Y i ≥ y , let E y E_y E y project onto the estimator-output subspace whose decoded values satisfy that comparison. The Hermitian unitary
J y = A † ( I − 2 E y ) A J_y=A^\dagger(I-2E_y)A J y = A † ( I − 2 E y ) A
has initialized block 1 − 2 q i ± ( y ) 1-2q_i^{\pm}(y) 1 − 2 q i ± ( y ) . Put
a s e l = 1 2 − α − β , x ( q ) = α + β − 2 q 2 − α − β , g = β − α 2 − α − β > 0. (15) a_{\mathrm{sel}}=\frac{1}{2-\alpha-\beta},\qquad x(q)=\frac{\alpha+\beta-2q}{2-\alpha-\beta},\qquad g=\frac{\beta-\alpha}{2-\alpha-\beta}>0. \tag*{(15)} a sel = 2 − α − β 1 , x ( q ) = 2 − α − β α + β − 2 q , g = 2 − α − β β − α > 0. (15)
On a selector qubit, prepare V 0 ∣ 0 ⟩ = a s e l ∣ 0 ⟩ + 1 − a s e l ∣ 1 ⟩ V_0\lvert0\rangle=\sqrt{a_{\mathrm{sel}}}\lvert0\rangle+\sqrt{1-a_{\mathrm{sel}}}\lvert1\rangle V 0 ∣ 0 ⟩ = a sel ∣ 0 ⟩ + 1 − a sel ∣ 1 ⟩ and define
U y = ( V 0 † ⊗ I ) ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ J y − ∣ 1 ⟩ ⟨ 1 ∣ ⊗ I ) ( V 0 ⊗ I ) . (16) U_y=(V_0^\dagger\otimes I)(\lvert0\rangle\langle0\rvert\otimes J_y-\lvert1\rangle\langle1\rvert\otimes I)(V_0\otimes I). \tag*{(16)} U y = ( V 0 † ⊗ I ) (∣ 0 ⟩ ⟨ 0 ∣ ⊗ J y − ∣ 1 ⟩ ⟨ 1 ∣ ⊗ I ) ( V 0 ⊗ I ) . (16)
Its initialized block is X = ∑ i , y x ( q i + ( y ) ) Π ~ i , y X=\sum_{i,y}x(q_i^{+}(y))\widetilde{\Pi}_{i,y} X = ∑ i , y x ( q i + ( y )) Π i , y . The range of x x x lies in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , and
q ≤ α ⟹ x ( q ) ≥ g , q ≥ β ⟹ x ( q ) ≤ − g . (17) q\leq\alpha\Longrightarrow x(q)\geq g,\qquad q\geq\beta\Longrightarrow x(q)\leq-g. \tag*{(17)} q ≤ α ⟹ x ( q ) ≥ g , q ≥ β ⟹ x ( q ) ≤ − g . (17)
For each level ℓ \ell ℓ , choose 0 < u ℓ < 1 0<u_\ell<1 0 < u ℓ < 1 and an odd real polynomial φ ℓ \varphi_\ell φ ℓ of degree d ℓ d_\ell d ℓ , bounded by one on [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , such that
∣ φ ℓ ( x ) − sign ( x ) ∣ ≤ u ℓ for g ≤ ∣ x ∣ ≤ 1. (18) \lvert\varphi_\ell(x)-\operatorname{sign}(x)\rvert\leq u_\ell\qquad\text{for }g\leq\lvert x\rvert\leq1. \tag*{(18)} ∣ φ ℓ ( x ) − sign ( x )∣ ≤ u ℓ for g ≤ ∣ x ∣ ≤ 1. (18)
Appendix § 11 .§ 1 constructs such polynomials with d ℓ = O ( g − 1 log ( 2 / u ℓ ) ) d_\ell=O(g^{-1}\log(2/u_\ell)) d ℓ = O ( g − 1 log ( 2/ u ℓ )) . Thus a geometrically decreasing u ℓ u_\ell u ℓ gives d ℓ = O ( ℓ + 1 ) d_\ell=O(\ell+1) d ℓ = O ( ℓ + 1 ) for fixed margins. We assume this degree bound when deriving the uniform asymptotic resource bounds.
Lemma 4.1. For every ℓ ≥ 0 \ell\geq0 ℓ ≥ 0 , there is a full unitary T ℓ T_\ell T ℓ on C Y CY C Y and a common O ( w ) O(w) O ( w ) -qubit work register W 0 W_0 W 0 whose initialized block is
( I ⊗ ⟨ 0 ∣ W 0 ) T ℓ ( I ⊗ ∣ 0 ⟩ W 0 ) = ∑ z k ℓ ( z ) Π ~ z , 0 ≤ k ℓ ( z ) ≤ 1. (19) (I\otimes\langle0\vert_{W_0})T_\ell(I\otimes\lvert0\rangle_{W_0})=\sum_z k_\ell(z)\widetilde{\Pi}_z,\qquad0\leq k_\ell(z)\leq1. \tag*{(19)} ( I ⊗ ⟨ 0 ∣ W 0 ) T ℓ ( I ⊗ ∣ 0 ⟩ W 0 ) = z ∑ k ℓ ( z ) Π z , 0 ≤ k ℓ ( z ) ≤ 1. (19) Its scalar acceptance probability e ℓ ( z ) = k ℓ ( z ) 2 e_\ell(z)=k_\ell(z)^2 e ℓ ( z ) = k ℓ ( z ) 2 obeys
e ℓ ( z ) ≥ ( 1 − u ℓ / 2 ) 4 ( z ∈ G ) , e ℓ ( z ) ≤ ( u ℓ / 2 ) 2 ( z ∈ B ) . (20) e_\ell(z)\geq(1-u_\ell/2)^4\quad(z\in G),\qquad e_\ell(z)\leq(u_\ell/2)^2\quad(z\in B). \tag*{(20)} e ℓ ( z ) ≥ ( 1 − u ℓ /2 ) 4 ( z ∈ G ) , e ℓ ( z ) ≤ ( u ℓ /2 ) 2 ( z ∈ B ) . (20) The filter, its inverse, and controlled versions use at most 4 d ℓ 4d_\ell 4 d ℓ base-estimator queries, no preparation queries, and no controlled unknown oracle. They are independent of the incumbent threshold and act as the identity on preparation references and stored sampling garbage.
Proof. Real-polynomial QSVT [9 Corollary 18] applied to U y U_y U y produces a unitary S ℓ S_\ell S ℓ with clean block φ ℓ ( X ) \varphi_\ell(X) φ ℓ ( X ) , using d ℓ d_\ell d ℓ signal traversals. For a Hermitian block, an odd singular-value transformation equals the corresponding signed eigenvalue polynomial. The real-polynomial selector combines opposite phase sequences using the same number of traversals and a constant number of extra qubits.
On an additional selector qubit h h h , the unitary X h H h ctrl h ( S ℓ ) H h X_h H_h \operatorname{ctrl}_h(S_\ell) H_h X h H h ctrl h ( S ℓ ) H h has clean block
k ℓ ± ( i , y ) = 1 − φ ℓ ( x ( q i ± ( y ) ) ) 2 ∈ [ 0 , 1 ] . k_\ell^\pm(i,y)=\frac{1-\varphi_\ell(x(q_i^\pm(y)))}{2}\in[0,1]. k ℓ ± ( i , y ) = 2 1 − φ ℓ ( x ( q i ± ( y ))) ∈ [ 0 , 1 ] .
Use separate work for the two comparisons and multiply these blocks. Each is scalar on a sector/score block and acts trivially on the other’s work, so k ℓ = k ℓ − k ℓ + k_\ell=k_\ell^-k_\ell^+ k ℓ = k ℓ − k ℓ + . On G G G , both factors are at least 1 − u ℓ / 2 1-u_\ell/2 1 − u ℓ /2 . On B B B , at least one is at most u ℓ / 2 u_\ell/2 u ℓ /2 . Squaring gives (20) .
One signal traversal uses two base-estimator queries. Controlled traversals require no controlled estimator, since for every known control condition b b b ,
ctrl b J y = A † ctrl b ( I − 2 E y ) A . (21) \operatorname{ctrl}_b J_y=A^\dagger\operatorname{ctrl}_b(I-2E_y)A. \tag*{(21)} ctrl b J y = A † ctrl b ( I − 2 E y ) A . (21)
The oracle operations cancel on inactive branches over the full workspace. Both base-estimator queries are still counted. The selector preparation and unpreparation also cancel there. Thus each comparison uses 2 d ℓ 2d_\ell 2 d ℓ base-estimator queries, giving 4 d ℓ 4d_\ell 4 d ℓ in total, including for controlled and inverse filters. Acceptance tests all work, including the selectors. The phase list is classical; quantum width is independent of ℓ \ell ℓ .
For subsequent bounds, choose any certified numbers
0 < r ℓ ≤ ( 1 − u ℓ / 2 ) 4 , ( u ℓ / 2 ) 2 ≤ b ℓ ≤ 1. (22) 0<r_\ell\leq(1-u_\ell/2)^4,\qquad(u_\ell/2)^2\leq b_\ell\leq1. \tag*{(22)} 0 < r ℓ ≤ ( 1 − u ℓ /2 ) 4 , ( u ℓ /2 ) 2 ≤ b ℓ ≤ 1. (22)
Then e ℓ ≥ r ℓ e_\ell\geq r_\ell e ℓ ≥ r ℓ on G G G and e ℓ ≤ b ℓ e_\ell\leq b_\ell e ℓ ≤ b ℓ on B B B . These certificates can use either analytic error bounds or exact polynomial integration.
The threshold τ \tau τ can be imposed by appending a flag qubit h τ h_\tau h τ to W 0 W_0 W 0 . Define T ^ ℓ ( τ ) \widehat{T}_\ell(\tau) T ℓ ( τ ) by applying T ℓ T_\ell T ℓ and flipping h τ h_\tau h τ when y ≥ τ y\geq\tau y ≥ τ . Its clean block on z z z is
k ℓ ( z ) 1 { y < τ } . k_\ell(z)1_{\{y<\tau\}}. k ℓ ( z ) 1 { y < τ } .
Write W = W 0 h τ W=W_0h_\tau W = W 0 h τ for the common workspace used at every recursive level.
Remark 4.2. We use exact known gates, as permitted by the query model in § 2 . Appendix § 11 .§ 3 bounds the effect of approximating these gates on the full computation.
Amplification with reusable workspace
We combine the filters with amplitude amplification to construct recursive trials that accept only estimates below τ \tau τ . Fix a maximum depth K ≥ 1 K\geq1 K ≥ 1 , and introduce a counter register D D D with labels 0 , … , K 0,\ldots,K 0 , … , K . The label 0 0 0 denotes the active component and the other labels identify the first filter that rejected a component. Subsequent filters act only on the active component. The filter workspace is in the zero state on this component and can therefore be reused at every level. Let
Π = ∣ 0 ⟩ ⟨ 0 ∣ D ⊗ I \Pi=|0\rangle\langle0|_D\otimes I Π = ∣0 ⟩ ⟨ 0 ∣ D ⊗ I
be the projector onto the active subspace.
For 0 ≤ ℓ < K 0\leq\ell<K 0 ≤ ℓ < K , define the unitary F ℓ ( τ ) F_\ell(\tau) F ℓ ( τ ) by applying T ^ ℓ ( τ ) \widehat{T}_\ell(\tau) T ℓ ( τ ) controlled on D = 0 D=0 D = 0 , followed by swapping counter values 0 0 0 and ℓ + 1 \ell+1 ℓ + 1 conditional on W ≠ 0 W\neq0 W = 0 .
Let R 0 = I − 2 ∣ 0 ⟩ ⟨ 0 ∣ R_0 = I - 2|0\rangle\langle0| R 0 = I − 2∣0 ⟩ ⟨ 0∣ be the reflection about the all-zero state of all trial registers. This reflection and comparisons on D D D use only known gates. Define
B 1 ( τ ) = F 0 ( τ ) B p r e p , (23) B_1(\tau) = F_0(\tau)B_{\mathrm{prep}}, \tag*{(23)} B 1 ( τ ) = F 0 ( τ ) B prep , (23)
B j + 1 ( τ ) = F j ( τ ) [ − B j ( τ ) R 0 B j ( τ ) † ( I − 2 Π ) ] B j ( τ ) , 1 ≤ j < K . (24) B_{j+1}(\tau) = F_j(\tau)\left[-B_j(\tau)R_0B_j(\tau)^\dagger(I-2\Pi)\right]B_j(\tau), \qquad1 \leq j < K. \tag*{(24)} B j + 1 ( τ ) = F j ( τ ) [ − B j ( τ ) R 0 B j ( τ ) † ( I − 2Π ) ] B j ( τ ) , 1 ≤ j < K . (24)
The bracketed operator performs one amplitude-amplification step on the active component before the next filter is applied.
When the new filter at level ℓ \ell ℓ is applied, only counter labels 0 , … , ℓ 0,\ldots,\ell 0 , … , ℓ are occupied, and the active component has W = 0 W=0 W = 0 . For components rejected at this level, the swap changes the counter label from 0 0 0 to ℓ + 1 \ell+1 ℓ + 1 . The active component can reuse the filter workspace at the next level.
A trial of depth j j j applies B j ( τ ) B_j(\tau) B j ( τ ) to the all-zero state and tests whether D = 0 D=0 D = 0 . If so, it measures the stored score.
Proposal probabilities
Lemma 4.3. For every threshold τ \tau τ , write B j ( τ ) ∣ 0 ⟩ = g j + χ j B_j(\tau)|0\rangle= g_j+\chi_j B j ( τ ) ∣0 ⟩ = g j + χ j , where g j = Π B j ( τ ) ∣ 0 ⟩ g_j=\Pi B_j(\tau)|0\rangle g j = Π B j ( τ ) ∣0 ⟩ and Π χ j = 0 \Pi\chi_j=0 Π χ j = 0 . The active workspace is zero, and χ j \chi_j χ j uses only counter values 1 , … , j 1,\ldots,j 1 , … , j . Define
ω j ( z ) = π z ∏ ℓ = 0 j − 1 ϵ ℓ ( z ) , R j ( τ ) = ∑ z ∈ S : y < τ ω j ( z ) , H j ( τ ) = ∑ z ∈ B : y < τ ω j ( z ) . (25) \omega_j(z)=\pi_z\prod_{\ell=0}^{j-1} \epsilon_\ell(z), \qquad R_j(\tau)=\sum_{z\in S:y<\tau}\omega_j(z), \qquad H_j(\tau)=\sum_{z\in B:y<\tau}\omega_j(z). \tag*{(25)} ω j ( z ) = π z ℓ = 0 ∏ j − 1 ϵ ℓ ( z ) , R j ( τ ) = z ∈ S : y < τ ∑ ω j ( z ) , H j ( τ ) = z ∈ B : y < τ ∑ ω j ( z ) . (25) There are real numbers c j ( τ ) c_j(\tau) c j ( τ ) such that
Pr { active and pair z } = c j ( τ ) 2 ω j ( z ) 1 { y < τ } , s j : = ∥ g j ∥ 2 = c j 2 ( R j + H j ) . (26) \Pr\{\text{active and pair }z\}=c_j(\tau)^2\omega_j(z)1_{\{y<\tau\}}, \qquad s_j:=\lVert g_j\rVert^2=c_j^2(R_j+H_j). \tag*{(26)} Pr { active and pair z } = c j ( τ ) 2 ω j ( z ) 1 { y < τ } , s j := ∥ g j ∥ 2 = c j 2 ( R j + H j ) . (26) with c 1 = 1 c_1=1 c 1 = 1 , c j + 1 = ( 3 − 4 s j ) c j c_{j+1}=(3-4s_j)c_j c j + 1 = ( 3 − 4 s j ) c j , and ∣ c j ∣ ≤ 3 j − 1 |c_j|\leq3^{j-1} ∣ c j ∣ ≤ 3 j − 1 . The preparation cost is exactly 3 j − 1 3^{j-1} 3 j − 1 , and the estimator cost q j A q_j^A q j A obeys
q 1 A = 1 + 4 d 0 , q j + 1 A = 3 q j A + 4 d j , q j A = O ( 3 j − 1 ) . (27) q_1^A=1+4d_0,\qquad q_{j+1}^A=3q_j^A+4d_j,\qquad q_j^A=O(3^{j-1}). \tag*{(27)} q 1 A = 1 + 4 d 0 , q j + 1 A = 3 q j A + 4 d j , q j A = O ( 3 j − 1 ) . (27) The circuit B j ( τ ) B_j(\tau) B j ( τ ) uses O ( s P + w + log ( K + 1 ) ) O(s_P+w+\log(K+1)) O ( s P + w + log ( K + 1 )) qubits.
Proof. The first filter leaves active amplitude k 0 ( z ) k_0(z) k 0 ( z ) times the prepared pair amplitude, with all its work zero. It records rejection in label 1. For an arbitrary normalized g + χ g+\chi g + χ with g g g active and s = ∥ g ∥ 2 s=\lVert g\rVert^2 s = ∥ g ∥ 2 , the expression in square brackets in (24) maps
g + χ ⟼ ( 3 − 4 s ) g + ( 1 − 4 s ) χ . g+\chi\longmapsto(3-4s)g+(1-4s)\chi. g + χ ⟼ ( 3 − 4 s ) g + ( 1 − 4 s ) χ .
This follows by expanding the reflection B j R 0 B j † B_jR_0B_j^\dagger B j R 0 B j † about B j ∣ 0 ⟩ B_j|0\rangle B j ∣0 ⟩ . Applying F j F_j F j then multiplies each active pair amplitude by k j ( z ) k_j(z) k j ( z ) and sends newly rejected work to the unused counter label j + 1 j+1 j + 1 . Older rejected counter values are unchanged. Induction proves the active workspace invariant and (26) . Repeated threshold indicators reduce to the same strict indicator, and ∣ 3 − 4 s j ∣ ≤ 3 |3-4s_j|\leq3 ∣3 − 4 s j ∣ ≤ 3 .
The recursion for B j + 1 B_{j+1} B j + 1 uses two calls to B j B_j B j , one to its inverse B j † B_j^\dagger B j † , and an additional filter. Thus the query recurrences are exact for the indicated implementation, or upper bounds when a filter uses fewer traversals. Since d ℓ = O ( ℓ + 1 ) d_\ell=O(\ell+1) d ℓ = O ( ℓ + 1 ) , the geometric sum gives
q j A 3 j − 1 = 1 + ∑ ℓ < j 4 d ℓ 3 ℓ = O ( 1 ) . \frac{q_j^A}{3^{j-1}}=1+\sum_{\ell<j}\frac{4d_\ell}{3^\ell}=O(1). 3 j − 1 q j A = 1 + ℓ < j ∑ 3 ℓ 4 d ℓ = O ( 1 ) .
All three recursive calls act sequentially on the same registers. The recursion can be unrolled classically into a gate sequence, without requiring a quantum register to keep track of the recursive calls. Rejection labels require only ⌈ log 2 ( K + 1 ) ⌉ \lceil\log_{2}(K+1)\rceil ⌈ log 2 ( K + 1 )⌉ qubits, and all filter work has width O ( w ) O(w) O ( w ) .
The nonnegative weights ω j \omega_j ω j depend on the level but not on τ \tau τ . They are nonincreasing with j j j on every pair, and R j R_j R j is nondecreasing in τ \tau τ . Thus an accepted update makes every R j ( τ ) R_j(\tau) R j ( τ ) nonincreasing. The score can decrease without a strict decrease in acceptable rank, because an accepted pair can lie outside S S S . Define the certified retention and amplified leakage at depth j j j by
r ⋆ ( j ) = ∏ ℓ = 0 j − 1 r ℓ , Λ j = g j − 1 ∏ ℓ = 0 j − 1 b ℓ . (28) r_\star(j)=\prod_{\ell=0}^{j-1}r_\ell,\qquad\Lambda_j=g^{j-1}\prod_{\ell=0}^{j-1}b_\ell. \tag*{(28)} r ⋆ ( j ) = ℓ = 0 ∏ j − 1 r ℓ , Λ j = g j − 1 ℓ = 0 ∏ j − 1 b ℓ . (28)
Then
ω j ( z ) ≥ r ⋆ ( j ) π z ( z ) ( z ∈ G ) , g j − 1 H j ( τ ) ≤ Λ j . (29) \omega_j(z)\ge r_\star(j)\pi_z(z)\quad(z\in G),\qquad g^{j-1}H_j(\tau)\le\Lambda_j. \tag*{(29)} ω j ( z ) ≥ r ⋆ ( j ) π z ( z ) ( z ∈ G ) , g j − 1 H j ( τ ) ≤ Λ j . (29)
Thus r ⋆ ( j ) r_\star(j) r ⋆ ( j ) lower-bounds the fraction of each good pair’s initial weight remaining after filtering, and Λ j \Lambda_j Λ j upper-bounds the active probability contributed by unacceptable pairs after amplification. For a uniform asymptotic schedule we will certify constants r ⋆ > 0 r_\star>0 r ⋆ > 0 and Λ ≥ 0 \Lambda\ge0 Λ ≥ 0 satisfying
r ⋆ ( j ) ≥ r ⋆ ( j ≥ 1 ) , ∑ j ≥ 1 Λ j ≤ Λ . (30) r_\star(j)\ge r_\star\quad(j\ge1),\qquad\sum_{j\ge1}\Lambda_j\le\Lambda. \tag*{(30)} r ⋆ ( j ) ≥ r ⋆ ( j ≥ 1 ) , j ≥ 1 ∑ Λ j ≤ Λ. (30)
These quantities retain the dependence on the filter choices. Appendix § 11 .§ 2 proves feasibility of the uniform conditions. Appendix § 13 .§ 2 gives finite numerical schedules using the same filter certificates.
Adaptive selection
We first give conditions on the schedule, then describe the selection algorithm and state bounds on its success probability and query cost. A geometric schedule proves the asymptotic result. The schedule and inner validation procedure used in the numerical comparisons are specified in Appendix § 13 .§ 2 .
The selection algorithm
The selection algorithm keeps the lowest score that passes validation, together with its candidate. Its schedule consists of a depth K K K , trial counts t 1 , … , t K t_1,\ldots,t_K t 1 , … , t K , and an inner validation procedure V \mathcal{V} V . We give sufficient conditions for these choices before describing the algorithm.
Fix a depth K ≥ 1 K\ge1 K ≥ 1 , cap scales h j ⋆ > 0 h_j^\star>0 h j ⋆ > 0 , and validation completeness 0 < v a c c < 1 0<v_{\mathrm{acc}}<1 0 < v acc < 1 . The cap scales set the target rank bounds R j ( τ ) ≤ h j ⋆ ϑ − ( j − 1 ) R_j(\tau)\le h_j^\star\vartheta^{-(j-1)} R j ( τ ) ≤ h j ⋆ ϑ − ( j − 1 ) . Choose failure allowances ε c a p , ε v a l > 0 \varepsilon_{\mathrm{cap}},\varepsilon_{\mathrm{val}}>0 ε cap , ε val > 0 with
σ = ε c a p + ε v a l < 1 / 2. \sigma=\varepsilon_{\mathrm{cap}}+\varepsilon_{\mathrm{val}}<1/2. σ = ε cap + ε val < 1/2.
With Λ j \Lambda_j Λ j from (28) , define
a j ⋆ = ∏ ℓ = 1 j − 1 [ 1 − 4 3 ( h ℓ ⋆ + Λ ℓ ) ] , η j ⋆ = v a c c ( a j ⋆ ) 2 h j ⋆ . (31) a_j^\star=\prod_{\ell=1}^{j-1}\left[1-\frac{4}{3}\left(h_\ell^\star+\Lambda_\ell\right)\right],\qquad\eta_j^\star=v_{\mathrm{acc}}(a_j^\star)^2h_j^\star. \tag*{(31)} a j ⋆ = ℓ = 1 ∏ j − 1 [ 1 − 3 4 ( h ℓ ⋆ + Λ ℓ ) ] , η j ⋆ = v acc ( a j ⋆ ) 2 h j ⋆ . (31)
The empty product is one. Require every factor to be positive and choose certified lower bounds 0 < η j ≤ η j ⋆ 0<\eta_j\le\eta_j^\star 0 < η j ≤ η j ⋆ with η j < 1 \eta_j<1 η j < 1 . Choose positive integer trial counts t j t_j t j such that
h K ⋆ ϑ − ( K − 1 ) < r ⋆ ( K ) ( 1 − 2 β ) p , ∑ j = 1 K ( 1 − η j ) t j ≤ ε c a p , T = ∑ j = 1 K t j . (32) h_K^\star\vartheta^{-(K-1)}<r_\star(K)(1-2\beta)p,\qquad\sum_{j=1}^{K}(1-\eta_j)^{t_j}\le\varepsilon_{\mathrm{cap}},\qquad T=\sum_{j=1}^{K}t_j. \tag*{(32)} h K ⋆ ϑ − ( K − 1 ) < r ⋆ ( K ) ( 1 − 2 β ) p , j = 1 ∑ K ( 1 − η j ) t j ≤ ε cap , T = j = 1 ∑ K t j . (32)
Use an inner validation procedure V \mathcal{V} V with one reusable estimator workspace, classical counts, and at most n n n estimates per invocation. Require conditional completeness at least v a c c v_{\mathrm{acc}} v acc on S S S . When min ( q i − , q i + ) ≤ γ \min(q_i^-,q_i^+) \le\gamma min ( q i − , q i + ) ≤ γ , require conditional soundness at most
ζ = ε v a l T (33) \zeta= \frac{\varepsilon_{\mathrm{val}}}{T} \tag*{(33)} ζ = T ε val (33)
Lemmas 3.2 and 3.3 provide such validation procedures. One sufficient choice is
V ( y ) = Val γ , α ( y , min { ζ , 1 − v a c c } ) . \mathcal{V}(y) = \operatorname{Val}_{\gamma,\alpha}\left(y,\min\{\zeta,1-v_{\mathrm{acc}}\}\right). V ( y ) = Val γ , α ( y , min { ζ , 1 − v acc } ) .
We now describe the selection algorithm for a schedule satisfying the conditions above. We call this constant-confidence procedure the seed algorithm.
Algorithm 1.
Given P P P , A A A , their inverses, the decoder, p p p , and a schedule K , ( t j ) K,(t_j) K , ( t j ) , V \mathcal{V} V satisfying the conditions above, initialize τ ← + ∞ \tau\leftarrow+\infty τ ← + ∞ and i n c ← ⊥ \mathrm{inc} \leftarrow\perp inc ←⊥ .
For each j = 1 , … , K j=1,\ldots,K j = 1 , … , K , perform t j t_j t j trials as follows. (a) Initialize the trial registers to zero and apply B j ( τ ) B_j(\tau) B j ( τ ) . (b) Measure D D D . If D ≠ 0 D \ne0 D = 0 , discard the trial and proceed to the next repetition. (c) Measure the stored score y y y . If y ≥ τ y \ge\tau y ≥ τ , discard the trial and proceed to the next repetition. Otherwise, run V \mathcal{V} V on the candidate with stored score y y y . (d) If validation accepts, replace the incumbent with this candidate and set τ ← y \tau\leftarrow y τ ← y . Otherwise, discard the candidate.
Return ( i n c , τ ) (\mathrm{inc},\tau) ( inc , τ ) if an incumbent was retained, and return ⊥ \perp ⊥ otherwise.
Lemma 5.1. In Algorithm 1 , each candidate produced by a completed trial may be assigned a fixed, unobserved sector i i i without changing the joint distribution of the classical transcript and the final hypothetical objective measurement X o u t X_{\mathrm{out}} X out . Here the classical transcript consists of the measurement outcomes and classical random choices.
Conditional on i i i and the transcript before a validation, the estimates used in that validation are independent and have distribution Y i Y_i Y i . Thus Lemma 3.2 applies.
The same conclusions hold for the repeated runs and additional validation in Algorithm 2.
Proof. Fix the classical transcript after a trial has ended and its score has been measured. Let ρ \rho ρ be the conditional state of the candidate register, and set
p i = Tr ( Π i ρ ) . p_i = \operatorname{Tr}(\Pi_i\rho). p i = Tr ( Π i ρ ) .
Consider n n n subsequent estimator calls, each with its workspace initialized to ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ and measured afterwards. By (1) , the joint probability of workspace outcomes x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n and sector i i i in a hypothetical sector measurement after these calls is
Pr { x 1 , … , x n , i } = p i ∏ r = 1 n ∣ ⟨ x r ∣ A i ∣ 0 ⟩ ∣ 2 . \Pr\{x_1,\ldots,x_n,i\}=p_i\prod_{r=1}^{n}\left|\langle x_r|A_i|0\rangle\right|^2. Pr { x 1 , … , x n , i } = p i r = 1 ∏ n ∣ ⟨ x r ∣ A i ∣0 ⟩ ∣ 2 .
These are the probabilities obtained by choosing i i i once with probability p i p_i p i and then generating independent workspace outcomes according to A i ∣ 0 ⟩ A_i\lvert0\rangle A i ∣ 0 ⟩ . Decoding the outcomes gives independent estimates with distribution Y i Y_i Y i .
The conditional probabilities may change depending on whether the candidate is accepted or rejected. The next estimator output still has distribution Y i Y_i Y i within a fixed fixed sector. Each new trial uses separate registers and is only dependent on the incumbent through its recorded score. Hence, even if a successful candidate replaces the incumbent, we can use the same calculation after each trial and each validation.
The argument also applies to further validation and selection of candidates returned by independent runs. Since the objective has value f i f_i f i in sector i i i , it gives the claimed joint distribution with X o u t X_{\mathrm{out}} X out .
Only the reduced state of the candidate enters the calculation. Sampling garbage and other unused auxiliary registers may therefore be discarded.
Only the candidate and its classical score need be retained after a trial. Sampling garbage and unused work may be discarded, by Lemma 5.1 . Only the current candidate and the candidate produced by a new trial need coexist. The check y < τ y < \tau y < τ is automatic for ideal active trials but makes the decreasing-threshold rule explicit.
Selection guarantee
Theorem 5.2. Under the conditions of § 5.1 , with probability at least 1 − σ 1-\sigma 1 − σ the algorithm returns a pair ( i , y ) (i,y) ( i , y ) satisfying jointly
q ˉ i ( y ) , q i + ( y ) > γ , y ≤ a p + ε . (34) \bar{q}_i(y), q_i^+(y) > \gamma,\qquad y \le a_p+\varepsilon. \tag*{(34)} q ˉ i ( y ) , q i + ( y ) > γ , y ≤ a p + ε . (34)
For a retained candidate this is a statement about its latent final sector, as in Lemma 5.1 . Sufficient worst-case budgets are
Q P s e e d = ∑ j = 1 K t j 3 j − 1 , Q A s e e d = ∑ j = 1 K t j q j A + n T . (35) Q_P^{\mathrm{seed}}=\sum_{j=1}^{K} t_j 3^{j-1},\qquad Q_A^{\mathrm{seed}}=\sum_{j=1}^{K} t_j q_j^A+nT. \tag*{(35)} Q P seed = j = 1 ∑ K t j 3 j − 1 , Q A seed = j = 1 ∑ K t j q j A + n T . (35)
where q j A q_j^A q j A satisfies (27) . The live quantum space is O ( s P + w + log ( K + 1 ) ) O(s_P+w+\log(K+1)) O ( s P + w + log ( K + 1 )) .
The following estimate applies to unnormalized strict ranks, including atoms, ties, and adaptively accepted proposals. It does not assume independence between successive thresholds.
Lemma 5.3 (Rank-cap hitting). Let ω \omega ω be nonnegative weights on a finite set of acceptable pairs and R ( τ ) = ∑ z : y < τ ω ( z ) R(\tau)=\sum_{z:y<\tau}\omega(z) R ( τ ) = ∑ z : y < τ ω ( z ) . Suppose each trial at the current threshold proposes each acceptable z z z with probability c ( τ ) 2 ω ( z ) 1 { y < τ } c(\tau)^2\omega(z)1_{\{y<\tau\}} c ( τ ) 2 ω ( z ) 1 { y < τ } . Whenever the desired cap has not been reached, suppose c ( τ ) 2 ≥ C > 0 c(\tau)^2\ge C>0 c ( τ ) 2 ≥ C > 0 , uniformly conditional on earlier history. An acceptable proposal is accepted with conditional probability at least v a c c > 0 v_{\mathrm{acc}}>0 v acc > 0 , and every accepted proposal decreases τ \tau τ to its score. Other accepted proposals are allowed, but must also decrease the threshold. For θ > 0 \theta>0 θ > 0 with v a c c C θ ≤ 1 v_{\mathrm{acc}}C\theta\le1 v acc C θ ≤ 1 , after t t t trials,
Pr { R ( τ ) > θ } ≤ ( 1 − v a c c C θ ) t ≤ exp ( − v a c c C θ t ) . \Pr\{R(\tau)>\theta\}\le(1-v_{\mathrm{acc}}C\theta)^t\le\exp(-v_{\mathrm{acc}}C\theta t). Pr { R ( τ ) > θ } ≤ ( 1 − v acc C θ ) t ≤ exp ( − v acc C θ t ) .
Proof. If total acceptable weight is at most θ \theta θ , the cap already holds. Otherwise let y ∗ y_* y ∗ be the smallest score such that acceptable pairs with y ≤ y ∗ y\le y_* y ≤ y ∗ have total weight at least θ \theta θ . Acceptable pairs with y < y ∗ y<y_* y < y ∗ have total weight less than θ \theta θ . Whenever R ( τ ) > θ R(\tau)>\theta R ( τ ) > θ , one has y ∗ < τ y_*<\tau y ∗ < τ . Thus acceptable pairs with y ≤ y ∗ y\le y_* y ≤ y ∗ remain available, and accepting any of them makes R ( τ ) ≤ θ R(\tau)\le\theta R ( τ ) ≤ θ . The conditional probability of accepting one of these pairs is at least v a c c C θ v_{\mathrm{acc}}C\theta v acc C θ . A decreasing threshold cannot undo the cap. Let F r \mathcal{F}_r F r be the history after r r r trials. On every history with R ( τ r ) > θ R(\tau_r)>\theta R ( τ r ) > θ , the conditional probability of missing the cap in trial r + 1 r+1 r + 1 is at most 1 − v a c c C θ 1-v_{\mathrm{acc}}C\theta 1 − v acc C θ . Iterating conditional expectation proves the first bound. ∎
Proof of Theorem 5.2. We show that after level j j j ,
R j ( τ ) ≤ h j ⋆ 9 − ( j − 1 ) . (36) R_j(\tau) \le h_j^\star9^{-(j-1)}. \tag*{(36)} R j ( τ ) ≤ h j ⋆ 9 − ( j − 1 ) . (36)
Fix any history up to the start of level j j j for which the bounds at earlier levels hold. Since accepted scores decrease τ \tau τ , these bounds continue to hold during level j j j . For the next trial at this level, we therefore have
s ℓ ( τ ) = c ℓ ( τ ) 2 ( R ℓ ( τ ) + H ℓ ( τ ) ) ≤ h ℓ ⋆ + Λ ℓ , 1 ≤ ℓ < j . s_\ell(\tau) = c_\ell(\tau)^2\left(R_\ell(\tau) + H_\ell(\tau)\right) \le h_\ell^\star+ \Lambda_\ell,\qquad1 \le\ell< j. s ℓ ( τ ) = c ℓ ( τ ) 2 ( R ℓ ( τ ) + H ℓ ( τ ) ) ≤ h ℓ ⋆ + Λ ℓ , 1 ≤ ℓ < j .
By the definition of a j ⋆ a_j^\star a j ⋆ and positivity of the factors,
c j ( τ ) 3 j − 1 = ∏ ℓ < j ( 1 − 4 3 s ℓ ( τ ) ) ≥ a j ⋆ > 0. \frac{c_j(\tau)}{3^{j-1}} = \prod_{\ell<j}\left(1-\frac{4}{3}s_\ell(\tau)\right) \ge a_j^\star> 0. 3 j − 1 c j ( τ ) = ℓ < j ∏ ( 1 − 3 4 s ℓ ( τ ) ) ≥ a j ⋆ > 0.
Apply Lemma 5.3 with
C = η j 9 j − 1 v a c c h j ⋆ , θ = h j ⋆ 9 − ( j − 1 ) , C = \frac{\eta_j 9^{j-1}}{v_{\mathrm{acc}}h_j^\star},\qquad\theta= h_j^\star9^{-(j-1)}, C = v acc h j ⋆ η j 9 j − 1 , θ = h j ⋆ 9 − ( j − 1 ) ,
for which c j ( τ ) 2 ≥ C c_j(\tau)^2 \ge C c j ( τ ) 2 ≥ C and v a c c C θ = η j < 1 v_{\mathrm{acc}}C\theta= \eta_j < 1 v acc C θ = η j < 1 . The probability that (36) first fails at level j j j is therefore at most ( 1 − η j ) t j (1-\eta_j)^{t_j} ( 1 − η j ) t j . Summing over j j j gives
Pr { at least one rank bound fails } ≤ ∑ j = 1 K ( 1 − η j ) t j ≤ ε c a p . \Pr\{\text{at least one rank bound fails}\} \le\sum_{j=1}^{K}(1-\eta_j)^{t_j} \le\varepsilon_{\mathrm{cap}}. Pr { at least one rank bound fails } ≤ j = 1 ∑ K ( 1 − η j ) t j ≤ ε cap .
Suppose all the rank bounds hold. If the final score satisfies τ > a p + ε \tau> a_p+\varepsilon τ > a p + ε , including τ = + ∞ \tau=+\infty τ = + ∞ , Lemma 3.1 and (29) give
R K ( τ ) ≥ r ⋆ ( K ) ( 1 − 2 β ) p > h K ⋆ 9 − ( K − 1 ) , R_K(\tau) \ge r_\star(K)(1-2\beta)p > h_K^\star9^{-(K-1)}, R K ( τ ) ≥ r ⋆ ( K ) ( 1 − 2 β ) p > h K ⋆ 9 − ( K − 1 ) ,
where the strict inequality follows from (32) . This contradicts (36) at level K K K . Hence an incumbent exists and its score is at most a p + ε a_p+\varepsilon a p + ε .
At each validation, conditional on the preceding history, the probability of accepting a pair with min { q − ( y ) , q + ( y ) } ≤ γ \min\{q_-(y),q_+(y)\}\le\gamma min { q − ( y ) , q + ( y )} ≤ γ is at most ζ \zeta ζ . By Lemma 5.1 this bound also holds for retained quantum candidates. If such a pair is not accepted during any validation, the final incumbent must satisfy q − ( y ) , q + ( y ) > γ q_-(y),q_+(y)>\gamma q − ( y ) , q + ( y ) > γ . Since there are at most T T T validations,
Pr { ( 5.4 ) fails } ≤ ε c a p + T ζ = ε c a p + ε v a l = σ . \Pr\{(5.4)\text{ fails}\} \le\varepsilon_{\mathrm{cap}}+T\zeta=\varepsilon_{\mathrm{cap}}+\varepsilon_{\mathrm{val}}=\sigma. Pr {( 5.4 ) fails } ≤ ε cap + T ζ = ε cap + ε val = σ .
At level j j j , a trial uses 3 j − 1 3^{j-1} 3 j − 1 preparation queries and at most q j A q_j^A q j A estimator queries, followed by at most n n n estimator queries for validation. Summing the costs of the t j t_j t j trials at each level therefore gives (35) . Trials and validations share the estimator workspace, so the space bound is the same as one trial plus at most s P s_P s P qubits for the incumbent.
Geometric scheduling
Assume the filter certificates satisfy (30) with r ⋆ > 0 r_\star>0 r ⋆ > 0 and Λ < 3 / 4 \Lambda<3/4 Λ < 3/4 , and d ℓ = O ( ℓ + 1 ) d_\ell=O(\ell+1) d ℓ = O ( ℓ + 1 ) . Choose fixed constants
1 3 < ρ < 1 , 0 < ϑ < 1 , h > 0 , 0 < m < r ⋆ ( 1 − 2 β ) , h 1 − ρ + Λ < 3 4 . (37) \frac{1}{3}<\rho<1,\qquad0<\vartheta<1,\qquad h>0,\qquad0<m<r_\star(1-2\beta),\qquad\frac{h}{1-\rho}+\Lambda<\frac{3}{4}. \tag*{(37)} 3 1 < ρ < 1 , 0 < ϑ < 1 , h > 0 , 0 < m < r ⋆ ( 1 − 2 β ) , 1 − ρ h + Λ < 4 3 . (37)
Each level makes three calls to the preceding level, which accounts for the lower bound on ρ \rho ρ . Fix the validation and failure constants from § 5.1 and set
K = 1 + max { 0 , ⌊ log 9 h m p ⌋ } . (38) K = 1 + \max\left\{0,\left\lfloor\log_9\frac{h}{mp}\right\rfloor\right\}. \tag*{(38)} K = 1 + max { 0 , ⌊ log 9 m p h ⌋ } . (38)
For distance d ≥ 1 d \ge1 d ≥ 1 from the last level, put
h d = h ρ d − 1 , δ d = ε c a p ( 1 − ϑ ) ϑ q d − 1 , (39) h_d = h\rho^{d-1}, \qquad\delta_d = \varepsilon_{\mathrm{cap}}(1-\vartheta)\vartheta^{qd-1}, \tag*{(39)} h d = h ρ d − 1 , δ d = ε cap ( 1 − ϑ ) ϑ q d − 1 , (39)
a d = 1 − 4 3 ( h ρ d 1 − ρ + Λ ) , η d = v a c c a d 2 h d . (40) a_d = 1-\frac{4}{3}\left(\frac{h\rho^d}{1-\rho}+\Lambda\right), \qquad\eta_d = v_{\mathrm{acc}}a_d^2h_d. \tag*{(40)} a d = 1 − 3 4 ( 1 − ρ h ρ d + Λ ) , η d = v acc a d 2 h d . (40)
Choose L d ≥ log ( 1 / δ d ) L_d \ge\log(1/\delta_d) L d ≥ log ( 1/ δ d ) with L d = Θ ( d ) L_d = \Theta(d) L d = Θ ( d ) , and set
T d = ⌈ L d η d ⌉ , t j = T K − j + 1 , h j ⋆ = h K − j + 1 , T = ∑ d = 1 K T d . (41) T_d = \left\lceil\frac{L_d}{\eta_d}\right\rceil,\qquad t_j=T_{K-j+1},\qquad h_j^\star=h_{K-j+1},\qquad T=\sum_{d=1}^{K}T_d. \tag*{(41)} T d = ⌈ η d L d ⌉ , t j = T K − j + 1 , h j ⋆ = h K − j + 1 , T = d = 1 ∑ K T d . (41)
Use symmetric validation with ζ ^ = min { ε v a l / T , 1 − v a c c } \widehat{\zeta}=\min\{\varepsilon_{\mathrm{val}}/T,1-v_{\mathrm{acc}}\} ζ = min { ε val / T , 1 − v acc } , or any certified validation procedure with the same completeness and soundness guarantees.
Corollary 5.4. The geometric schedule satisfies Theorem 5.2 and has
Q P s e e d = O ( p − 1 / 2 ) , Q A s e e d = O ( p − 1 / 2 ) , S Q s e e d = O ( s P + w + log log ( 4 / p ) ) . (42) Q_P^{\mathrm{seed}}=O(p^{-1/2}),\qquad Q_A^{\mathrm{seed}}=O(p^{-1/2}),\qquad S_Q^{\mathrm{seed}}=O(s_P+w+\log\log(4/p)). \tag*{(42)} Q P seed = O ( p − 1/2 ) , Q A seed = O ( p − 1/2 ) , S Q seed = O ( s P + w + log log ( 4/ p )) . (42) The implied constants are independent of p p p , δ \delta δ , and the number of possible estimator outputs.
Proof. For a level j j j at distance d = K − j + 1 d=K-j+1 d = K − j + 1 , the cap and leakage estimates give
∑ ℓ < j ( h ℓ ⋆ + Λ ℓ ) ≤ h ρ d 1 − ρ + Λ < 3 4 . \sum_{\ell<j}(h_\ell^\star+\Lambda_\ell)\le\frac{h\rho^d}{1-\rho}+\Lambda<\frac{3}{4}. ℓ < j ∑ ( h ℓ ⋆ + Λ ℓ ) ≤ 1 − ρ h ρ d + Λ < 4 3 .
Every product factor is positive. The elementary product bound yields a j ⋆ ≥ a d > 0 a_j^\star\ge a_d>0 a j ⋆ ≥ a d > 0 , so η d ≤ η j ⋆ \eta_d\le\eta_j^\star η d ≤ η j ⋆ . Also h < ( 3 / 4 ) ( 1 − ρ ) < 1 / 2 h<(3/4)(1-\rho)<1/2 h < ( 3/4 ) ( 1 − ρ ) < 1/2 , hence 0 < η d < 1 0<\eta_d<1 0 < η d < 1 . Taking η j = η d \eta_j=\eta_d η j = η d gives
( 1 − η j ) t j ≤ e − η d T d ≤ δ d (1-\eta_j)^{t_j}\le e^{-\eta_dT_d}\le\delta_d ( 1 − η j ) t j ≤ e − η d T d ≤ δ d
and ∑ d = 1 K δ d ≤ ε c a p \sum_{d=1}^{K}\delta_d\le\varepsilon_{\mathrm{cap}} ∑ d = 1 K δ d ≤ ε cap . The depth choice ensures
h 9 − ( K − 1 ) ≤ m p < r ⋆ ( 1 − 2 β ) p ≤ r ⋆ ( K ) ( 1 − 2 β ) p , h9^{-(K-1)}\le mp<r_\star(1-2\beta)p\le r_\star(K)(1-2\beta)p, h 9 − ( K − 1 ) ≤ m p < r ⋆ ( 1 − 2 β ) p ≤ r ⋆ ( K ) ( 1 − 2 β ) p ,
which is the final-cap condition.
The a d a_d a d have a positive constant lower bound, and T d = O ( d ρ − ( d − 1 ) ) T_d=O(d\rho^{-(d-1)}) T d = O ( d ρ − ( d − 1 ) ) . Since 3 ρ > 1 3\rho>1 3 ρ > 1 ,
Q P s e e d = 3 K − 1 ∑ d = 1 K T d 3 d − 1 = O ( 3 K − 1 ) = O ( p − 1 / 2 ) . Q_P^{\mathrm{seed}}=3^{K-1}\sum_{d=1}^{K}\frac{T_d}{3^{d-1}}=O(3^{K-1})=O(p^{-1/2}). Q P seed = 3 K − 1 d = 1 ∑ K 3 d − 1 T d = O ( 3 K − 1 ) = O ( p − 1/2 ) .
The degree condition and (27) give the same bound for base-estimator queries used by the coherent trials. Validation uses O ( T log ( 2 T ) ) O(T\log(2T)) O ( T log ( 2 T )) forward base-estimator queries. Since T = O ( K ρ − K ) T=O(K\rho^{-K}) T = O ( K ρ − K ) and K = log 9 ( 1 / p ) + O ( 1 ) K=\log_9(1/p)+O(1) K = log 9 ( 1/ p ) + O ( 1 ) as p → 0 p\to0 p → 0 , this is
O ( p − ν log 2 ( 2 / p ) ) = o ( p − 1 / 2 ) , ν = log ( 1 / ρ ) log 9 < 1 2 . O\left(p^{-\nu}\log^2(2/p)\right)=o(p^{-1/2}),\qquad\nu=\frac{\log(1/\rho)}{\log9}<\frac{1}{2}. O ( p − ν log 2 ( 2/ p ) ) = o ( p − 1/2 ) , ν = log 9 log ( 1/ ρ ) < 2 1 .
Finally, log ( K + 1 ) = O ( log log ( 4 / p ) ) \log(K+1)=O(\log\log(4/p)) log ( K + 1 ) = O ( log log ( 4/ p )) .
For every fixed admissible margin triple, Appendix § 11 .§ 2 provides geometric-error filters with r ⋆ > 0 r_\star>0 r ⋆ > 0 and arbitrarily small Λ \Lambda Λ . Thus the schedule conditions are feasible. Fixing any one universal admissible choice makes the hidden constants universal in Theorem 2.2 . Appendix § 13 .§ 1 fixes one admissible filter family and selection parameters; Appendix § 13 .§ 2 derives finite schedules directly from Theorem 5.2 for each problem size.
Confidence amplification
On the success event of Theorem 5.2 , the returned pair satisfies q i − ( y ) , q i + ( y ) > γ > 1 / 3 q_i^{-}(y),q_i^{+}(y)>\gamma>1/3 q i − ( y ) , q i + ( y ) > γ > 1/3 . This margin above 1 / 3 1/3 1/3 allows confidence amplification with outer validation while retaining a valid candidate. Fix a choice of the constant parameters in Corollary 5.4, with failure bound σ < 1 / 2 \sigma<1/2 σ < 1/2 . Choose positive constants ω b a d , ω n o n e , ω r e j \omega_{\mathrm{bad}},\omega_{\mathrm{none}},\omega_{\mathrm{rej}} ω bad , ω none , ω rej whose sum is at most one. For δ < σ \delta<\sigma δ < σ , set
R = ⌈ log ( 1 / ( ω n o n e δ ) ) log ( 1 / σ ) ⌉ , ξ = min { ω b a d δ R , ω r e j δ } . (43) R=\left\lceil\frac{\log(1/(\omega_{\mathrm{none}}\delta))}{\log(1/\sigma)}\right\rceil,\qquad\xi=\min\left\{\frac{\omega_{\mathrm{bad}}\delta}{R},\omega_{\mathrm{rej}}\delta\right\}. \tag*{(43)} R = ⌈ log ( 1/ σ ) log ( 1/ ( ω none δ )) ⌉ , ξ = min { R ω bad δ , ω rej δ } . (43)
Then R ξ + σ R + ξ ≤ δ R\xi+\sigma^{R}+\xi\leq\delta R ξ + σ R + ξ ≤ δ . The confidence-amplification procedure uses p p p , δ \delta δ and fixed design parameters; ε \varepsilon ε is used only to form the final interval.
Algorithm 2.
Use the geometric schedule from Corollary 5.4 for Algorithm 1 , with failure bound σ \sigma σ from Theorem 5.2 . If δ ≥ σ \delta\geq\sigma δ ≥ σ , run the seed algorithm once, store its output in best, and go to Step 4.
For δ < σ \delta<\sigma δ < σ , compute R R R and ξ \xi ξ from (43) and set best ← ⊥ \leftarrow\perp ←⊥ .
Repeat the following steps R R R times
(a) Run Algorithm 1 with the schedule chosen in Step 1. If it returns ⊥ \perp ⊥ , continue to the next iteration.
(b) Validate the returned candidate and score y y y using Val 1 / 3 , γ ( y , ξ ) \operatorname{Val}_{1/3,\gamma}(y,\xi) Val 1/3 , γ ( y , ξ ) from Lemma 3.2 , with n 1 / 3 , γ ( ξ ) n_{1/3,\gamma}(\xi) n 1/3 , γ ( ξ ) new estimates as specified in (11) . If the validation procedure rejects the score y y y , discard the candidate and continue to the next iteration.
(c) Use the same incumbent rule as in Algorithm 1 . If best = ⊥ =\perp =⊥ or y y y is smaller than the best score, replace best with the new candidate and score. Otherwise, discard the new candidate.
If best = ⊥ =\perp =⊥ , prepare a new candidate using the unitary P P P from § 2 and set v = 0 v=0 v = 0 . Otherwise, take the candidate and score v v v from best. Return the candidate and
( v , L , U ) = ( v , v − ε , v + ε ) , (v,L,U)=(v,v-\varepsilon,v+\varepsilon), ( v , L , U ) = ( v , v − ε , v + ε ) ,
in the form specified by Theorem 2.2 .
Proof of Theorem 2.2 . By Theorem 5.2 , an output satisfying (34) is obtained with probability at least 1 − σ 1-\sigma 1 − σ . Since γ > 1 / 3 \gamma>1/3 γ > 1/3 , the inequalities for q i − ( y ) q_i^{-}(y) q i − ( y ) and q i + ( y ) q_i^{+}(y) q i + ( y ) imply ∣ y − f i ∣ ≤ ε \lvert y-f_i\rvert\leq\varepsilon ∣ y − f i ∣ ≤ ε . Together with y ≤ a p + ε y\leq a_p+\varepsilon y ≤ a p + ε , this gives (4) . In case δ ≥ σ \delta\geq\sigma δ ≥ σ , the required probability is therefore obtained by running Algorithm 1 once.
Assume now that δ < σ \delta<\sigma δ < σ . By Lemma 5.1 , we can compute the validation probabilities conditional on the sector of each candidate. If ∣ y − f i ∣ > ε \lvert y-f_i\rvert>\varepsilon ∣ y − f i ∣ > ε , then at least one of q i − ( y ) q_i^{-}(y) q i − ( y ) and q i + ( y ) q_i^{+}(y) q i + ( y ) is at most 1 / 3 1/3 1/3 , and Lemma 3.2 gives probability at most ξ \xi ξ of accepting the score. The probability of accepting an inaccurate score in any of the R R R runs is therefore at most R ξ R\xi R ξ . Since the runs are independent, the probability that none of the outputs satisfies (34) is at most σ R \sigma^{R} σ R . If one or more outputs satisfy these inequalities, consider the first of them. Conditional on the seed outputs and their sectors, Lemma 3.2 gives probability at most ξ \xi ξ of rejecting this output. It follows that, with probability at least 1 − R ξ − σ R − ξ ≥ 1 − δ 1-R\xi-\sigma^{R}-\xi\geq1-\delta 1 − R ξ − σ R − ξ ≥ 1 − δ , an output with score at most a p + ε a_p+\varepsilon a p + ε is accepted and all accepted scores are accurate. Selecting the smallest accepted score then gives (4) .
Let B P , B A = O ( p − 1 / 2 ) B_P, B_A = O(p^{-1/2}) B P , B A = O ( p − 1/2 ) be the query bounds for one run of Algorithm 1, as given by Corollary 5.4. For δ < σ \delta< \sigma δ < σ , the choices in (43) give R = O ( u ) R = O(u) R = O ( u ) and log ( 1 / ξ ) = O ( u ) \log(1/\xi) = O(u) log ( 1/ ξ ) = O ( u ) , where u = log ( 2 / δ ) u = \log(2/\delta) u = log ( 2/ δ ) . Since each validation uses O ( log ( 1 / ξ ) ) O(\log(1/\xi)) O ( log ( 1/ ξ )) estimator calls, we obtain
Q P ≤ R B P + 1 = O ( p − 1 / 2 u ) , Q_P \le RB_P + 1 = O(p^{-1/2}u), Q P ≤ R B P + 1 = O ( p − 1/2 u ) ,
Q A ≤ R ( B A + O ( log ( 1 / ξ ) ) ) = O ( p − 1 / 2 u + u 2 ) . Q_A \le R(B_A + O(\log(1/\xi))) = O(p^{-1/2}u + u^2). Q A ≤ R ( B A + O ( log ( 1/ ξ ))) = O ( p − 1/2 u + u 2 ) .
By Corollary 5.4, Algorithm 1 uses S Q s e e d = O ( s P + w + log log ( 4 / p ) ) S_Q^{\mathrm{seed}} = O(s_P + w + \log\log(4/p)) S Q seed = O ( s P + w + log log ( 4/ p )) qubits. These registers can be reused in each repetition, and validation uses the estimator work registers. The best candidate from earlier repetitions is stored separately in at most s P s_P s P qubits. The numbers of repetitions and estimates collected so far are stored classically. The total number of qubits therefore satisfies
S Q ≤ S Q s e e d + s P = O ( s P + w + log log ( 4 / p ) ) . S_Q \le S_Q^{\mathrm{seed}} + s_P = O(s_P + w + \log\log(4/p)). S Q ≤ S Q seed + s P = O ( s P + w + log log ( 4/ p )) .
Applications
The theorem can be used with any estimator satisfying Definition 2.1 . If each application of A A A or A † A^\dagger A † requires at most q ( ϵ ) q(\epsilon) q ( ϵ ) queries to an underlying oracle, substituting this cost into Theorem 2.2 gives
Q P = O ( p − 1 / 2 u ) , Q p r i m = O ( q ( ϵ ) [ p − 1 / 2 u + u 2 ] ) , u = log ( 2 / δ ) . (44) Q_P = O(p^{-1/2}u), \qquad Q_{\mathrm{prim}} = O(q(\epsilon)[p^{-1/2}u + u^2]), \qquad u = \log(2/\delta). \tag*{(44)} Q P = O ( p − 1/2 u ) , Q prim = O ( q ( ϵ ) [ p − 1/2 u + u 2 ]) , u = log ( 2/ δ ) . (44)
We apply this substitution to amplitude estimation for bounded expectations and phase estimation for energy selection. Neither application requires controlled calls to the estimator or its inverse.
Bounded-expectation selection
Let W = ∑ i = 1 N ∣ i ⟩ ⟨ i ∣ ⊗ W i W = \sum_{i=1}^{N} \lvert i\rangle\langle i\rvert\otimes W_i W = ∑ i = 1 N ∣ i ⟩ ⟨ i ∣ ⊗ W i be a label-preserving unitary with W , W † W,W^\dagger W , W † available, and let Π 1 \Pi_1 Π 1 be a known projector on its work register. The objective is
f ( i ) = ∥ ( I ⊗ Π 1 ) W ∣ i ⟩ ∣ 0 ⟩ ∥ 2 ∈ [ 0 , 1 ] . (45) f(i) = \lVert(I \otimes\Pi_1)W\lvert i\rangle\lvert0\rangle\rVert^2 \in[0,1]. \tag*{(45)} f ( i ) = ∥( I ⊗ Π 1 ) W ∣ i ⟩ ∣ 0 ⟩ ∥ 2 ∈ [ 0 , 1 ] . (45)
For example, consider a reversible simulation with candidate label i i i as input. Measuring its loss register would give a random value Z i ∈ [ 0 , 1 ] Z_i \in[0,1] Z i ∈ [ 0 , 1 ] . For each possible value z z z of Z i Z_i Z i , a rotation controlled by the loss register maps an auxiliary qubit from ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ to 1 − z ∣ 0 ⟩ + z ∣ 1 ⟩ \sqrt{1-z}\lvert0\rangle+ \sqrt{z}\lvert1\rangle 1 − z ∣ 0 ⟩ + z ∣ 1 ⟩ . Taking Π 1 = ∣ 1 ⟩ ⟨ 1 ∣ \Pi_1 = \lvert1\rangle\langle1\rvert Π 1 = ∣ 1 ⟩ ⟨ 1 ∣ on this qubit gives f ( i ) = E [ Z i ] f(i) = \mathbb{E}[Z_i] f ( i ) = E [ Z i ] in (45) .
By using amplitude estimation [21 ] , we obtain a coherent estimator that is ϵ \epsilon ϵ -accurate with probability at least 2 / 3 2/3 2/3 , using O ( 1 / ϵ ) O(1/\epsilon) O ( 1/ ϵ ) calls to W W W and W † W^\dagger W † . Both W W W and W † W^\dagger W † preserve the label, and the remaining operations act only on the work register. To control a Grover operator, we place controls on the known reflections, leaving the calls to W W W and W † W^\dagger W † uncontrolled. When the control qubit is 0, the reflections act as the identity and the two oracle calls cancel.
Standard phase-estimation-based amplitude estimation uses O ( w W + log ( 2 / ϵ ) ) O(w_W + \log(2/\epsilon)) O ( w W + log ( 2/ ϵ )) work qubits, where w W w_W w W is the work width of W W W . Classical samples alone do not provide coherent access to W W W and W † W^\dagger W † .
Corollary 6.1. Assume (45) , and let P P P independently prepare a prior μ \mu μ on the labels. For known 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 , 0 < η < 1 0 < \eta< 1 0 < η < 1 , and 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 , an algorithm returns a label s s s such that, simultaneously for every a a a with μ { f ≤ a } ≥ p \mu\{f \le a\} \ge p μ { f ≤ a } ≥ p ,
Pr { f ( s ) ≤ a + η } ≥ 1 − δ . \Pr\{f(s) \le a + \eta\} \ge1 - \delta. Pr { f ( s ) ≤ a + η } ≥ 1 − δ . It also returns the certificate (6) at numerical precision ε = η / 2 \varepsilon= \eta/2 ε = η /2 . With u = log ( 2 / δ ) u = \log(2/\delta) u = log ( 2/ δ ) , its worst-case query bounds are
Q P = O ( p − 1 / 2 u ) , Q W = O ( η − 1 ( p − 1 / 2 u + u 2 ) ) . (46) Q_P = O(p^{-1/2}u), \qquad Q_W = O\left(\eta^{-1}(p^{-1/2}u + u^2)\right). \tag*{(46)} Q P = O ( p − 1/2 u ) , Q W = O ( η − 1 ( p − 1/2 u + u 2 ) ) . (46) Its live quantum space is O ( s P + w W + log ( 2 / η ) + log log ( 4 / p ) ) O(s_P + w_W + \log(2/\eta) + \log\log(4/p)) O ( s P + w W + log ( 2/ η ) + log log ( 4/ p )) . Neither controlled P P P nor controlled W W W is required.
Proof. Use amplitude estimation at precision ε = η / 2 \varepsilon= \eta/2 ε = η /2 as the base estimator in Theorem 2.2 . Its exact label-preserving form satisfies Definition 2.1 . Substitute q ( ε ) = O ( 1 / η ) q(\varepsilon) = O(1/\eta) q ( ε ) = O ( 1/ η ) in (44) . The space bound follows from the estimator width. The successful event of the main theorem implies all the stated target inequalities jointly.
For uniform preparation, the constant-confidence query bound is worst-case optimal.
Corollary 6.2. For N ≥ 2 N \ge2 N ≥ 2 and 0 < η < 1 0 < \eta< 1 0 < η < 1 , returning an η \eta η -optimal label,
f ( s ) ≤ min i f ( i ) + η , f(s) \le\min_i f(i) + \eta, f ( s ) ≤ i min f ( i ) + η , with probability at least 2 / 3 2/3 2/3 has worst-case query complexity Θ ( N / η ) \Theta(\sqrt{N}/\eta) Θ ( N / η ) in the model (45) . Failure at most δ \delta δ is achieved with
Q W = O ( η − 1 ( N u + u 2 ) ) , u = log ( 2 / δ ) , Q_W = O\left(\eta^{-1}(\sqrt{N}u + u^2)\right), \qquad u = \log(2/\delta), Q W = O ( η − 1 ( N u + u 2 ) ) , u = log ( 2/ δ ) , on every execution and O ( w W + log ( 2 N ) + log ( 2 / η ) ) O(w_W + \log(2N) + \log(2/\eta)) O ( w W + log ( 2 N ) + log ( 2/ η )) live qubits. The bounds also hold with controlled access to W W W and W † W^\dagger W † .
Proof. With uniform preparation, each label has probability 1 / N 1/N 1/ N , so the total probability assigned to minimizing labels is at least 1 / N 1/N 1/ N . Applying Corollary 6.1 with p = 1 / N p = 1/N p = 1/ N therefore gives a label s s s satisfying f ( s ) ≤ min i f ( i ) + η f(s) \le\min_i f(i) + \eta f ( s ) ≤ min i f ( i ) + η with probability at least 1 − δ 1 - \delta 1 − δ . Uniform preparation uses O ( log ( 2 N ) ) O(\log(2N)) O ( log ( 2 N )) qubits and requires no calls to W W W or W † W^\dagger W † . Since p = 1 / N p = 1/N p = 1/ N , the additional term log log ( 4 / p ) = log log ( 4 N ) \log\log(4/p) = \log\log(4N) log log ( 4/ p ) = log log ( 4 N ) is also O ( log ( 2 N ) ) O(\log(2N)) O ( log ( 2 N )) . The matching lower bound is proved in Appendix § 12 .
For η ≥ 1 \eta\ge1 η ≥ 1 , any label is η \eta η -optimal since f ( i ) ∈ [ 0 , 1 ] f(i) \in[0,1] f ( i ) ∈ [ 0 , 1 ] . The corresponding maximization result follows by replacing Π 1 \Pi_1 Π 1 with I − Π 1 I - \Pi_1 I − Π 1 .
Table 3 compares query complexity of the proposed method with existing methods for selecting an η \eta η -optimal label. For the algorithm of Wang, You, Li, and Childs [16 Corollary 1] , the query bound also depends on the differences between the minimum objective value and the remaining values. Their bound assumes a unique minimum. Ordering the losses as f ( 1 ) < f ( 2 ) ≤ ⋯ ≤ f ( N ) f_{(1)} < f_{(2)} \le\cdots\le f_{(N)} f ( 1 ) < f ( 2 ) ≤ ⋯ ≤ f ( N ) , define
Table 3. Query and sample bounds for selecting an η \eta η -optimal label with fixed success probability, for N ≥ 2 N \ge2 N ≥ 2 and 0 < η < 1 0 < \eta< 1 0 < η < 1 . The classical bound counts independent samples; the quantum bounds count calls to the supplied coherent oracle and its inverse.
Δ i = f ( i ) − f ( 1 ) , H = ∑ i = 2 N Δ i − 2 . \Delta_i = f_{(i)} - f_{(1)}, \qquad H = \sum_{i=2}^{N} \Delta_i^{-2}. Δ i = f ( i ) − f ( 1 ) , H = i = 2 ∑ N Δ i − 2 .
For fixed positive gaps, their bound becomes independent of η \eta η when η ≤ Δ 2 \eta\le\Delta_2 η ≤ Δ 2 , since the minimum of N / η 2 N/\eta^2 N / η 2 and H H H is then H H H . Corollary 6.2 also applies when several labels attain the minimum.
The classical bound follows from median elimination [22 Theorem 10] applied to rewards 1 − Z i 1-Z_i 1 − Z i . For quantum minimum finding, using amplitude estimation with ε = η / 2 \varepsilon=\eta/2 ε = η /2 in Proposition A.1 , with p = 1 / N p=1/N p = 1/ N , results in O ( ( N / η ) log ( 2 N ) ) O((\sqrt{N}/\eta)\log(2N)) O (( N / η ) log ( 2 N )) queries. The factor log ( 2 N ) \log(2N) log ( 2 N ) comes from repeated calls to the estimator to reduce its failure probability.
The analysis of SOGAS by Hu, Hu, and Zhou [17 ] gives O ( ( N / η ) polylog ( N / ( δ η ) ) ) O((\sqrt{N}/\eta)\operatorname{polylog}(N/(\delta\eta))) O (( N / η ) polylog ( N / ( δ η ))) queries for coherent simulation with bounded output. For fixed δ \delta δ , this upper bound has the same N / η \sqrt{N}/\eta N / η factor as Corollary 6.2, together with additional factors polynomial in log ( N / η ) \log(N/\eta) log ( N / η ) .
Low-energy state preparation
Let 0 ≤ H ≤ I 0 \le H \le I 0 ≤ H ≤ I , with ground energy E 0 = λ min ( H ) E_0=\lambda_{\min}(H) E 0 = λ m i n ( H ) , and let P P P prepare a guiding state, possibly entangled with reference registers. We assume access to P , P † P,P^\dagger P , P † and controlled applications of U = e i H U=e^{iH} U = e i H and its inverse. Each controlled application counts as one evolution query, so implementing a controlled power U k U^k U k requires ∣ k ∣ |k| ∣ k ∣ queries.
For 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , coherent phase estimation [21 , 23 ] estimates the energy to accuracy ε \varepsilon ε with probability at least 2 / 3 2/3 2/3 , using O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) evolution queries and O ( log ( 2 / ε ) ) O(\log(2/\varepsilon)) O ( log ( 2/ ε )) work qubits. We decode the phase estimates in [ − π , π ) [-\pi,\pi) [ − π , π ) , which contains the energy interval [ 0 , 1 ] [0,1] [ 0 , 1 ] in its interior. Estimates outside of this energy interval are clipped to 0 or 1. This replacement does not increase the estimation error, because the true energy is in [ 0 , 1 ] [0,1] [ 0 , 1 ] . On an eigenspace with energy E E E , the evolution U U U acts as e i E I e^{iEI} e i E I , so the controlled evolutions act on the estimator’s work register in the same way for every state in that eigenspace. The estimator therefore has the form
A = ∑ i Π i ⊗ A i A=\sum_i \Pi_i\otimes A_i A = i ∑ Π i ⊗ A i
where Π i \Pi_i Π i are the energy projectors, and satisfies Definition 2.1 also when the eigenvalues are degenerate. Its construction uses only the evolution oracle and known gates.
Corollary 6.3. Suppose the guiding state has probability at least p p p on energies at most a a a , where 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 is known. For 0 < η < 1 0 < \eta< 1 0 < η < 1 and 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 , an algorithm returns a candidate whose density matrix, averaged over the algorithm’s measurement outcomes and classical random choices, has weight at least 1 − δ 1-\delta 1 − δ on energies at most a + η a+\eta a + η . It also returns the certificate (6) with ε = η / 2 \varepsilon=\eta/2 ε = η /2 . The query bounds are
Q P = O ( p − 1 / 2 u ) , Q U = O ( η − 1 ( p − 1 / 2 u + u 2 ) ) , u = log ( 2 / δ ) . (47) Q_P=O(p^{-1/2}u),\qquad Q_U=O(\eta^{-1}(p^{-1/2}u+u^2)),\qquad u=\log(2/\delta). \tag*{(47)} Q P = O ( p − 1/2 u ) , Q U = O ( η − 1 ( p − 1/2 u + u 2 )) , u = log ( 2/ δ ) . (47)
The quantum space is O ( s P + log ( 2 / η ) + log log ( 4 / p ) ) O(s_P + \log(2/\eta) + \log\log(4/p)) O ( s P + log ( 2/ η ) + log log ( 4/ p )) qubits, excluding workspace internal to the supplied evolution oracle. The threshold a a a and the spectral distribution need not be known.
Proof. Apply Theorem 2.2 with the phase estimator above and ε = η / 2 \varepsilon= \eta/2 ε = η /2 . Since the guiding state has probability at least p p p on energies at most a a a , we have a p ≤ a a_p \le a a p ≤ a . It follows that
X o u t ≤ a p + 2 ε ≤ a + η X_{\mathrm{out}} \le a_p + 2\varepsilon\le a + \eta X out ≤ a p + 2 ε ≤ a + η
with probability at least 1 − δ 1-\delta 1 − δ , which gives the stated weight in the averaged output density matrix. The estimator and its inverse each require O ( 1 / η ) O(1/\eta) O ( 1/ η ) evolution queries and O ( log ( 2 / η ) ) O(\log(2/\eta)) O ( log ( 2/ η )) work qubits. The query and space bounds follow by substituting these costs into Theorem 2.2 .
Suppose now that the guiding state has ground-space amplitude overlap at least ω > 0 \omega> 0 ω > 0 , and that a positive lower bound Δ \Delta Δ on the spectral gap is known. Choose a fixed 0 < c g a p < 1 / 2 0 < c_{\mathrm{gap}} < 1/2 0 < c gap < 1/2 and apply Theorem 2.2 with p = ω 2 p = \omega^2 p = ω 2 and ε = c g a p Δ \varepsilon= c_{\mathrm{gap}}\Delta ε = c gap Δ . Since the probability in the ground space is at least ω 2 \omega^2 ω 2 , we have a p = E 0 a_p = E_0 a p = E 0 . The theorem therefore gives
X o u t ≤ E 0 + 2 c g a p Δ < E 0 + Δ X_{\mathrm{out}} \le E_0 + 2c_{\mathrm{gap}}\Delta< E_0 + \Delta X out ≤ E 0 + 2 c gap Δ < E 0 + Δ
with probability at least 1 − δ 1-\delta 1 − δ . Every energy outside the ground space is at least E 0 + Δ E_0+\Delta E 0 + Δ , so the averaged output density matrix has ground-space weight at least 1 − δ 1-\delta 1 − δ . The query bounds become
Q P = O ( ω − 1 u ) , Q U = O ( Δ − 1 ( ω − 1 u + u 2 ) ) . Q_P = O(\omega^{-1}u), \qquad Q_U = O\left(\Delta^{-1}(\omega^{-1}u + u^2)\right). Q P = O ( ω − 1 u ) , Q U = O ( Δ − 1 ( ω − 1 u + u 2 ) ) .
Ground-state preparation from a guiding state has also been studied by Jeffery, Somma, Witteveen, and de Wolf [24 ] . For a Hamiltonian with a unique ground state, they give a transducer construction and an algorithm combining amplitude amplification with verification [24 Theorem 1.3 and Section 2] . Both use an estimate of the ground energy, which can first be obtained using the algorithm of Jeffery and Witteveen [18 Theorem 1.1] . Chen, Gao, Wang, and Zhou [25 ] study ground-state preparation using a Hamiltonian block encoding, assuming a unique ground state and a known energy threshold inside the gap. Both works bound the trace distance between the prepared state and the target state. The result above gives Pr { X o u t = E 0 } ≥ 1 − δ \Pr\{X_{\mathrm{out}} = E_0\} \ge1-\delta Pr { X out = E 0 } ≥ 1 − δ and applies to ground spaces of any dimension.
Ground-energy estimation
Consider the same Hamiltonian access model, but with the goal of only obtaining a classical energy estimate. Repeating the minimum-finding algorithm of Theorem 2.2 independently and taking the median of the resulting estimates reduces the dependence on log ( 2 / δ ) \log(2/\delta) log ( 2/ δ ) in the evolution-query bound from quadratic to linear.
Corollary 6.4. Suppose ∥ ( Π min ⊗ I R ) P ∣ 0 ⟩ ∥ ≥ ω > 0 \lVert(\Pi_{\min} \otimes I_R)P\lvert0\rangle\rVert\ge\omega> 0 ∥( Π m i n ⊗ I R ) P ∣ 0 ⟩∥ ≥ ω > 0 , where Π min \Pi_{\min} Π m i n is the ground-space projector. Given this lower bound, 0 < η < 1 / 4 0 < \eta< 1/4 0 < η < 1/4 , and 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 , an additive-η \eta η estimate of E 0 E_0 E 0 can be returned with probability at least 1 − δ 1-\delta 1 − δ using
Q P = O ( ω − 1 u ) , Q U = O ( ( ω η ) − 1 u ) , u = log ( 2 / δ ) , (48) Q_P = O(\omega^{-1}u), \qquad Q_U = O((\omega\eta)^{-1}u), \qquad u = \log(2/\delta), \tag*{(48)} Q P = O ( ω − 1 u ) , Q U = O (( ω η ) − 1 u ) , u = log ( 2/ δ ) , (48) on every execution, with no requirement of a spectral gap, initial energy estimate, or controlled preparation. The algorithm uses O ( s P + log ( 2 / η ) + log log ( 4 / ω 2 ) ) O(s_P + \log(2/\eta) + \log\log(4/\omega^2)) O ( s P + log ( 2/ η ) + log log ( 4/ ω 2 )) qubits, with the estimates and repetition counter stored classically. As in Corollary 6.3 , the qubit count excludes the internal workspace of the evolution oracle.
Proof. Set p = ω 2 p=\omega^2 p = ω 2 . Since the ground-space mass is at least p p p , the quantile in (3) is a p = E 0 a_p=E_0 a p = E 0 . Fix 0 < σ E < 1 / 2 0<\sigma_E<1/2 0 < σ E < 1/2 and run Theorem 2.2 at failure probability σ E \sigma_E σ E with phase-estimation precision ε = η \varepsilon=\eta ε = η . On its successful event,
E 0 − η ≤ X o u t − η ≤ v ≤ a p + η = E 0 + η . E_0-\eta\le X_{\mathrm{out}}-\eta\le v\le a_p+\eta=E_0+\eta. E 0 − η ≤ X out − η ≤ v ≤ a p + η = E 0 + η .
Thus with probability at least 1 − σ E 1-\sigma_E 1 − σ E , the marginal classical estimate v v v is within η \eta η of E 0 E_0 E 0 . Each run uses O ( ω − 1 ) O(\omega^{-1}) O ( ω − 1 ) preparation queries and O ( ( ω η ) − 1 ) O((\omega\eta)^{-1}) O (( ω η ) − 1 ) evolution queries. Repeat the algorithm independently m m m times, where m m m is an odd number, to obtain estimates v 1 , … , v m v_1,\ldots,v_m v 1 , … , v m , and return their median. If more than half of these estimates are in [ E 0 − η , E 0 + η ] [E_0-\eta,E_0+\eta] [ E 0 − η , E 0 + η ] , then their median belongs to the same interval. Since each run fails with probability at most σ E < 1 / 2 \sigma_E<1/2 σ E < 1/2 , a Chernoff bound gives
Pr { ∣ median ( v 1 , … , v m ) − E 0 ∣ > η } ≤ exp ( − 2 m ( 1 / 2 − σ E ) 2 ) . \Pr\{|\operatorname{median}(v_1,\ldots,v_m)-E_0|>\eta\}\le\exp\left(-2m(1/2-\sigma_E)^2\right). Pr { ∣ median ( v 1 , … , v m ) − E 0 ∣ > η } ≤ exp ( − 2 m ( 1/2 − σ E ) 2 ) .
By choosing m = O ( u ) m=O(u) m = O ( u ) , the right-hand side is at most δ \delta δ , which gives (48) . The quantum registers can be reused after recording each estimate.
Table 4 compares the query bounds for a fixed success probability. Jeffery and Witteveen [18 Theorem 1.1] obtain O ( ( ω η ) − 1 ) O((\omega\eta)^{-1}) O (( ω η ) − 1 ) controlled-evolution queries. Corollary 6.4 gives the same evolution bound with O ( ω − 1 ) O(\omega^{-1}) O ( ω − 1 ) calls to P P P and P † P^\dagger P † , improving the preparation upper bound in their theorem. To compare the evolution queries, their phase convention can be converted to ours by a constant phase shift and reversal of the evolution. Their theorem assumes controlled preparation and also gives elementary-gate and workspace bounds.
Table 4. Upper bounds for guided ground-energy estimation with fixed success probability, precision η \eta η , and ground-space amplitude overlap at least ω \omega ω . Here ℓ η = log ( 2 / η ) \ell_\eta=\log(2/\eta) ℓ η = log ( 2/ η ) . Each elementary controlled-evolution operation counts as one evolution query, and both query counts include inverse applications. The AGGW bounds follow from the phase-estimation construction described below.
For the first row, use Proposition A.1 with p = ω 2 p=\omega^2 p = ω 2 and a phase estimator of precision η \eta η . Its accurate low estimate is within η \eta η of E 0 E_0 E 0 on the successful event, by the same inequality used above. Each call to the confidence-amplified phase estimator uses O ( η − 1 log ( 2 / ω ) ) O(\eta^{-1}\log(2/\omega)) O ( η − 1 log ( 2/ ω )) elementary controlled-evolution queries. This comparison uses the controlled-evolution model, whereas AGGW’s published energy application [6 Lemma 50] is stated for sparse-Hamiltonian access.
Mande and de Wolf [19 ] establish phase-estimation and related lower bounds. Somma and de Wolf [20 Theorem 3.1] construct hard Hamiltonian families of dimension O ( ω − 2 log ( 1 / δ ) ) O(\omega^{-2}\log(1/\delta)) O ( ω − 2 log ( 1/ δ )) requiring Ω ( ( ω η ) − 1 log ( 1 / δ ) ) \Omega((\omega\eta)^{-1}\log(1/\delta)) Ω (( ω η ) − 1 log ( 1/ δ )) controlled-evolution queries, even with unlimited preparation access. After constant rescaling into [ 0 , 1 ] [0,1] [ 0 , 1 ] , this gives the matching worst-case lower bound for (48) when 0 < ω , η , δ ≤ c 0<\omega,\eta,\delta\le c 0 < ω , η , δ ≤ c and the allowed dimension is at least C ω − 2 log ( 1 / δ ) C\omega^{-2}\log(1/\delta) C ω − 2 log ( 1/ δ ) , for suitable universal constants c > 0 c>0 c > 0 and C > 0 C>0 C > 0 . Thus, the evolution-query complexity is optimal in its dependence on overlap, precision, and confidence within the stated parameter range.
Conclusion
This paper has developed a quantum minimum-finding algorithm for objective values accessed through coherent numerical estimators that avoids the logarithmic overhead of amplifying their confidence before the search. It applies to arbitrary prepared distributions and allows the selected candidate to be retained as a quantum state. Assume the preparation assigns probability mass at least a known p p p to objective values at most a a a . The algorithm uses O ( p − 1 / 2 log ( 2 / δ ) ) O(p^{-1/2}\log(2/\delta)) O ( p − 1/2 log ( 2/ δ )) preparation queries and O ( p − 1 / 2 log ( 2 / δ ) + log 2 ( 2 / δ ) ) O(p^{-1/2}\log(2/\delta) + \log^2(2/\delta)) O ( p − 1/2 log ( 2/ δ ) + log 2 ( 2/ δ )) estimator queries to select a candidate with objective value at most a + 2 ε a + 2\varepsilon a + 2 ε with probability at least 1 − δ 1 - \delta 1 − δ . At constant success probability, the estimator-query bound and the factor 2 in the selection error are separately worst-case optimal.
Uniform preparation over N N N classical labels gives p = 1 / N p = 1/N p = 1/ N and hence O ( N ) O(\sqrt{N}) O ( N ) estimator queries with additive selection error 2 ε 2\varepsilon 2 ε . Combining this result with amplitude estimation gives a worst-case optimal complexity of Θ ( N / η ) \Theta(\sqrt{N}/\eta) Θ ( N / η ) queries to the underlying oracle for selecting an η \eta η -optimal bounded expectation.
Using phase estimation, a candidate with energy at most a + η a + \eta a + η can be selected with O ( p − 1 / 2 ) O(p^{-1/2}) O ( p − 1/2 ) preparation queries and O ( p − 1 / 2 / η ) O(p^{-1/2}/\eta) O ( p − 1/2 / η ) elementary controlled-evolution queries. A guiding state with ground-space amplitude overlap at least ω \omega ω gives ground-energy estimation to additive error η \eta η using O ( ω − 1 ) O(\omega^{-1}) O ( ω − 1 ) preparation queries and O ( ( ω η ) − 1 ) O((\omega\eta)^{-1}) O (( ω η ) − 1 ) elementary controlled-evolution queries.
Further work could reduce the constants by improving the polynomial filters and validation parameters. It also remains open whether the log 2 ( 2 / δ ) \log^2(2/\delta) log 2 ( 2/ δ ) term can be removed from the estimator-query bound when the selected quantum candidate is retained.
Author contribution statement
The contributions presented in this paper were developed by the author. OpenAI’s ChatGPT was used to assist with surveying the literature, discussing mathematical ideas, and editing the manuscript.
Acknowledgements
This work was supported in part by the Research Council of Norway through the project Quantum computing for the defence sector – QC4DS (grant no. 346299).
Confidence amplification before minimum finding
This appendix analyzes implementations of AGGW [6 ] and Chen–de Wolf [7 ] that amplify the estimator’s confidence before minimum finding, under the oracle conventions in Definition 2.1 . The resulting query bounds are given in Table 1 . We first consider generalized minimum finding with arbitrary preparation, and then the specialization to uniform preparation over labels.
Table 1. Query bounds for minimum finding at constant overall confidence, using a numerical estimator that is ε \varepsilon ε -accurate with probability at least 2 / 3 2/3 2/3 on every label. All methods guarantee an additive selection error of at most 2 ε 2\varepsilon 2 ε . The first two rows concern an arbitrary preparation with qualifying mass p p p and count preparation queries. The last three rows concern N N N labels with known uniform preparation, which is free.
Proposition A.1. Suppose μ { f ≤ a } ≥ p \mu\{f \le a\} \ge p μ { f ≤ a } ≥ p . Using upfront confidence amplification , AGGW generalized minimum finding [6 Algorithm 3 and Theorem 49] can return a retained candidate and a numerical value y y y such that, jointly with probability at least 2 / 3 2/3 2/3 ,
∣ y − X o u t ∣ ≤ ε , y ≤ a + ε , X o u t ≤ a + 2 ε . |y-X_{\mathrm{out}}| \le\varepsilon,\qquad y \le a+\varepsilon,\qquad X_{\mathrm{out}} \le a+2\varepsilon. ∣ y − X out ∣ ≤ ε , y ≤ a + ε , X out ≤ a + 2 ε . The algorithm is given p p p but not a a a or μ \mu μ . On every execution it uses
Q P = O ( p − 1 / 2 ) , Q A = O ( p − 1 / 2 log ( 2 / p ) ) . Q_P = O(p^{-1/2}),\qquad Q_A = O(p^{-1/2}\log(2/p)). Q P = O ( p − 1/2 ) , Q A = O ( p − 1/2 log ( 2/ p )) . It requires no controlled P P P or controlled A A A .
Proof. For 0 < b < 1 / 2 0 < b < 1/2 0 < b < 1/2 , apply the base estimator using k = O ( log ( 2 / b ) ) k = O(\log(2/b)) k = O ( log ( 2/ b )) separate work registers initialized to ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ , where k k k is odd and sufficiently large. Computing the median reversibly gives a unitary estimator A b A_b A b with error probability at most b b b in each sector. Choose b = c p b = cp b = c p , where c > 0 c > 0 c > 0 is a sufficiently small universal constant. In sector i i i , write ∣ χ i ⟩ = A b , i ∣ 0 ⟩ \lvert\chi_i\rangle= A_{b,i}\lvert0\rangle ∣ χ i ⟩ = A b , i ∣ 0 ⟩ , let G i G_i G i project onto estimates within ε \varepsilon ε of f i f_i f i , and define
∣ χ i g ⟩ = G i ∣ χ i ⟩ ∥ G i ∣ χ i ⟩ ∥ . \lvert\chi_i^g\rangle= \frac{G_i\lvert\chi_i\rangle}{\lVert G_i\lvert\chi_i\rangle\rVert}. ∣ χ i g ⟩ = ∥ G i ∣ χ i ⟩∥ G i ∣ χ i ⟩ .
Their inner product is real and at least 1 − b \sqrt{1-b} 1 − b . Let R i R_i R i be a rotation in their span that maps ∣ χ i ⟩ \lvert\chi_i\rangle ∣ χ i ⟩ to ∣ χ i g ⟩ \lvert\chi_i^g\rangle ∣ χ i g ⟩ , and extend it by the identity on the orthogonal complement. Then
∥ R i − I ∥ = 2 − 2 ⟨ χ i g ∣ χ i ⟩ ≤ 2 b . \lVert R_i-I\rVert= \sqrt{2-2\langle\chi_i^g\mid\chi_i\rangle} \le\sqrt{2b}. ∥ R i − I ∥ = 2 − 2 ⟨ χ i g ∣ χ i ⟩ ≤ 2 b .
Let R = ∑ i Π i ⊗ R i R=\sum_i\Pi_i\otimes R_i R = ∑ i Π i ⊗ R i and define actual and ideal preparations
B = A b ( P ⊗ I ) , B ′ = R B . B=A_b(P\otimes I),\qquad B'=RB. B = A b ( P ⊗ I ) , B ′ = R B .
Then ∥ B − B ′ ∥ ≤ 2 b \lVert B-B'\rVert\le\sqrt{2b} ∥ B − B ′ ∥ ≤ 2 b , with the same bound for the inverses. The ideal preparation is used only in the analysis, its definition need not be known to the algorithm. It preserves sector masses, and all its encoded estimates are accurate. Its score law therefore assigns mass at least p p p to estimates at most a + ε a+\varepsilon a + ε .
AGGW’s capped generalized minimum-finding algorithm, with a fixed cap M = O ( p − 1 / 2 ) M=O(p^{-1/2}) M = O ( p − 1/2 ) , returns such a low score with probability at least 3 / 4 3/4 3/4 [6 Theorem 49] . Retain the registers associated with each incumbent score rather than discarding the candidate. Completed ideal proposals are restrictions of the prepared state by predicates on that score, so they remain supported on accurate sector/score pairs. In particular, a returned low score satisfies the stated candidate guarantee.
A query hybrid for the capped computation bounds the change in the probability of any final event by at most
M ∥ B − B ′ ∥ = O ( p − 1 / 2 b ) = O ( c ) . M\lVert B-B'\rVert= O(p^{-1/2}\sqrt{b}) = O(\sqrt{c}). M ∥ B − B ′ ∥ = O ( p − 1/2 b ) = O ( c ) .
This holds for measured adaptive implementations by contractivity of trace distance, and the final hypothetical objective measurement can be included in the event. Taking c c c sufficiently small makes the change at most 1 / 12 1/12 1/12 , giving success at least 2 / 3 2/3 2/3 for the actual preparation.
Each call to B B B or B † B^\dagger B † uses one preparation query and O ( log ( 2 / b ) ) = O ( log ( 2 / p ) ) O(\log(2/b)) = O(\log(2/p)) O ( log ( 2/ b )) = O ( log ( 2/ p )) base-estimator queries. The number of calls is capped at M = O ( p − 1 / 2 ) M = O(p^{-1/2}) M = O ( p − 1/2 ) , giving the worst-case query bounds. Prepared-state reflections use B B B , B † B^\dagger B † around known reflections and require no controlled access to the original unknown unitaries.
For uniform preparation over N N N labels, Chen and de Wolf [7 arXiv v2, Theorem 2.4 and Appendix A] use O ( N ) O(\sqrt{N}) O ( N ) calls to an estimator with failure probability at most b / N b/N b / N , where b > 0 b > 0 b > 0 is a sufficiently small constant. Each call is implemented by computing the median reversibly from O ( log ( 2 N ) ) O(\log(2N)) O ( log ( 2 N )) base estimates. The total query count is therefore O ( N log ( 2 N ) ) O(\sqrt{N}\log(2N)) O ( N log ( 2 N )) , with selection error 2 ε 2\varepsilon 2 ε at fixed success probability. The corresponding numerical bound in Table 5 is calculated in Appendix § 13 .§ 3 .
Table 5. Worst-case base-estimator query bounds for success probability 15 / 16 15/16 15/16 and selection error 2 ε 2\varepsilon 2 ε . Values are rounded upward to three significant figures.
For k = 1 k = 1 k = 1 , the weak and strong approximation definitions of Gao, Ji, and Wang [8 ] coincide. Their Algorithm 1 has a single iteration, starting with an empty excluded-index set. The hiding operation is therefore the identity. The algorithm then applies generalized minimum finding to a uniform label preparation followed by the numerical oracle, with target mass 1 / N 1/N 1/ N . This is the same reduction used by Chen and de Wolf [7 Appendix A] .
Implementation of filters
This appendix specifies the construction of bounded polynomial approximations to the sign function used in § 4.1 , and verifies the filter conditions in Corollary 5.4. The final subsection shows that approximating the known gates changes the success probability by at most the sum of their operator-norm errors.
Bounded sign polynomials
For an odd integer n ≥ 3 n \ge3 n ≥ 3 and an integer r ≥ 1 r \ge1 r ≥ 1 , let T n T_n T n be the Chebyshev polynomial of the first kind and define
K n , r ( x ) = ( T n ( x ) n x ) 2 r , φ n , r ( x ) = ∫ 0 x K n , r ( t ) d t ∫ 0 1 K n , r ( t ) d t , d n , r = 2 r ( n − 1 ) + 1. (49) K_{n,r}(x) = \left(\frac{T_n(x)}{nx}\right)^{2r}, \qquad\varphi_{n,r}(x) = \frac{\int_0^x K_{n,r}(t)\,\mathrm{d}t}{\int_0^1 K_{n,r}(t)\,\mathrm{d}t}, \qquad d_{n,r} = 2r(n-1)+1. \tag*{(49)} K n , r ( x ) = ( n x T n ( x ) ) 2 r , φ n , r ( x ) = ∫ 0 1 K n , r ( t ) d t ∫ 0 x K n , r ( t ) d t , d n , r = 2 r ( n − 1 ) + 1. (49)
The quotient at zero is defined by continuity. For odd n n n , T n ( x ) = ( − 1 ) ( n − 1 ) / 2 sin ( n arcsin x ) T_n(x) = (-1)^{(n-1)/2}\sin(n\arcsin x) T n ( x ) = ( − 1 ) ( n − 1 ) /2 sin ( n arcsin x ) . Thus the kernel is a nonnegative even polynomial with value one at zero. Its normalized integral is odd, nondecreasing, bounded by one on [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , and has exactly the displayed degree.
Lemma B.1. For 0 < g < 1 0 < g < 1 0 < g < 1 , the worst sign error on g ≤ ∣ x ∣ ≤ 1 g \le\lvert x\rvert\le1 g ≤ ∣ x ∣ ≤ 1 is
E n , r ( g ) = ∫ g 1 K n , r ( t ) d t ∫ 0 1 K n , r ( t ) d t ≤ 35 r 16 ( 2 r − 1 ) ( n g ) − ( 2 r − 1 ) . (50) E_{n,r}(g) = \frac{\int_g^1 K_{n,r}(t)\,\mathrm{d}t}{\int_0^1 K_{n,r}(t)\,\mathrm{d}t} \le\frac{35\sqrt{r}}{16(2r-1)}(ng)^{-(2r-1)}. \tag*{(50)} E n , r ( g ) = ∫ 0 1 K n , r ( t ) d t ∫ g 1 K n , r ( t ) d t ≤ 16 ( 2 r − 1 ) 35 r ( n g ) − ( 2 r − 1 ) . (50)
For rational g g g , the exact error is rational and computable by polynomial integration. For every 0 < u < 1 0 < u < 1 0 < u < 1 , choices with n = O ( 1 / g ) n = O(1/g) n = O ( 1/ g ) and r = O ( log ( 2 / u ) ) r = O(\log(2/u)) r = O ( log ( 2/ u )) give E n , r ( g ) ≤ u E_{n,r}(g) \le u E n , r ( g ) ≤ u and d n , r = O ( g − 1 log ( 2 / u ) ) d_{n,r} = O(g^{-1}\log(2/u)) d n , r = O ( g − 1 log ( 2/ u )) .
Proof. Monotonicity and oddness show that the maximum error occurs at x = g x=g x = g or x = − g x=-g x = − g , giving the integral expression. For 0 ≤ t ≤ 1 / ( 2 n r ) 0\le t\le1/(2n\sqrt{r}) 0 ≤ t ≤ 1/ ( 2 n r ) put z = n arcsin t z=n\arcsin t z = n arcsin t . Since n ≥ 3 n\ge3 n ≥ 3 ,
z 2 ≤ n 2 t 2 1 − t 2 ≤ 9 35 r , sin z n t ≥ 1 − 3 70 r . z^2\le\frac{n^2t^2}{1-t^2}\le\frac{9}{35r},\qquad\frac{\sin z}{nt}\ge1-\frac{3}{70r}. z 2 ≤ 1 − t 2 n 2 t 2 ≤ 35 r 9 , n t sin z ≥ 1 − 70 r 3 .
The second inequality uses z ≥ n t z\ge nt z ≥ n t , sin z ≥ z − z 3 / 6 \sin z\ge z-z^3/6 sin z ≥ z − z 3 /6 , and positivity of the displayed lower bound. The even exponent removes the sign of T n T_n T n , and Bernoulli’s inequality gives K n , r ( t ) ≥ ( 1 − 3 / ( 70 r ) ) 2 r ≥ 32 / 35 K_{n,r}(t)\ge(1-3/(70r))^{2r}\ge32/35 K n , r ( t ) ≥ ( 1 − 3/ ( 70 r ) ) 2 r ≥ 32/35 . Hence
∫ 0 1 K n , r ( t ) d t ≥ 16 35 n r . \int_0^1 K_{n,r}(t)\,\mathrm{d}t\ge\frac{16}{35n\sqrt{r}}. ∫ 0 1 K n , r ( t ) d t ≥ 35 n r 16 .
For t ∈ [ g , 1 ] t\in[g,1] t ∈ [ g , 1 ] , use ∣ T n ( t ) ∣ ≤ 1 |T_n(t)|\le1 ∣ T n ( t ) ∣ ≤ 1 . Extending the integral of the bound ( n t ) − 2 r (nt)^{-2r} ( n t ) − 2 r to infinity gives
∫ g 1 K n , r ( t ) d t ≤ n − 2 r g − ( 2 r − 1 ) 2 r − 1 . \int_g^1 K_{n,r}(t)\,\mathrm{d}t\le\frac{n^{-2r}g^{-(2r-1)}}{2r-1}. ∫ g 1 K n , r ( t ) d t ≤ 2 r − 1 n − 2 r g − ( 2 r − 1 ) .
which proves the inequality. Polynomial integration proves rationality. For the degree claim, fix any constant c > 1 c>1 c > 1 and take the least odd n ≥ max { 3 , c / g } n\ge\max\{3,c/g\} n ≥ max { 3 , c / g } . Then n g ≥ c ng\ge c n g ≥ c and n = O ( 1 / g ) n=O(1/g) n = O ( 1/ g ) . The error bound decreases exponentially in r r r , so an integer r = O ( log ( 2 / u ) ) r=O(\log(2/u)) r = O ( log ( 2/ u )) suffices. Constants here may depend on the fixed c c c .
Filter guarantees
For fixed margins, take u ℓ = u 0 χ ℓ u_\ell=u_0\chi^\ell u ℓ = u 0 χ ℓ with 0 < χ < 1 0<\chi<1 0 < χ < 1 and u 0 > 0 u_0>0 u 0 > 0 sufficiently small. Choose the polynomials by Lemma B.1 , and set r ℓ = ( 1 − u ℓ / 2 ) 4 r_\ell=(1-u_\ell/2)^4 r ℓ = ( 1 − u ℓ /2 ) 4 and b ℓ = ( u ℓ / 2 ) 2 b_\ell=(u_\ell/2)^2 b ℓ = ( u ℓ /2 ) 2 . If u 0 / [ 2 ( 1 − χ ) ] < 1 u_0/[2(1-\chi)]<1 u 0 / [ 2 ( 1 − χ )] < 1 and 9 u 0 2 / 4 < 1 9u_0^2/4<1 9 u 0 2 /4 < 1 , then
inf j ≥ 1 r ⋆ ( j ) ≥ ( 1 − u 0 2 ( 1 − χ ) ) 4 > 0 , \inf_{j\ge1}r_\star(j)\ge\left(1-\frac{u_0}{2(1-\chi)}\right)^4>0, j ≥ 1 inf r ⋆ ( j ) ≥ ( 1 − 2 ( 1 − χ ) u 0 ) 4 > 0 ,
∑ j ≥ 1 Λ j ≤ u 0 2 / 4 1 − 9 u 0 2 / 4 . \sum_{j\ge1}\Lambda_j\le\frac{u_0^2/4}{1-9u_0^2/4}. j ≥ 1 ∑ Λ j ≤ 1 − 9 u 0 2 /4 u 0 2 /4 .
The first bound follows from ∏ ( 1 − x ℓ ) ≥ 1 − ∑ x ℓ \prod(1-x_\ell)\ge1-\sum x_\ell ∏ ( 1 − x ℓ ) ≥ 1 − ∑ x ℓ . For the second, bound every b ℓ b_\ell b ℓ by u 0 2 / 4 u_0^2/4 u 0 2 /4 and sum the geometric series. Thus total leakage can be made arbitrarily small while retention stays positive. Moreover d ℓ = O ( ℓ + 1 ) d_\ell=O(\ell+1) d ℓ = O ( ℓ + 1 ) . This proves feasibility of the symbolic assumptions in Corollary 5.4 for every fixed admissible margin triple.
Implementation precision
The results above assume exact known gates. We now estimate the change in the output when these gates are replaced by unitary approximations.
Proposition B.2. Suppose a finite adaptive quantum computation uses at most M M M known unitary gates on each execution. Let V t , h V_{t,h} V t , h be the gate at location t t t after classical history h h h , and suppose that its approximation satisfies
∥ V ~ t , h − V t , h ∥ ≤ ϵ t \lVert\widetilde{V}_{t,h}-V_{t,h}\rVert\le\epsilon_t ∥ V t , h − V t , h ∥ ≤ ϵ t for every possible h h h . Let ρ o u t \rho_{\mathrm{out}} ρ out be the output density matrix of the original computation and ρ ~ o u t \widetilde{\rho}_{\mathrm{out}} ρ out that of the same computation with the known gates replaced by their approximations.
Both density matrices include the quantum registers and the recorded classical outcomes. Then
D ( ρ ~ o u t , ρ o u t ) : = 1 2 ∥ ρ ~ o u t − ρ o u t ∥ 1 ≤ ∑ t = 1 M ϵ t . D(\widetilde{\rho}_{\mathrm{out}},\rho_{\mathrm{out}}) := \frac{1}{2}\lVert\widetilde{\rho}_{\mathrm{out}}-\rho_{\mathrm{out}}\rVert_1 \le\sum_{t=1}^{M}\epsilon_t. D ( ρ out , ρ out ) := 2 1 ∥ ρ out − ρ out ∥ 1 ≤ t = 1 ∑ M ϵ t .
The same bound holds for the change in probability of any measurement outcome on these outputs.
Proof. For any density matrix ρ \rho ρ , the triangle inequality gives
1 2 ∥ V ~ ρ V ~ † − V ρ V † ∥ 1 ≤ ∥ V ~ − V ∥ . \frac{1}{2}\lVert\widetilde{V}\rho\widetilde{V}^{\dagger}-V\rho V^{\dagger}\rVert_1 \le\lVert\widetilde{V}-V\rVert. 2 1 ∥ V ρ V † − V ρ V † ∥ 1 ≤ ∥ V − V ∥ .
By keeping the measurement outcomes in a classical register, the gate at location t t t can be written as a direct sum over the histories h h h . The operator norm of the difference between the two direct sums is max h ∥ V ~ t , h − V t , h ∥ ≤ ϵ t \max_h\lVert\widetilde{V}_{t,h}-V_{t,h}\rVert\le\epsilon_t max h ∥ V t , h − V t , h ∥ ≤ ϵ t .
By adding identity gates after termination, it can be assumed that every execution contains M M M known gates. Let ρ ( t ) \rho^{(t)} ρ ( t ) denote the final density matrix obtained by approximating the first t t t known gates and keeping the remaining gates exact. Since the computations that define ρ ( t − 1 ) \rho^{(t-1)} ρ ( t − 1 ) and ρ ( t ) \rho^{(t)} ρ ( t ) differ only at location t t t , their states right before this gate are equal. The inequality above therefore gives a trace distance of at most ϵ t \epsilon_t ϵ t after the gate. Since the subsequent operations cannot increase trace distance, it follows that
D ( ρ ( t ) , ρ ( t − 1 ) ) ≤ ϵ t . D(\rho^{(t)},\rho^{(t-1)})\le\epsilon_t. D ( ρ ( t ) , ρ ( t − 1 ) ) ≤ ϵ t .
Using ρ ( 0 ) = ρ o u t \rho^{(0)}=\rho_{\mathrm{out}} ρ ( 0 ) = ρ out and ρ ( M ) = ρ ~ o u t \rho^{(M)}=\widetilde{\rho}_{\mathrm{out}} ρ ( M ) = ρ out , we obtain
D ( ρ ~ o u t , ρ o u t ) ≤ ∑ t = 1 M D ( ρ ( t ) , ρ ( t − 1 ) ) ≤ ∑ t = 1 M ϵ t . D(\widetilde{\rho}_{\mathrm{out}},\rho_{\mathrm{out}})\le\sum_{t=1}^{M}D(\rho^{(t)},\rho^{(t-1)})\le\sum_{t=1}^{M}\epsilon_t. D ( ρ out , ρ out ) ≤ t = 1 ∑ M D ( ρ ( t ) , ρ ( t − 1 ) ) ≤ t = 1 ∑ M ϵ t .
Applying a measurement to the final outputs gives the corresponding probability bound.
To account for these errors, fix 0 < ω g a t e < 1 0<\omega_{\mathrm{gate}}<1 0 < ω gate < 1 and apply Theorem 2.2 with failure allowance ( 1 − ω g a t e ) δ (1-\omega_{\mathrm{gate}})\delta ( 1 − ω gate ) δ . If each known gate is approximated such that the operator-norm error is at most ω g a t e δ / M \omega_{\mathrm{gate}}\delta/M ω gate δ / M , the probability of failure increases by at most ω g a t e δ \omega_{\mathrm{gate}}\delta ω gate δ and is therefore at most δ \delta δ . For fixed ω g a t e \omega_{\mathrm{gate}} ω gate , replacing δ \delta δ by ( 1 − ω g a t e ) δ (1-\omega_{\mathrm{gate}})\delta ( 1 − ω gate ) δ adds a constant to log ( 2 / δ ) \log(2/\delta) log ( 2/ δ ) , so the asymptotic query bounds are unchanged. The number of gates depends on the choice of synthesis method.
Lower bound for expectation selection
We prove the Ω ( N / η ) \Omega(\sqrt{N}/\eta) Ω ( N / η ) lower bound [16 ] in the oracle model of Corollary 6.2 by an adversary argument [26 , 27 ] .
Lower bound for Corollary 6.2. Suppose first that 0 < η ≤ 1 / 8 0<\eta\le1/8 0 < η ≤ 1/8 . For each j ∈ [ N ] j\in[N] j ∈ [ N ] , define
W j = ∑ i = 1 N ∣ i ⟩ ⟨ i ∣ ⊗ R θ 1 1 { i = j } , R θ = ( cos θ − sin θ sin θ cos θ ) . W_j=\sum_{i=1}^{N}|i\rangle\langle i|\otimes R_{\theta_1\mathbf{1}_{\{i=j\}}},\qquad
R_{\theta}=\begin{pmatrix}\cos\theta&-\sin\theta\\ \sin\theta&\cos\theta\end{pmatrix}. W j = i = 1 ∑ N ∣ i ⟩ ⟨ i ∣ ⊗ R θ 1 1 { i = j } , R θ = ( cos θ sin θ − sin θ cos θ ) .
where θ 0 = π / 4 \theta_0=\pi/4 θ 0 = π /4 and θ 1 = arcsin 1 / 2 − 2 η \theta_1=\arcsin\sqrt{1/2-2\eta} θ 1 = arcsin 1/2 − 2 η . With success projector ∣ 1 ⟩ ⟨ 1 ∣ |1\rangle\langle1| ∣1 ⟩ ⟨ 1∣ , the objective value is 1 / 2 − 2 η 1/2-2\eta 1/2 − 2 η at label j j j and 1 / 2 1/2 1/2 at every other label. Since the difference is 2 η 2\eta 2 η , an η \eta η -optimal output must be j j j .
Let s η = ∥ I − R θ 1 † R θ 0 ∥ s_{\eta}=\lVert I-R_{\theta_1}^{\dagger}R_{\theta_0}\rVert s η = ∥ I − R θ 1 † R θ 0 ∥ . The derivative of arcsin x \arcsin\sqrt{x} arcsin x is at most 2 / 3 2/\sqrt{3} 2/ 3 on [ 1 / 4 , 1 / 2 ] [1/4,1/2] [ 1/4 , 1/2 ] , and therefore
s η = 2 sin ( ( θ 0 − θ 1 ) / 2 ) ≤ θ 0 − θ 1 ≤ 4 η 3 . s_{\eta}=2\sin\left((\theta_0-\theta_1)/2\right)\leq\theta_0-\theta_1\leq\frac{4\eta}{\sqrt{3}}. s η = 2 sin ( ( θ 0 − θ 1 ) /2 ) ≤ θ 0 − θ 1 ≤ 3 4 η .
We prove the lower bound with access to
O j = ∑ σ ∈ { − 1 , 0 , 1 } ∣ σ ⟩ ⟨ σ ∣ ⊗ W j σ . O_j=\sum_{\sigma\in\{-1,0,1\}}|\sigma\rangle\langle\sigma|\otimes W_j^\sigma. O j = σ ∈ { − 1 , 0 , 1 } ∑ ∣ σ ⟩ ⟨ σ ∣ ⊗ W j σ .
The choices σ = 1 , − 1 , 0 \sigma=1,-1,0 σ = 1 , − 1 , 0 give a forward query, an inverse query, and the identity, respectively. Let T T T be the maximum number of queries made by the algorithm. By postponing measurements until the end and completing shorter branches with identity queries (σ = 0 \sigma=0 σ = 0 ), the state of all registers is pure after each of the T T T queries.
Write ∣ ψ j t ⟩ |\psi_j^t\rangle ∣ ψ j t ⟩ for the state after t t t queries on instance j j j , and let Γ \Gamma Γ be the adjacency matrix of the complete graph on [ N ] [N] [ N ] . Define
∣ Φ t ⟩ = N − 1 / 2 ∑ j ∣ j ⟩ ∣ ψ j t ⟩ , F t = ⟨ Φ t ∣ ( Γ ⊗ I ) ∣ Φ t ⟩ . |\Phi_t\rangle=N^{-1/2}\sum_j|j\rangle|\psi_j^t\rangle,\qquad F_t=\langle\Phi_t|(\Gamma\otimes I)|\Phi_t\rangle. ∣ Φ t ⟩ = N − 1/2 j ∑ ∣ j ⟩ ∣ ψ j t ⟩ , F t = ⟨ Φ t ∣ ( Γ ⊗ I ) ∣ Φ t ⟩ .
The initial state is independent of j j j , so F 0 = N − 1 F_0=N-1 F 0 = N − 1 . For j ′ ≠ j j'\ne j j ′ = j , the algorithm returns j j j with probability at least 2 / 3 2/3 2/3 on instance j j j and at most 1 / 3 1/3 1/3 on instance j ′ j' j ′ . The trace distance between the final states is therefore at least 1 / 3 1/3 1/3 . Since these states are pure,
∣ ⟨ ψ j T ∣ ψ j ′ T ⟩ ∣ ≤ 2 2 3 , ∣ F T ∣ ≤ 2 2 3 ( N − 1 ) . \left|\langle\psi_j^T|\psi_{j'}^T\rangle\right|\leq\frac{2\sqrt{2}}{3},\qquad|F_T|\leq\frac{2\sqrt{2}}{3}(N-1). ⟨ ψ j T ∣ ψ j ′ T ⟩ ≤ 3 2 2 , ∣ F T ∣ ≤ 3 2 2 ( N − 1 ) .
To bound the change caused by a query, write
Q = ∑ j ∣ j ⟩ ⟨ j ∣ ⊗ O j , D = ( Γ ⊗ I ) − Q † ( Γ ⊗ I ) Q . Q=\sum_j|j\rangle\langle j|\otimes O_j,\qquad D=(\Gamma\otimes I)-Q^\dagger(\Gamma\otimes I)Q. Q = j ∑ ∣ j ⟩ ⟨ j ∣ ⊗ O j , D = ( Γ ⊗ I ) − Q † ( Γ ⊗ I ) Q .
The change in F t F_t F t is at most ∥ D ∥ \lVert D\rVert ∥ D ∥ . For a forward query to label i i i , the work qubit is rotated by R θ 1 R_{\theta_1} R θ 1 when j = i j=i j = i and by R θ 0 R_{\theta_0} R θ 0 otherwise. Ordering the instance indices with i i i first gives the corresponding block of D D D as
( 0 1 T ⊗ C 1 ⊗ C † 0 ) , C = I − R θ 1 † R θ 0 , \begin{pmatrix}
0 & \mathbf{1}^{\mathsf T}\otimes C\\
\mathbf{1}\otimes C^{\dagger} & 0
\end{pmatrix},\qquad C=I-R_{\theta_1}^{\dagger}R_{\theta_0}, ( 0 1 ⊗ C † 1 T ⊗ C 0 ) , C = I − R θ 1 † R θ 0 ,
where 1 ∈ R N − 1 \mathbf{1}\in\mathbb{R}^{N-1} 1 ∈ R N − 1 is the all-ones column vector. This block has norm s η N − 1 s_{\eta}\sqrt{N-1} s η N − 1 . Replacing C C C by C † C^{\dagger} C † gives the block for an inverse query. For σ = 0 \sigma=0 σ = 0 , the query is the identity, so the corresponding block of D D D is zero. Since D D D is a direct sum over the queried labels and the choices of σ \sigma σ , it follows that
∥ D ∥ = s η N − 1 . \lVert D\rVert=s_{\eta}\sqrt{N-1}. ∥ D ∥ = s η N − 1 .
Operations independent of j j j preserve F t F_t F t . Summing the changes over the T T T queries therefore gives
( 1 − 2 2 3 ) ( N − 1 ) ≤ ∣ F 0 − F T ∣ ≤ T s η N − 1 . \left(1-\frac{2\sqrt{2}}{3}\right)(N-1)\leq|F_0-F_T|\leq T s_{\eta}\sqrt{N-1}. ( 1 − 3 2 2 ) ( N − 1 ) ≤ ∣ F 0 − F T ∣ ≤ T s η N − 1 .
Using s η ≤ 4 η / 3 s_{\eta}\leq4\eta/\sqrt{3} s η ≤ 4 η / 3 , we obtain T = Ω ( N / η ) T=\Omega(\sqrt{N}/\eta) T = Ω ( N / η ) .
For 1 / 8 < η < 1 1/8<\eta<1 1/8 < η < 1 , take the exact Boolean value oracle with f ( j ) = 0 f(j)=0 f ( j ) = 0 and f ( i ) = 1 f(i)=1 f ( i ) = 1 for i ≠ j i\ne j i = j . An η \eta η -optimal output must again be j j j . Each query, including a controlled or inverse query, can be implemented with a constant number of Boolean search queries. The search lower bound [2 ] consequently gives
T = Ω ( N ) = Ω ( N / η ) , T=\Omega(\sqrt{N})=\Omega(\sqrt{N}/\eta), T = Ω ( N ) = Ω ( N / η ) ,
which completes the proof.
Concrete constants and comparisons
This appendix gives concrete constants for the parameters in the proposed algorithm, and compares it with a classical procedure based on medians and with the Chen–de Wolf construction in terms of query bounds. The parameters of each procedure are chosen so that the returned label s s s and score v v v satisfy
∣ v − f ( s ) ∣ ≤ ε , v ≤ min i f ( i ) + ε \lvert v-f(s)\rvert\le\varepsilon,\qquad v \le\min_i f(i)+\varepsilon ∣ v − f ( s )∣ ≤ ε , v ≤ i min f ( i ) + ε
with probability at least 15/16.
Parameter choices
In the analysis we consider the following exact rational constants:
( γ , α , β ) = ( 17 50 , 7 20 , 9 20 ) , ( ρ , h , m ) = ( 7 10 , 1 16 , 1 18 ) , (\gamma,\alpha,\beta)=\left(\frac{17}{50},\frac{7}{20},\frac{9}{20}\right),\qquad
(\rho,h,m)=\left(\frac{7}{10},\frac{1}{16},\frac{1}{18}\right), ( γ , α , β ) = ( 50 17 , 20 7 , 20 9 ) , ( ρ , h , m ) = ( 10 7 , 16 1 , 18 1 ) ,
( ϑ , θ ) = ( 1 2 , 9 26 ) , ( r ∗ , Λ ) = ( 14 25 , 1 200 ) , (\vartheta,\theta)=\left(\frac{1}{2},\frac{9}{26}\right),\qquad
(r_\ast,\Lambda)=\left(\frac{14}{25},\frac{1}{200}\right), ( ϑ , θ ) = ( 2 1 , 26 9 ) , ( r ∗ , Λ ) = ( 25 14 , 200 1 ) ,
( v a c c , ε c a p , ε v a l , σ ) = ( 63 64 , 3 64 , 1 64 , 1 16 ) . (51) (v_{\mathrm{acc}},\varepsilon_{\mathrm{cap}},\varepsilon_{\mathrm{val}},\sigma)
=\left(\frac{63}{64},\frac{3}{64},\frac{1}{64},\frac{1}{16}\right). \tag*{(51)} ( v acc , ε cap , ε val , σ ) = ( 64 63 , 64 3 , 64 1 , 16 1 ) . (51)
These margins ( γ , α , β ) = ( 0.34 , 0.35 , 0.45 ) (\gamma,\alpha,\beta)=(0.34,0.35,0.45) ( γ , α , β ) = ( 0.34 , 0.35 , 0.45 ) satisfy (9) and give the signal gap g = ( β − α ) / ( 2 − α − β ) = 1 / 12 g=(\beta-\alpha)/(2-\alpha-\beta)=1/12 g = ( β − α ) / ( 2 − α − β ) = 1/12 .
Use the polynomial family in Appendix § 11 .§ 1 with
n ℓ = 25 , r ℓ = 1 + ⌊ ℓ / 2 ⌋ , d ℓ = 48 r ℓ + 1. (52) n_\ell=25,\qquad r_\ell=1+\lfloor\ell/2\rfloor,\qquad d_\ell=48r_\ell+1. \tag*{(52)} n ℓ = 25 , r ℓ = 1 + ⌊ ℓ /2 ⌋ , d ℓ = 48 r ℓ + 1. (52)
A convenient error certificate is E 25 , r ( 1 / 12 ) ≤ u ( r ) E_{25,r}(1/12)\le u(r) E 25 , r ( 1/12 ) ≤ u ( r ) , where
u ( 1 ) = 1 8 , u ( r ) = 1 100 3 − ( r − 2 ) ( r ≥ 2 ) . (53) u(1)=\frac{1}{8},\qquad u(r)=\frac{1}{100}3^{-(r-2)}\quad(r\ge2). \tag*{(53)} u ( 1 ) = 8 1 , u ( r ) = 100 1 3 − ( r − 2 ) ( r ≥ 2 ) . (53)
Exact polynomial integration verifies 1 ≤ r ≤ 10 1\le r\le10 1 ≤ r ≤ 10 . For r ≥ 11 r\ge11 r ≥ 11 , Lemma B.1 gives E 25 , r ( 1 / 12 ) ≤ ( 35 / 16 ) ( 25 / 12 ) − ( 2 r − 1 ) ≤ u ( r ) E_{25,r}(1/12)\le(35/16)(25/12)^{-(2r-1)}\le u(r) E 25 , r ( 1/12 ) ≤ ( 35/16 ) ( 25/12 ) − ( 2 r − 1 ) ≤ u ( r ) : the second inequality holds at r = 11 r=11 r = 11 and is preserved because ( 12 / 25 ) 2 < 1 / 3 (12/25)^2<1/3 ( 12/25 ) 2 < 1/3 . Taking r ℓ = ( 1 − u ( r ℓ ) / 2 ) 4 r_\ell=(1-u(r_\ell)/2)^4 r ℓ = ( 1 − u ( r ℓ ) /2 ) 4 and b ℓ = ( u ( r ℓ ) / 2 ) 2 b_\ell=(u(r_\ell)/2)^2 b ℓ = ( u ( r ℓ ) /2 ) 2 therefore yields
∏ ℓ ≥ 0 r ℓ ≥ ( 15 16 ) 8 ( 197 200 ) 4 > 14 25 , ∑ j ≥ 1 Λ j ≤ 1 247 < 1 200 . (54) \prod_{\ell\ge0}r_\ell\ge\left(\frac{15}{16}\right)^8\left(\frac{197}{200}\right)^4>\frac{14}{25},\qquad
\sum_{j\ge1}\Lambda_j\le\frac{1}{247}<\frac{1}{200}. \tag*{(54)} ℓ ≥ 0 ∏ r ℓ ≥ ( 16 15 ) 8 ( 200 197 ) 4 > 25 14 , j ≥ 1 ∑ Λ j ≤ 247 1 < 200 1 . (54)
Since r 0 = r 1 = 1 r_0=r_1=1 r 0 = r 1 = 1 , we separate the first two factors in the retention product and apply ∏ ( 1 − x ℓ ) ≥ 1 − ∑ x ℓ \prod(1-x_\ell)\ge1-\sum x_\ell ∏ ( 1 − x ℓ ) ≥ 1 − ∑ x ℓ to the remaining factors before taking the fourth power. The bound b ℓ ≤ 1 / 256 b_\ell\le1/256 b ℓ ≤ 1/256 gives Λ j ≤ 256 − 1 ( 9 / 256 ) j − 1 \Lambda_j\le256^{-1}(9/256)^{j-1} Λ j ≤ 25 6 − 1 ( 9/256 ) j − 1 , from which the leakage estimate follows by summing over j j j . Moreover,
m = 1 18 < 7 125 = r ∗ ( 1 − 2 β ) , h 1 − ρ + Λ = 16 75 < 3 4 , m=\frac{1}{18}<\frac{7}{125}=r_\ast(1-2\beta),\qquad
\frac{h}{1-\rho}+\Lambda=\frac{16}{75}<\frac{3}{4}, m = 18 1 < 125 7 = r ∗ ( 1 − 2 β ) , 1 − ρ h + Λ = 75 16 < 4 3 ,
so the selection conditions are satisfied.
Selection schedule
For any given N N N , use the fixed parameters above and the geometric schedule in § 5.3 with p = 1 / N p = 1/N p = 1/ N and L d = log ( 1 / δ d ) L_d = \log(1/\delta_d) L d = log ( 1/ δ d ) . In particular,
K = 1 + ⌈ log 9 9 N 8 ⌉ , δ d = 3 64 2 d , t j = ⌈ log ( 1 / δ d ) η d ⌉ , d = K − j + 1 , (55) K = 1 + \left\lceil\log_{9} \frac{9N}{8} \right\rceil,\qquad\delta_d = \frac{3}{64\,2^d},\qquad t_j = \left\lceil\frac{\log(1/\delta_d)}{\eta_d} \right\rceil,\qquad d = K-j+1, \tag*{(55)} K = 1 + ⌈ log 9 8 9 N ⌉ , δ d = 64 2 d 3 , t j = ⌈ η d log ( 1/ δ d ) ⌉ , d = K − j + 1 , (55)
where η d \eta_d η d is given by (40) . Let T = ∑ j t j T = \sum_j t_j T = ∑ j t j and write D ( x ∥ y ) = x log ( x / y ) + ( 1 − x ) log ( ( 1 − x ) / ( 1 − y ) ) D(x\mathbin{\|}y) = x\log(x/y) + (1-x)\log((1-x)/(1-y)) D ( x ∥ y ) = x log ( x / y ) + ( 1 − x ) log (( 1 − x ) / ( 1 − y )) . Use the validation procedure of Lemma 3.3 with
n v a l = ⌈ max { log ( 64 T ) D ( θ ∥ γ ) , log 128 D ( θ ∥ } α ) } ⌉ , k v a l = ⌈ θ n v a l ⌉ . (56) n_{\mathrm{val}} = \left\lceil\max\left\{ \frac{\log(64T)}{D(\theta\mathbin{\|}\gamma)}, \frac{\log128}{D(\theta\mathbin{\|}\}\alpha)} \right\} \right\rceil,\qquad k_{\mathrm{val}} = \lceil\theta n_{\mathrm{val}}\rceil. \tag*{(56)} n val = ⌈ max { D ( θ ∥ γ ) log ( 64 T ) , D ( θ ∥ } α ) log 128 } ⌉ , k val = ⌈ θ n val ⌉ . (56)
Chernoff bounds give soundness at most 1 / ( 64 T ) 1/(64T) 1/ ( 64 T ) and completeness at least 63 / 64 63/64 63/64 . The total number of estimator queries, including validation, is bounded by
Q A = ∑ j = 1 K t j q j A + n v a l T , Q_A = \sum_{j=1}^{K} t_j q_j^A + n_{\mathrm{val}}T, Q A = j = 1 ∑ K t j q j A + n val T ,
where q j A q_j^A q j A is given in (27) . By Corollary 5.4, this gives Q A = O ( N ) Q_A = O(\sqrt{N}) Q A = O ( N ) for the chosen parameters.
For concrete choices outside this fixed-confidence comparison, one may use
( ω b a d , ω n o n e , ω r e j ) = ( 1 / 2 , 1 / 4 , 1 / 4 ) (\omega_{\mathrm{bad}},\omega_{\mathrm{none}},\omega_{\mathrm{rej}}) = (1/2,1/4,1/4) ( ω bad , ω none , ω rej ) = ( 1/2 , 1/4 , 1/4 )
in § 5.4 , c g a p = 1 / 4 c_{\mathrm{gap}} = 1/4 c gap = 1/4 and σ E = 1 / 8 \sigma_E = 1/8 σ E = 1/8 in § 6 , and ω g a t e = 1 / 2 \omega_{\mathrm{gate}} = 1/2 ω gate = 1/2 in Appendix § 11 .§ 3 .
Comparison with baseline algorithms
A natural classical comparison approach is based on computing the median of repeated estimates for each label. For each label i i i , let v i v_i v i be the median of k k k independent base-estimator outputs, where k k k is odd. The procedure returns a label s s s with v s = min i v i v_s = \min_i v_i v s = min i v i , together with the score v = v s v = v_s v = v s .
If ∣ v i − f ( i ) ∣ > ε |v_i-f(i)|>\varepsilon ∣ v i − f ( i ) ∣ > ε , at least ( k + 1 ) / 2 (k+1)/2 ( k + 1 ) /2 of the estimates used to form v i v_i v i must be inaccurate. Since each estimate is inaccurate with probability at most 1 / 3 1/3 1/3 , it follows that Pr { ∣ v i − f ( i ) ∣ > ε } ≤ b k \Pr\{|v_i-f(i)|>\varepsilon\}\leq b_k Pr { ∣ v i − f ( i ) ∣ > ε } ≤ b k , where
b k = 3 − k ∑ r = ( k + 1 ) / 2 k ( k r ) 2 k − r . (57) b_k = 3^{-k}\sum_{r=(k+1)/2}^{k}\binom{k}{r}2^{k-r}. \tag*{(57)} b k = 3 − k r = ( k + 1 ) /2 ∑ k ( r k ) 2 k − r . (57)
Choose the smallest odd k k k satisfying b k ≤ 1 / ( 16 N ) b_k \leq1/(16N) b k ≤ 1/ ( 16 N ) , and let i ∗ i_* i ∗ be a label minimizing f f f . By the union bound, with probability at least 1 − N b k ≥ 15 / 16 1-Nb_k \geq15/16 1 − N b k ≥ 15/16 , all medians are accurate and therefore
∣ v − f ( s ) ∣ ≤ ε , v = v s ≤ v i ∗ ≤ f ( i ∗ ) + ε . |v-f(s)|\leq\varepsilon,\qquad v=v_s\leq v_{i_*}\leq f(i_*)+\varepsilon. ∣ v − f ( s ) ∣ ≤ ε , v = v s ≤ v i ∗ ≤ f ( i ∗ ) + ε .
The procedure uses N k Nk N k base-estimator queries.
Chen and de Wolf [7 arXiv v2, Theorem 2.4 and Appendix A] give a bound of M = 1000 N log 2 ( 1 / δ 1 ) M=1000\sqrt{N}\log_2(1/\delta_1) M = 1000 N log 2 ( 1/ δ 1 ) invocations of the amplified estimator and failure at most δ 1 + M 2 b \delta_1+M\sqrt{2}b δ 1 + M 2 b when the amplified estimator has error at most b b b per label. The logarithm is base two. We use their published prefactor and the simple choice δ 1 = 1 / 32 \delta_1=1/32 δ 1 = 1/32 , giving M = 5000 N M=5000\sqrt{N} M = 5000 N . Take the smallest odd
k ≥ 2 log ( 51200000000 N ) log ( 9 / 8 ) . (58) k \geq\frac{2\log(51200000000N)}{\log(9/8)}. \tag*{(58)} k ≥ log ( 9/8 ) 2 log ( 51200000000 N ) . (58)
The binomial Chernoff bound gives b k ≤ 1 / ( 51200000000 N ) b_k \le1/(51200000000N) b k ≤ 1/ ( 51200000000 N ) and total failure at most 1 / 16 1/16 1/16 . A reversible median retaining its work uses k k k base-estimator queries in either direction, so the budget is M k Mk M k . Neither these comparison parameters nor the proposed parameters in Appendix D.1 are optimized.
Substituting the parameter values above into the query bounds gives the values in Table 5 . The values are rounded up to 3 digits. The proposed algorithm gives the lowest
query bound at each problem size in the table except for N = 2 20 N = 2^{20} N = 2 20 , where the classical procedure gives the smallest bound.
For the proposed method, validation dominates the query budget for small problem sizes. Its share decreases from 84.55 % 84.55\% 84.55% at N = 2 20 N = 2^{20} N = 2 20 to 0.00002794 % 0.00002794\% 0.00002794% for N = 2 100 N = 2^{100} N = 2 100 .
Reducing the constants
The constants in the query bounds could be reduced by using the finite amplification products in (31) and sharper retention and leakage estimates at each level. The filter accuracies and trial counts could then be chosen together with the probability margins and validation parameters to minimize
∑ j t j q j A + n v a l T . \sum_j t_j q_j^{A} + n_{\mathrm{val}}T. j ∑ t j q j A + n val T .
Since the relative cost of validation varies with N N N , it would be beneficial to optimize the parameters separately for each problem size N N N . Using exact binomial tails may reduce the number of estimates needed for validation compared with the Chernoff bounds used here.
It would be interesting to search numerically for minimax polynomials that satisfy the required approximation bounds with a lower degree. These polynomials must be odd and bounded in absolute value by one on [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Another possibility is to combine the two cumulative-probability tests in Lemma 4.1 into one transformation. For the same analysis to be applicable, the resulting filter must satisfy the acceptance bounds and retain the scalar form of the initialized block and the workspace conditions of that lemma.