LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite amplification preserves the good state with a deterministic call cap

Statement

Under the inputs and promise of Finite amplification from a supplied success lower bound, that finite procedure succeeds with probability at least $1 - β$ . Conditional on success, its returned register has exactly the density operator $∣ g ⟩ ⟨ g ∣$ , where $∣ g ⟩ = P U ∣ 0 ⟩ / \sqrt{p}$ . This includes all output and workspace registers of the original conditional good state.

Its deterministic caps are $2 R M$ total calls to $U, U^{†}$ , $R (M - 1)$ zero-input reflections and $R (M + 1)$ good reflections, including the controlled good-reflection calls implementing at most two instruments per trial. It uses at most $R \log_{2} M$ unbiased random bits. Consequently its primitive-call cap is $O (p_{0}^{- 1 / 2} (1 + \ln (1 / β)))$ , or $O (p_{0}^{- 1 / 2} \ln (1 / β))$ when $β \leq 1 / 2$ . Query calls, gates, initialization, instruments, control variants and classical preprocessing are separately charged.

Facts & Assumptions

Given: The finite schedule, fresh operations, access capabilities and rational parameters of the algorithm.

[F1]

Finite amplification from a supplied success lower bound specifies $M, R$ , direct attempts, independent uniform indices and the explicit failure branch.

[F2]

Amplitude-amplification invariant plane and Exact success probability after amplitude amplification give the invariant-plane rotation and success probability $\sin^{2} ((2 j + 1) θ)$ when $p = \sin^{2} θ$ .

[F3]

Projective measurement outcome weights are probabilities, Conditional state for a projective measurement and A unit-vector outer product is a density operator give the outcome probabilities and normalized density operator on positive-probability branches.

[F4]

The addition formulas for sine and cosine, Double-angle and quadratic power-reduction identities and Parity and the Pythagorean identity for sine and cosine give sine addition, $\sin^{2} x = (1 - \cos (2 x)) / 2$ and $∣ \sin x ∣ \leq 1$ .

[F5]

Amplitude-amplification access and resource accounting, Controlled Unitary Access and Circuit-family and computation cost model separately charge the four factors of an iterate, control variants and gate/classical work.

[F6]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t gives the increasing natural logarithm on positive reals and its integral formula.

Proof

1.1givenF2F3algebra

For $0 < p < 1$ , write $U ∣ 0 ⟩ = \cos θ ∣ h ⟩ + \sin θ ∣ g ⟩$ , where $0 < θ < π / 2$ . By [F2], $Q^{j} U ∣ 0 ⟩ = \cos ((2 j + 1) θ) ∣ h ⟩ + \sin ((2 j + 1) θ) ∣ g ⟩$ . On every positive-probability good branch its projection is a scalar multiple of $∣ g ⟩$ , so [F3] gives exactly $∣ g ⟩ ⟨ g ∣$ . Direct attempts give the same conditional state. If $p = 1$ , every direct attempt succeeds and returns this state; no zero-probability component is normalized.

1.2givenF2F4algebra

For $0 < p < 1$ , sine addition in [F4] gives $\sin ((4 j + 4) θ) - \sin (4 j θ) = 2 \cos ((4 j + 2) θ) \sin (2 θ)$ . Summing over $j = 0, \dots, M - 1$ and using $\sin (2 θ) > 0$ gives $\sum_{j} \cos ((4 j + 2) θ) = \sin (4 M θ) / (2 \sin (2 θ))$ . Thus the mean success probability of the uniform-index attempt is $a_{M} = 1 / 2 - \sin (4 M θ) / (4 M \sin (2 θ)) \geq 1 / 2 - 1 / (4 M \sin (2 θ)) \geq 1 / 2 - 1 / (2 M \sin (2 θ))$ .

1.3givenF1F3F5algebra

A trial has at most two preparations and $M - 1$ iterates. By [F5], it uses at most $M + 1$ forward calls, $M - 1$ inverse calls, $M - 1$ zero reflections and $M - 1$ iterate good reflections. Each of at most two instruments adds one controlled good reflection: on a vector $v$ , the control construction has joint state $∣ 0 ⟩ \otimes (I - P) v + ∣ 1 ⟩ \otimes P v$ immediately before measurement, which is exactly the required instrument. Thus the displayed per-trial caps hold, and only the second attempt draws $\log_{2} M$ random bits.

2.1givenF1F4step 1.2algebra

If $0 < p < 3 / 4$ , then $\sin (2 θ) = 2 \sqrt{p (1 - p)} \geq \sqrt{p} \geq \sqrt{p_{0}}$ . Since $M \geq 2 / \sqrt{p_{0}}$ , step 1.2 implies $a_{M} \geq 1 / 4$ . The whole trial succeeds with probability $p + (1 - p) a_{M} \geq a_{M} \geq 1 / 4$ . For $3 / 4 \leq p \leq 1$ the direct attempt succeeds with probability at least $3 / 4$ . Hence every promised input has trial success probability at least $1 / 4$ .

3.1givenF1F3step 1.1step 2.1inductionalgebra

Conditional on any preceding failures, freshness leaves the next trial's success probability at least $1 / 4$ . Finite induction bounds total failure by $(3 / 4)^{R} \leq β$ . Every successful branch returns the state of step 1.1; summing its scalar branch weights and dividing by total success probability therefore gives the same density operator, even after forgetting the index, stopping trial and earlier failure outcomes.

4.1givenF1F6step 1.3algebra∎

Minimality of the power of two $M$ gives $2 / \sqrt{p_{0}} \leq M < 4 / \sqrt{p_{0}}$ . Also $R \leq 1 + \ln (1 / β) / \ln (4 / 3)$ , by applying [F6] to $(3 / 4)^{R} \leq β$ and the minimal positive integer choice. Multiplying the finite per-trial counts by $R$ proves the call and randomness caps and their asymptotic bounds.

Remarks

For gate costs $C_{U}, C_{i n v}, C_{0}, C_{g}$ of the supplied implementations, with $C_{g}$ covering both used good-reflection control variants and instrument ancilla overhead charged explicitly, the quantum gate cap is $R ((M + 1) C_{U} + (M - 1) C_{i n v} + (M - 1) C_{0} + (M + 1) C_{g} + O (\log M))$ . Register initialization is included in its actual supplied preparation cost. Binary counters and comparisons admit $O (R M \log M)$ elementary classical bit operations; exact arithmetic constructing $M, R$ is separate finite preprocessing. A padded coherent circuit implementation must use and charge the supplied controlled operations. The logarithmic bound retains an additive $1$ for $β$ arbitrarily close to $1$ .

Depends on

Used by

Finite CKS sparse QLSP with variable-time inverse estimation Algorithm
CKS nearly-linear condition-number guarantee Theorem
Variable-time amplitude-amplification theorem Theorem

Dependency tree · two levels

66 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum Amplitude Amplification and Estimation (standard reference, not scraped)
Andris Ambainis, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations (standard reference, not scraped)