Polynomial Signals
Exercise PLAN-508
primary source nl only. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- K is a power of two so the binary digit scheme is exact
- Query count means uses of the base block-encoding unitary; gate and state-preparation costs are not included
- The degree-2k transform uses exactly 2k base-unitary queries
Question
To build a block encoding of a linear combination of even Chebyshev transforms, sum over k from 0 to K-1 of coefficients times the degree-2k Chebyshev transform, one needs a select operation that, conditioned on an index register holding k, applies the degree-2k transform. The degree-2k transform is itself built from 2k uses of the base block-encoding unitary. (a) Prove that a direct index-controlled implementation that applies each degree-2k transform independently uses a number of base-unitary queries that grows quadratically in K. (b) Prove that an implementation exploiting the binary digits of the index, which reuses a single squared iterate across the digits, uses only 2K-2 base-unitary queries when K is a power of two, and observe that this equals the query count of a single degree-(2K-2) transform. State the query counts without converting them into gate or state-preparation costs.
Hint: mathematical route
A direct index-controlled select of even Chebyshev transforms costs order K^2 base-unitary queries, but reusing one squared iterate across the binary digits of the index costs only 2K-2 queries, equal to a single top-order term.
- Each degree-2k branch costs 2k base-unitary queries.
- Independent summation over k gives K(K-1), order K squared.
- Binary expansion of k turns the power into per-digit controlled applications of the squared iterate to the 2^j power.
- Each position contributes 2 times 2^j queries.
- The geometric sum totals 2^{a+1}-2 = 2K-2 queries.
- This equals a single degree-(2K-2) transform; counts stay at query level only.
Reference solution
(a) In the direct implementation the branch for index k runs the degree-2k transform, costing 2k queries to the base unitary. Summing independently over k from 0 to K-1 gives total queries 2 times (0 + 1 + ... + (K-1)) = 2 times K(K-1)/2 = K(K-1), which is of order K squared. The inefficiency is that the squared base iterate used inside degree-2k is rebuilt from scratch for every k rather than reused. (b) Write K = 2^a and the index k in binary as digits k_{a-1} ... k_0. The degree-2k transform equals the squared base iterate raised to the power k. Using the binary expansion, k = sum over j of k_j 2^j, so raising to the power k is achieved by, for each digit position j, conditionally applying the squared iterate raised to the 2^j power exactly when digit k_j is one. The squared iterate to the 2^j power is applied once per position, contributing 2 times 2^j base-unitary queries (each squared iterate is two base-unitary uses). The total is 2 times (1 + 2 + 4 + ... + 2^{a-1}) = 2 times (2^a - 1) = 2^{a+1} - 2 = 2K - 2 queries. This matches the query count of a single degree-(2K-2) transform, which uses 2 times (K-1) = 2K-2 base-unitary queries, so the whole controlled sum costs no more base-unitary queries than one top-order term. These are counts of queries to the base unitary only; translating them into elementary-gate counts or into the cost of preparing the index-register superposition is a separate accounting that depends on additional oracle implementations and is not performed here.
Assessment rubric
- Shows the direct implementation costs 2 times sum of k = K(K-1), order K squared, and identifies the non-reuse as the cause (1 weight)
- Explains the binary-digit scheme raises the squared iterate to the power k via per-digit controlled applications (1 weight)
- Computes the total as 2 times (2^a - 1) = 2K - 2 queries for K = 2^a (1 weight)
- Observes 2K-2 equals a single degree-(2K-2) transform's query count and keeps the accounting at query level without converting to gate or preparation cost (1 weight)
Graph-grounded prerequisites
These are support/source anchors, not an automatically extracted theorem-dependency proof.
- Oracle and circuit complexity (frozen curriculum anchor; see graph registry)
- Block Encoding (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: 7cf4beda2da8c73ec4a6fa0699a93edd8cf7c9b9585060f38c2a11ce7d2c9c40
Item digest: 99fb50087dd29dddc1503144dc867f4855efd2d53d33cf573ad8a8869fe5ed47
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 6. This is not measured graph distance or model difficulty.