Polynomial Signals
Exercise PLAN-511
primary source nl only. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- A is accessed by a unitary with an input projector of rank N and an output projector of rank N'
- Each reflection is twice a projector minus the identity
- The iterate is adjoint(U) (output reflection) U (input reflection)
Question
Suppose an operator A maps an N-dimensional input space into an N'-dimensional output space and is accessed through a single unitary U on a larger space together with two projectors: an input projector of rank N and an output projector of rank N'. Define the two reflections as twice the respective projector minus the identity, and define the qubitization iterate as the product of the adjoint of U, the OUTPUT reflection, U, and the INPUT reflection. (a) Prove that when the input and output ranks are equal this iterate reduces, after a suitable change of basis, to the ordinary same-space qubitization iterate. (b) Explain precisely what feature of the construction continues to make sense when the ranks differ, and why the two-dimensional reduction underlying the cosine-sine analysis still applies.
Hint: mathematical route
Qubitization beyond the computational basis is a product of two projector reflections; equal input/output ranks reduce it to the ordinary iterate, and unequal ranks still admit the two-dimensional rotation analysis because any two-reflection product splits into at most two-dimensional invariant planes.
- Equal ranks give a unitary identifying the output subspace with the input subspace.
- Under this identification the iterate becomes adjoint(U) R U R, the ordinary same-space iterate.
- For general ranks the iterate is still a well-defined product of two projector reflections.
- A product of two reflections splits the space into at most two-dimensional invariant planes.
- Rank mismatch only changes the number of paired planes versus fixed one-dimensional pieces.
- Each two-dimensional plane is a rotation whose angle encodes a singular value of A.
Reference solution
(a) When N' = N the output projector has the same rank as the input projector, so there is a unitary change of basis identifying the output subspace with the input subspace; under this identification the output reflection becomes the input reflection and U together with its adjoint act between two copies of the same N-dimensional flagged subspace. Substituting, the iterate adjoint(U) (output reflection) U (input reflection) becomes adjoint(U) (input reflection) U (input reflection), which is exactly the standard same-space qubitization iterate adjoint(U) R U R with the single reflection R = 2(input projector) - I. Thus the general iterate specializes to the ordinary one up to the basis change. (b) When the ranks differ the construction still makes sense because the iterate is defined purely as a product of two reflections built from genuine projectors; nothing in that definition requires the two projector ranks to agree. The cosine-sine / two-dimensional reduction continues to apply because the product of two reflections always decomposes the ambient space into mutually orthogonal subspaces that are at most two-dimensional and invariant: on each such plane each reflection acts as a one-dimensional sign flip relative to the plane's intersection with the respective projector range, and the product of the two reflections acts as a rotation of that plane. The possibly different ranks only change how many planes are paired versus left as fixed vectors (the mismatch in dimension contributes extra invariant one-dimensional pieces), but every two-dimensional block still carries a planar rotation whose angle encodes a singular value of A. Hence the same singular-value transformation analysis via two-dimensional rotations survives when N' is not equal to N; this is the natural setting for a basis-changed singular value transformation.
Assessment rubric
- Shows that equal ranks allow a basis change identifying output with input subspace, reducing the iterate to adjoint(U) R U R with one reflection (1 weight)
- States the general iterate is well defined for any ranks since it is just a product of two projector reflections (1 weight)
- Explains the product of two reflections always splits the space into at most two-dimensional invariant planes (1 weight)
- Notes rank mismatch only alters the count of paired planes versus fixed vectors, with each plane still a rotation encoding a singular value (1 weight)
Graph-grounded prerequisites
These are support/source anchors, not an automatically extracted theorem-dependency proof.
- Operator and semigroup theory (frozen curriculum anchor; see graph registry)
- Matrix analysis (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: ed4585cfb75c266e5b089844b910e94a070956a03ae17c3f01168dd077e4f78e
Item digest: 216c79773b04ab1d4a02081409afd1d5bcb8b699bbc13e5e52d49665f0603746
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 6. This is not measured graph distance or model difficulty.