Polynomial Signals
Exercise PLAN-515
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
- M at least one and known in advance; marked set has M elements among N
- Good/bad states are the normalized marked/unmarked superpositions
- sine of the half-angle equals sqrt(M/N)
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 assumptions: M>=1 marked states among N basis states, M known in advance, so the allowed domain includes M=N. Let Π_mark project onto the marked basis states, psi be uniform, and G=(2|psi><psi|-I)(I-2Π_mark). Assess the predecessor's universal construction of normalized good and bad superpositions, its phrase that the angle from the bad state has the stated half-angle, and its uniform 'optimal iteration count/near-one' conclusion. Do not silently assume M<N. For 1<=M<N construct g,b, define phi=arcsin(sqrt(M/N)), identify the actual angle from b to psi and the full iteration angle2phi, and prove success after integer k is sin^2((2k+1)phi). For M/N<=1/2 choose a nonnegative integer nearest to pi/(4phi)-1/2 and prove a quantitative success bound from its rounding error; for M/N>1/2 examine k=0. State exactly which Theta(sqrt(N/M)) assertion holds as M/N tends to zero, rather than claiming a positive iteration optimum uniformly or a global maximum over all integers. Treat M=N separately without defining a bad vector. Explain why M calibrates this direct stopping rule, while not being logically necessary for every possible search method. Count only Grover marking-reflection calls here; no unproved finite-bit/gate or verification cost is free.
Hint: mathematical route
Interior multi-marked Grover dynamics has angle2arcsin(sqrt(M/N)); nearest-first-peak rounding gives bounded success, sparse fractions yield the usual iteration asymptotic, and the all-marked case needs zero iterations and has no bad vector.
- For M<N define normalized g,b and decompose psi; at M=N the bad vector does not exist and psi is already entirely good.
- sin(phi)=sqrt(M/N), where phi is the actual angle from b when b exists;2phi is the full iteration angle.
- The two reflection product has the exact oriented rotation matrix on the nontrivial good/bad plane, not a global rank-one marking reflection.
- The good success probability is sin^2((2k+1)phi); at M=N the exact state gains (-1)^k and probability remains1.
- Nearest-first-peak rounding gives success>=1-M/N when M/N<=1/2 and sparse-regime k=Theta(sqrt(N/M)); k=0 suffices for larger fractions.
- Known M calibrates this direct rule; unknown M can cause over/under-rotation, not a general impossibility for all search algorithms.
Reference solution
Write r=M/N. The unique domain implication is 1<=M<=N, not M<N. When M<N, g=M^(-1/2)sum_marked|x> and b=(N-M)^(-1/2)sum_unmarked|x> are normalized and orthogonal, and psi=sqrt(r)g+sqrt(1-r)b. With phi=arcsin(sqrt(r)), the angle FROM b TOWARD g of psi is phi, not an angle whose half is phi; the iteration angle is2phi. On this plane, I-2Π_mark acts as diag(-1,1), and the diffusion reflection has matrix [[2sin^2(phi)-1,2sin(phi)cos(phi)],[2sin(phi)cos(phi),2cos^2(phi)-1]]. Their product in ordered(g,b) is [[cos2phi,sin2phi],[-sin2phi,cos2phi]], so G^k psi=sin((2k+1)phi)g+cos((2k+1)phi)b and the success probability is sin^2((2k+1)phi). The marking reflection is not globally I-2|g><g| when M>1; that rank-one expression is only its restriction to the relevant plane. For 0<r<=1/2, put x=pi/(4phi)-1/2>=1/2 and choose any nearest nonnegative integer k. Then |k-x|<=1/2, hence |(2k+1)phi-pi/2|<=phi. Success is therefore at least cos^2(phi)=1-r>=1/2. This is a first-peak rounding rule, not a global optimizer over every later integer iterate. As r tends to zero, phi=sqrt(r)(1+O(r)), k=pi/(4sqrt(r))+O(1), so k=Theta(sqrt(N/M)) and the success lower bound1-r tends to one. The success probability need not approach one for an arbitrary fixed fraction: r=1/2 gives1/2 for every integer k. For r>1/2, k=0 already succeeds with probability r>1/2, so a positive Theta(sqrt(N/M)) minimal iteration count is not a uniform claim. The selected total1+k is O(sqrt(N/M)) over the whole promised domain, whereas the sparse-regime iteration asymptotic has the stated meaning. At M=N the good state equals psi, the unmarked sum is zero and cannot be normalized. G psi=-psi, so G^k psi=(-1)^k psi and success is one already at k=0; no plane or angle-from-b assertion is defined there. The formal parameter phi=pi/2 may still be used in the scalar sine-square identity, not to fabricate b. M=0 is outside the retained promise and would have no normalized good state. Known M supplies r and the calibrated stopping rule. Without that information a chosen fixed k can over- or under-rotate; this is a limitation of this direct rule, not an impossibility of unknown-M algorithms. Alternatives require separately specified schedules/information and their own proof/cost. Each Grover iteration uses one marking reflection; preparation, diffusion synthesis, verifying/repeating outputs and finite-bit gates are not made free by this algebraic count. The question revision retains/refutes the old endpoint and ambiguous count demands instead of pretending they were proved.
Assessment rubric
- Retains M=N in the promised domain, explicitly exposes the zero unmarked sum and answers that case without inventing a normalized bad state; does not silently replace assumptions by M<N. (1 weight)
- For 1<=M<N derives normalized g,b, the geometric angle phi versus iteration2phi, correct ordered matrices and all-k success; distinguishes the global marked-subspace projector from its rank-one plane restriction. (1 weight)
- Proves the nearest-first-peak rounding error at most phi and success>=1-r for r<=1/2, handles r>1/2 by k=0, and uses r=1/2 to refute a universal near-unit guarantee. (1 weight)
- States k=pi/(4sqrt(r))+O(1) only as r->0, not a uniformly positive/global optimum; explains known-M calibration versus unknown-M alternatives and keeps the oracle/resource boundary explicit. (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)
- Operator and semigroup theory (frozen curriculum anchor; see graph registry)
- Oracle and circuit complexity (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: 15b71c7d5e6643e4a7266d3ee33ef290f9c40ce59973d7e7b627723f74b4742d
Item digest: 72db6ffe698e777d01d1200224051cf4c73e89b2fcd45a09145413c4993d49f1
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-515-grover-multi-marked-iteration-count", "predecessor_item_digest": "c43f284df9948aea79762f7797a9fa54e23675d85ae9d393c3ac55281cba72c1", "predecessor_contract_hash": "fa874276dfb0cbc5379d847074a106af8d877df1dba90ef559690fd9f8494b8c", "current_contract_hash": "15b71c7d5e6643e4a7266d3ee33ef290f9c40ce59973d7e7b627723f74b4742d", "changed_contract_fields": [ "question" ], "repair_record": "shared/repairs/plan-515-marked-fraction-rounding-question-successor.json", "repair_record_digest": "fede52207a41d39dab74a357712fd6375f31a1943eaba85ae637ad0eddf44a39", "review_record": "reports/textbook-v1/repairs/plan-515-marked-fraction-rounding-question-successor-review.json", "review_digest": "9892a5b704465aed9390b643984a02434389caabcb960a255c89b39cec09d6c3", "equivalence_to_predecessor_claimed": false, "additional_core_count": 0 }