Polynomial Signals
Exercise PLAN-520
primary source nl only. Explicit question version 2 with distinct contract-change review; the predecessor question is not equivalent current gold. Core, family and split are retained. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- Initial success probability p is small and positive; the good subspace is defined by a projector
- sine of the half-angle equals sqrt(p); amplitude is the sine of the running angle
- Costs counted in state-preparation-unitary and good-subspace-reflection calls
This question explicitly revises its historical contract. A Lean companion must bind the current contract hash, not the predecessor hash. This is one reserved core, not two exercises.
Question
Keep the original assumption of a small positive initial success probability p for a state psi=U|0> and an orthogonal good projector Π, and keep the original query-level cost convention. Assess/refute the predecessor's assertion that every reflection iteration increases the good amplitude by order sqrt(p); do not replace it silently by a near-start assertion. First analyze the mathematical iterate W=R_psi R_good with R_good=I-2Π and R_psi=2|psi><psi|-I: for0<p<1 derive its signed good coefficient a_k, its exact increment, a quantitative early-angle range with positive Theta(sqrt(p)) increments, and a family of arbitrarily small p for which a later increment is negative. Compare with independent classical repetition's exact cumulative success and increments, including their saturation. Exhibit a p-dependent integer stopping rule attaining a specified constant success (for example1/4) in Theta(1/sqrt(p)) iterations as p->0, versus Theta(1/p) independent classical trials for that same target. Then AUDIT applicability rather than add promises: identify the inverse/known-zero-reflection access that supplies R_psi, and the p-information needed to select this calibrated rule; give the exact U,U-dagger,R_good and known-zero-reflection call tuple conditionally on those dependencies. Explain what forward preparation and a good-subspace reflection alone do not certify, and why the classical comparison also needs an available good-outcome check. Keep signed amplitude, norm and probability distinct; handle zero/all-good endpoints separately as outside the small-positive regime, without dividing by zero or claiming free workspace cleanup, controls, gates or finite-bit compilation.
Hint: mathematical route
Amplitude increments equal2sqrt(p) times a running cosine: they are positive Theta(sqrt(p)) only in a specified early window. A calibrated constant-success schedule has the quadratic repetition advantage only with the reversible-reflection and good-check access explicitly accounted for.
- For0<p<1 set sin(phi)=sqrt(p) and normalize the two projected components; endpoints do not admit both normalized vectors.
- The mathematical two-reflection product rotates the good/bad plane by angle2phi with the stated orientation, giving signed coefficient sin((2k+1)phi).
- The exact increment is2sqrt(p)cos((2k+2)phi), positive Theta(sqrt(p)) in an early window and negative for an explicit arbitrarily-small-p over-rotation family.
- Independent classical repetition has cumulative1-(1-p)^t and increment p(1-p)^t, so its linear-in-p regime also has a window and saturation.
- A calibrated constant-success integer schedule needs Theta(1/sqrt(p)) iterates versus Theta(1/p) independent trials; implementation conditionally costs(k+1,k,k,k) calls to U,U-dagger,R_good,S_0, with calibration/check access not presumed.
- Born's rule relates the signed rotating coefficient to squared probability; no perpetual increase, free inverse/cleanup/check or global gate/lower-bound claim is inferred.
Reference solution
The assertion of a positive order-sqrt(p) increase at every iteration is false. For0<p<1 set phi=arcsin(sqrt(p)), g=Πpsi/sqrt(p) and b=(I-Π)psi/sqrt(1-p). These are orthonormal and psi=sin(phi)g+cos(phi)b, even when the ambient Hilbert space or good subspace has larger dimension. On their plane R_good=diag(-1,1) and R_psi is the reflection about psi, so W has ordered(g,b) matrix [[cos2phi,sin2phi],[-sin2phi,cos2phi]]. Therefore W^k psi=sin((2k+1)phi)g+cos((2k+1)phi)b. The signed good coefficient is a_k=sin((2k+1)phi), its norm is |a_k| and success probability is a_k^2, not the signed sine itself. Subtracting consecutive sines gives a_(k+1)-a_k=2sin(phi)cos((2k+2)phi)=2sqrt(p)cos((2k+2)phi). In the explicit early window0<=(2k+2)phi<=pi/3 it lies between sqrt(p) and2sqrt(p). It is not positive forever: take any integer m>=1, phi=pi/(4m+2), p=sin^2(phi). Then p->0 as m->infinity, a_m=1 and a_(m+1)=cos(2phi)<1. At still later angles the signed coefficient can be negative, although probabilities remain nonnegative. For independent classical trials, C_t=1-(1-p)^t and C_(t+1)-C_t=p(1-p)^t. This is Theta(p) only on a bounded-tp window as p->0: for p<=1/2 and tp<=C, p exp(-2C)<=increment<=p, since log(1-p)>=-2p. It saturates rather than increasing linearly forever. For a concrete matched target, let beta=pi/6 and, for sufficiently small p such that phi<=pi/12, choose k=ceil((beta/phi-1)/2). It is nonnegative, and beta<=(2k+1)phi<beta+2phi<=pi/3. Hence success>=sin^2(beta)=1/4 and k=Theta(1/phi)=Theta(1/sqrt(p)). All increments used before stopping lie within the displayed early window. Within this fixed-iterate scheme any first attainment of success>=1/4 also needs (2k+1)phi>=pi/6, using |sin(alpha)|<=alpha for alpha>=0; this justifies the Theta scaling here, not a lower bound for all quantum algorithms. The least number of independent classical trials for the same target is ceil(log(3/4)/log(1-p))=Theta(1/p). Born's rule squares the rotating signed coefficient; in the early window the angle and amplitude scale linearly with k sqrt(p), while probability scales quadratically there. This coherent rotation, not perpetual amplitude growth, explains the matched quadratic comparison. Applicability is conditional. A normalized state vector defines the mathematical R_psi, but free physical access to it does not follow just from forward U. With S_0=2|0><0|-I on the FULL preparation input/workspace, the identity R_psi=U S_0 U-dagger supplies it when inverse preparation and S_0 are available. Starting from U|0>, k iterates then use exactly k+1 calls to U, k to U-dagger, k to R_good and k to S_0. The calibrated k above is a function of p; implementing that direct rule requires p or sufficient calibration information. Neither that information nor unit-cost U-dagger is included as a new standing assumption here. Unknown-p schedules would require separate analysis. Classical rejection/repetition further needs fresh preparations and an accessible measurement/check of the good event; a bare phase-reflection oracle does not by itself certify a free projective membership test. Extra inverse/control/check synthesis, gates and finite-bit precision must be charged separately. U and its inverse act on the complete specified workspace; the proof does not promise that discarded garbage is clean or an arbitrary unknown state can be reflected about for free. At p=0, the initial state is entirely bad and W leaves it fixed, so no amplification occurs; g is undefined. At p=1, it is entirely good and W^k psi=(-1)^k psi has success1 already with k=0; b is undefined. These endpoints are outside the small-positive asymptotic, not artificial normalized zero states. This answer proves the revised windowed/conditional task and explicitly does not prove the original universal-increment or access guarantee.
Assessment rubric
- Derives normalized good/bad components only for0<p<1, the exact oriented rotation and a_k=sin((2k+1)phi); distinguishes signed coefficient, absolute norm and squared success. (1 weight)
- Computes the exact increment2sqrt(p)cos((2k+2)phi), proves the explicit early-window two-sided bounds and supplies the small-p over-rotation family with a negative increment. (1 weight)
- Uses exact C_t and p(1-p)^t, their bounded-tp window and saturation; derives a concrete integer constant-success schedule and compares the SAME target with independent classical repetitions without asserting a universal quantum lower bound. (1 weight)
- Identifies inverse U, full-input S_0, calibration and the classical check as dependencies, gives exact(k+1,k,k,k) call counts conditionally, does not silently assume those dependencies, and handles p=0/1 and workspace/resource boundaries. (1 weight)
Graph-grounded prerequisites
These are support/source anchors, not an automatically extracted theorem-dependency proof.
- Approximation theory (frozen curriculum anchor; see graph registry)
- Oracle and circuit complexity (frozen curriculum anchor; see graph registry)
- Operator and semigroup theory (frozen curriculum anchor; see graph registry)
Lean view and evidence boundary
No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.
Sources and provenance
- website/research/sources.json
lin-wiebe-2026-qasc
Source SHA-256:9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae· MIT metadata only - Primary source
Contract: b2fe41619a12e1932fb1f8c78109c1582e824efb65a575099d817994cc93958c
Item digest: 5c8f37b039e0d6f59984c18a87209f00a045f7be09be249cf6bb136cc8671f20
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 6. This is not measured graph distance or model difficulty.
Question revision lineage
{ "question_version": 2, "predecessor_key": "qcb-core-plan-520-amplitude-vs-probability-quadratic", "predecessor_item_digest": "ef7c3621b6b5fad8fc6359734a3c10021e16390ab56e6b8333bbd138868ef0c2", "predecessor_contract_hash": "9fc6da7ea892a915785e7651e360083795319bc98f19859b6d758618a32c676e", "current_contract_hash": "b2fe41619a12e1932fb1f8c78109c1582e824efb65a575099d817994cc93958c", "changed_contract_fields": [ "question" ], "repair_record": "shared/repairs/plan-520-windowed-amplification-access-question-successor.json", "repair_record_digest": "ce248c860a3bf8a7e19eea10d9d6a5661f00a66ab3fa6aef196b5d4c1ea5c8fe", "review_record": "reports/textbook-v1/repairs/plan-520-windowed-amplification-access-question-successor-review.json", "review_digest": "04d2ee1957a6b6fb01b9d9e801b1edb31ee2593f2e81d4f8e8535d6468e2899a", "equivalence_to_predecessor_claimed": false, "additional_core_count": 0 }