Scientific Algorithms
Exercise PLAN-220
primary source nl only. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- U_A in HBE_{1,m}(A) is Hermitian with ||A|| <= 1
- A = sum_i lambda_i |v_i><v_i| with -1 < lambda_i < 1 (edge cases lambda_i = pm 1 handled separately)
- Pi = |0^m><0^m| tensor I; Z_Pi = 2Pi - I
- lambda_i = cos theta_i with 0 < theta_i < pi
- T_k(cos theta) = cos(k theta), U_{k-1}(cos theta) = sin(k theta)/sin theta
Question
Let U_A in HBE_{1,m}(A) be a Hermitian block encoding of a Hermitian A with ||A|| <= 1, spectral decomposition A = sum_i lambda_i |v_i><v_i|, so that U_A |0^m>|v_i> = lambda_i |0^m>|v_i> + sqrt(1-lambda_i^2)|perp_i> with Pi|perp_i> = 0, Pi = |0^m><0^m| tensor I. For -1 < lambda_i < 1, prove that H_i = span{|0^m>|v_i>, |perp_i>} is a 2D invariant subspace of U_A on which U_A is a reflection [[lambda_i, sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2), -lambda_i]], that the iterate O = U_A Z_Pi (with Z_Pi = 2 Pi - I) acts on H_i as the rotation [[lambda_i, -sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2), lambda_i]], and hence that O^k restricted to H_i has top-left entry T_k(lambda_i) (Chebyshev polynomial of the first kind), so O^k = (U_A Z_Pi)^k is a (1,m,0)-block-encoding of T_k(A). State where Hermiticity of U_A is used.
Hint: mathematical route
For a Hermitian block encoding, each eigenvector is qubitized into a 2D subspace where U_A is a reflection and O = U_A Z_Pi a rotation; O^k has top-left T_k(lambda_i), so (U_A Z_Pi)^k block-encodes the Chebyshev polynomial T_k(A).
- U_A Hermitian unitary gives U_A^2 = I; applying U_A twice yields U_A|perp_i> = sqrt(1-lambda_i^2)|0^m>|v_i> - lambda_i|perp_i>, so H_i is 2D invariant.
- In B_i, [U_A]_{B_i} = [[lambda_i, sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2), -lambda_i]], a reflection.
- [Z_Pi]_{B_i} = diag(1,-1), so O = U_A Z_Pi has [O]_{B_i} = [[lambda_i,-sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2),lambda_i]], a rotation.
- [O^k]_{B_i} has top-left entry cos(k theta_i) = T_k(lambda_i).
- Summing over i gives Pi O^k Pi = |0^m><0^m| tensor T_k(A), so O^k in BE_{1,m,0}(T_k(A)).
Reference solution
Invariant subspace and reflection form: by the HBE relation, U_A|0^m>|v_i> = lambda_i|0^m>|v_i> + sqrt(1-lambda_i^2)|perp_i>, with |perp_i> normalized and orthogonal to the Pi-subspace. Since U_A is Hermitian (U_A = U_A^dagger) and U_A is unitary, U_A^2 = I. Apply U_A again to the identity above: U_A(U_A|0^m>|v_i>) = |0^m>|v_i>, i.e. lambda_i U_A|0^m>|v_i> + sqrt(1-lambda_i^2) U_A|perp_i> = |0^m>|v_i>. Substituting U_A|0^m>|v_i> and solving gives U_A|perp_i> = sqrt(1-lambda_i^2)|0^m>|v_i> - lambda_i|perp_i>. Thus both U_A|0^m>|v_i> and U_A|perp_i> lie in H_i = span{|0^m>|v_i>, |perp_i>}, so H_i is invariant, and in the ordered basis B_i = {|0^m>|v_i>, |perp_i>} the matrix of U_A is [[lambda_i, sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2), -lambda_i]], a (symmetric, trace-0, determinant -1) reflection. Hermiticity is used precisely here: applying U_A = U_A^dagger a SECOND time (via U_A^2 = I) is what produces the closed expression for U_A|perp_i> and hence the 2D invariance; without Hermiticity U_A|perp_i> need not stay in H_i. Iterate as rotation: H_i is invariant for Pi too, with [Pi]_{B_i} = [[1,0],[0,0]] (since |0^m>|v_i> is in range(Pi) and |perp_i> is orthogonal to it). Hence Z_Pi = 2Pi - I has [Z_Pi]_{B_i} = [[1,0],[0,-1]], a reflection. The iterate O = U_A Z_Pi has matrix [[lambda_i, sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2), -lambda_i]] [[1,0],[0,-1]] = [[lambda_i, -sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2), lambda_i]], which with lambda_i = cos theta_i is exactly the rotation [[cos theta_i, -sin theta_i],[sin theta_i, cos theta_i]] (product of two reflections = rotation). Chebyshev powers: therefore [O^k]_{B_i} = [[cos k theta_i, -sin k theta_i],[sin k theta_i, cos k theta_i]] = [[T_k(lambda_i), -sqrt(1-lambda_i^2) U_{k-1}(lambda_i)],[sqrt(1-lambda_i^2) U_{k-1}(lambda_i), T_k(lambda_i)]], using T_k(cos theta) = cos(k theta) and U_{k-1}(cos theta) = sin(k theta)/sin theta. The top-left entry is T_k(lambda_i). Block encoding of T_k(A): the vectors {|0^m>|v_i>} span range(Pi), and on each H_i the (0^m,0^m) component of O^k equals T_k(lambda_i). Summing over i, Pi O^k Pi = sum_i T_k(lambda_i) |0^m>|v_i><v_i|<0^m| = |0^m><0^m| tensor T_k(A). Hence (<0^m| tensor I) O^k (|0^m> tensor I) = T_k(A), i.e. O^k = (U_A Z_Pi)^k in BE_{1,m,0}(T_k(A)). (For lambda_i = pm 1 the subspace is already 1D-invariant and T_k(pm1) = (pm1)^k is reproduced trivially.)
Assessment rubric
- Uses U_A Hermitian (U_A^2 = I) to apply U_A twice and derive U_A|perp_i> = sqrt(1-lambda_i^2)|0^m>|v_i> - lambda_i|perp_i>, proving H_i is 2D-invariant with the reflection matrix (1 weight)
- Explicitly identifies where Hermiticity is used (the second application / U_A^2 = I closing the subspace) (1 weight)
- Computes [Z_Pi]_{B_i} = diag(1,-1) and the product O = U_A Z_Pi as the rotation [[lambda_i,-sqrt(1-lambda_i^2)],[sqrt(1-lambda_i^2),lambda_i]] (1 weight)
- Raises to the k-th power to get top-left entry T_k(lambda_i) and sums over i to conclude O^k in BE_{1,m,0}(T_k(A)) (1 weight)
Graph-grounded prerequisites
These are support/source anchors, not an automatically extracted theorem-dependency proof.
- Block Encoding (frozen curriculum anchor; see graph registry)
- Operator and semigroup theory (frozen curriculum anchor; see graph registry)
- Matrix analysis (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: ec9dc64e542b86dfc207f02ba3eeea2716c1bf7559db9e35315fbc79f85a710c
Item digest: 17fa9371009c4d46bf734d23da434d92f20544b991214dd9f1936d2ae4633bcc
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 5. This is not measured graph distance or model difficulty.