Exercise PLAN-510

Coefficient1-norm LCU resources require an exact unit-normalized input block. A general factor-kappa input instead transforms A/kappa unless the polynomial and Chebyshev coefficients are rescaled; parity, projected output, endpoint and resource boundaries remain explicit.

1. The arbitrary-factor predecessor promise is refuted; under an exact normalized input, the parity-compatible Chebyshev expansion has the stated even/right or odd/balanced singular-value target.
2. Phase-aware coefficient preparation and SELECT/unprepare yield the fixed accepted block f^SV(A)/beta for beta>0; all-zero coefficients require a separate positive-factor zero block.
3. Padding the parity-order index requires O(log(d+1)) clean index qubits, with a0 for d0/d1 and no log(0) boundary.
4. Binary reuse of E=U†RUR yields2(K-1) queries, plus one U for odd parity, with correct left U R factor and controlled-reflection construction.
5. The queries are to U/U†; a factor-kappa input directly transforms A/kappa, and recovery of f^SV(A) requires rescaled Chebyshev coefficients/factor, not a silent input-normalization assumption.
6. Projected garbage and state-dependent success, approximation, coefficient-oracle/gate synthesis, finite-bit, input-state preparation, amplification and readout costs remain separate obligations.

The predecessor's premise is insufficient. Let A=2I_N, U=I_(2N), kappa=2 and epsilon=0. This is an exact single-ancilla block encoding since <0|U|0>=I_N=A/2. For f(x)=x, d=1 and beta=1, the promised factor1 block of f^SV(A)=2I_N would have norm2. Every compression of a unitary between isometric clean inputs/outputs has norm at most1, so that output is impossible. The problem is normalization, not the number of ancillas; approximate access additionally cannot justify an exact target without error analysis.

Now impose the stated CONDITIONAL exact normalized-input case: B=J†U J=A, so ||A||<=1 and all singular values are in[0,1]. With a full square SVD A=W Sigma V†, define f^SV(A)=V f(Sigma)V† for even f and W f(Sigma)V† for odd f. The latter is independent of a null-space singular-vector completion because an odd polynomial vanishes at0; the even target is the right transform, not generally the balanced one or the ordinary polynomial f(A). No Hermiticity of a general A is assumed here. Equal parities make the same definition linear in the Chebyshev terms that actually appear.

Let R=2JJ†-I be the known signal reflection (Z on the one signal qubit) and E=U†RUR, with rightmost operators applied first. The qubitization/CS construction gives J† E^j J = T_(2j)^SV(A), J† U R E^j J = T_(2j+1)^SV(A). These are accepted blocks, not pure full-output images. In singular coordinates each central two-by-two block is built from sigma and s=sqrt(1-sigma^2); E is a rotation by twice arccos(sigma), and U R E^j has the odd multiple. Their top entries give the displayed Chebyshev polynomials. At sigma0 and sigma1 use these same matrix/polynomial identities directly: never divide by s or demand a distinct two-dimensional garbage direction when it vanishes. The leftover output is orthogonal to the clean signal port.

Write the supported parity orders as 2j+p, p=d mod2, j=0,...,q=floor(d/2). Pad the coefficients with zeros to K=2^a>=q+1, where a=ceil(log2(q+1)) and a=0 when q=0. Let mu_j=alpha_(2j+p), beta=sum_j|mu_j|>0. Prepare |p_mu>=sum_j sqrt(|mu_j|/beta)|j> on the a-qubit index register and put phases theta_j=mu_j/|mu_j| on nonzero entries (phase1 for zero entries). Controlled SELECT applies E^j in the even case and U R E^j in the odd case. Phase-weighted prepare-SELECT-unprepare then has all-zero index/signal block sum_j mu_j T_(2j+p)^SV(A)/beta=f^SV(A)/beta. For complex coefficients use the actual unit-modulus theta_j as relative phases, not unsigned magnitudes; real signs are its special case. The total clean flag size is1+a, with any implementation scratch separately declared. The factor beta is achieved by this coefficient LCU; it is not asserted to be the least possible factor for every matrix/spectrum.

For query accounting, binary j=sum_l b_l2^l lets SELECT reuse one controlled E^(2^l) per index bit. It takes sum_l2^l=K-1 E steps, hence2(K-1) calls to U/U†, plus one unconditional U R for odd parity. Distinctly, the even circuit uses K-1 calls to U and K-1 to U†; the odd circuit uses K calls to U and K-1 to U†. The multiplication order in that odd case is U R on the LEFT of the even SELECT, so it acts after the even powers. This does not require a promise that an arbitrary unknown U can be controlled for free: controlled-E itself can be realized as U† controlled-R U controlled-R. With control0 the U†U cancels, and with control1 it is E; known controlled signal reflections have their own gate cost. K is less than2(q+1) except the trivial K1 case, giving O(d) queries for d>=1 and O(log(d+1)) index qubits. Rebuilding every independently selected order instead would sum j and can cost quadratically many queries.

For d0 and f=alpha_0 nonzero, a0 and no U query are needed: implement its unit phase times the identity clean block, with factor|alpha_0|. For d1 with odd f=alpha_1 x, a0 and one U query suffice, using the coefficient phase and U R (R fixes clean input). If all coefficients are zero, the target is zero and normalized coefficient preparation by beta is undefined; use any chosen POSITIVE factor, e.g.1, and a zero-block unitary X on a signal qubit instead. Do not call zero a positive factor or the zero polynomial degree-d in the usual exact-degree sense. The extension to a parity-compatible degree bound covers this degenerate coefficient list explicitly.

For an exact (kappa,1) input the compressed contraction is B=A/kappa. Applying the unmodified f algorithm yields f^SV(B)/beta, not generally f^SV(A)/beta. To recover the latter, form g(x)=f(kappa*x), retaining parity since kappa>0, reexpand g=sum_j gamma_j T_j, and use beta_kappa=sum_j|gamma_j| as the achieved factor. The positive scaling preserves singular vectors and g(sigma(A)/kappa)=f(sigma(A)), so g^SV(B)=f^SV(A). In the counterexample g(x)=2x and beta_kappa2, consistent with the compression bound. An approximate input exactly encodes its actual contraction J†U J; relating the resulting transform back to the intended A requires a separate perturbation/error contract, not just changing kappa in an exact formula.

On normalized input psi the chosen all-zero success probability is ||f^SV(A)psi||^2/beta^2 in the normalized theorem, with conditional state f^SV(A)psi/||f^SV(A)psi|| only if that norm is nonzero. Query counts do not produce arbitrary coefficient states, implement phases/controlled reflections, synthesize finite-bit gates, prepare psi, amplify a small success branch or read out the answer for free. Exact coefficient oracles here are ideal construction ingredients with separately accounted costs, as distinct from an executed compiler or a robustness theorem.

1. Refutes the missing-normalization promise by an exact valid input and compression-norm obstruction; then states the exact normalized-input conditional parity-dependent SV target and beta block with proper coefficient phases, fixed projections and nonzero-beta condition. (1 weight)
2. Accounts for the parity-order index register a=ceil(log2(floor(d/2)+1)), power-of-two zero padding and clean signal size, handling d0,d1 and all-zero coefficients without invalid logarithms, coefficient normalization or zero block factor. (1 weight)
3. Derives even E^j and odd U R E^j accepted blocks and binary SELECT reuse for O(d) U/U† calls; retains chronological factor order and0/1 singular-value endpoints. Any controlled-query implementation ingredient is explicit, not a free unknown-unitary control assumption. (1 weight)
4. Separates f^SV(A/kappa) from f^SV(A), rescales/reexpands g(x)=f(kappa x) and changes the coefficient factor accordingly. Keeps approximate-error, garbage/success normalization, coefficient-oracle, gate, finite-bit, input-state, amplification and readout accounting separate. (1 weight)

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.

Read the Lean track and existing diagnostic warmups

• website/research/sources.json

  lin-wiebe-2026-qasc

  Source SHA-256: 9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae · MIT metadata only
• Primary source

Contract: c70aee607b7ca91f359152628fb31bbab1e0855382bbbfcfa55b8468e8f239da

Item digest: 8b637db9ec6304099cb936ee63657fc1aa0901c5ae45b4e046ac8336b68e326a

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 6. This is not measured graph distance or model difficulty.

{ "question_version": 2, "predecessor_key": "qcb-core-plan-510-definite-parity-lcu-resource-statement", "predecessor_item_digest": "ff1a28db552836b74d04d8d088fac67ad5b1f63dc3d4aa67521223461a8981d0", "predecessor_contract_hash": "2bf5d37381543b15e282db4a961dd4db9e475ef5dda028ddbb1eb0448213bd6c", "current_contract_hash": "c70aee607b7ca91f359152628fb31bbab1e0855382bbbfcfa55b8468e8f239da", "changed_contract_fields": [ "question" ], "repair_record": "shared/repairs/plan-510-normalized-input-resource-question-successor.json", "repair_record_digest": "388b6fd668fa6318fd4cb4e64d2f5a7c8ab3f5822b6d520dad7a90d40ee80aad", "review_record": "reports/textbook-v1/repairs/plan-510-normalized-input-resource-question-successor-review.json", "review_digest": "98c29748a02c94322ecdf99855cc6c0365ba6267a8698c8b088605e85e60254c", "equivalence_to_predecessor_claimed": false, "additional_core_count": 0 }