Scientific Algorithms
Exercise PLAN-216
primary source nl only. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- Pi, Pi' are orthogonal projectors of ranks N, N' with the given orthonormal bases
- Xi, Xi' are unitaries whose first N, N' columns are those bases
- N' <= MN
- Xi_N, (Xi')_{N'} are the first-column blocks; A~ = ((Xi')_{N'})^dagger U_A Xi_N
- Operator-norm error ||.|| defines the approximation
Question
The block-encoding notion generalizes beyond computational-basis subspaces. Fix rank-N and rank-N' orthogonal projectors Pi, Pi' on an ambient space C^{MN} (M = 2^m), with orthonormal bases {|phi_j>}_{j in [N]} for range(Pi) and {|psi_i>}_{i in [N']} for range(Pi'). Collect these as the first columns of unitaries Xi, Xi' and let Xi_N, (Xi')_{N'} be those column blocks. For a unitary U_A on C^{MN}, define the induced block A~ := ((Xi')_{N'})^dagger U_A Xi_N in C^{N' x N}. Prove that the (i,j) entry of A~ equals <psi_i| U_A |phi_j>, that A~ coincides with the compression Pi' U_A Pi expressed in the chosen bases, and hence that the exact relation Pi' U_A Pi = sum_{i,j} |psi_i> A_ij <phi_j| is equivalent to A~ = A. Then state the (alpha,m,eps)-generalized block-encoding condition ||A - alpha A~|| <= eps and explain why it reduces to the ordinary computational-basis definition when Pi = Pi' = |0^m><0^m| tensor I and N' = N.
Hint: mathematical route
The induced block A~ = ((Xi')_{N'})^dagger U_A Xi_N has entries <psi_i|U_A|phi_j> and equals the compression Pi' U_A Pi in the chosen bases; ||A - alpha A~|| <= eps generalizes the computational-basis definition.
- Xi_N|e_j> = |phi_j>, (Xi')_{N'}|e_i> = |psi_i>, so A~_{ij} = <psi_i| U_A |phi_j>.
- With Pi = sum_j |phi_j><phi_j|, Pi' = sum_i |psi_i><psi_i|, Pi' U_A Pi = sum_{i,j} |psi_i> A~_{ij} <phi_j|.
- Hence Pi' U_A Pi = sum |psi_i> A_ij <phi_j| iff A~ = A; approximately, ||A - alpha A~|| <= eps.
- For Pi=Pi'=|0^m><0^m| tensor I, N'=N, A~_{ij} = <0^m|<i|U_A|0^m>|j>, the standard block.
- So the generalized condition reduces to the ordinary (alpha,m,eps)-block-encoding definition.
Reference solution
Entry formula: Xi_N has columns |phi_0>,...,|phi_{N-1}>, so Xi_N |e_j> = |phi_j> for the standard basis vector |e_j> of C^N; similarly (Xi')_{N'} |e_i> = |psi_i>, hence ((Xi')_{N'})^dagger |x> has i-th component <psi_i|x>. Therefore the (i,j) entry of A~ = ((Xi')_{N'})^dagger U_A Xi_N is A~_{ij} = <e_i| ((Xi')_{N'})^dagger U_A Xi_N |e_j> = (((Xi')_{N'})|e_i>)^dagger U_A (Xi_N |e_j>) = <psi_i| U_A |phi_j>. Compression identity: the orthogonal projectors can be written Pi = sum_j |phi_j><phi_j| and Pi' = sum_i |psi_i><psi_i| (spectral form on their ranges). Then Pi' U_A Pi = sum_{i,j} |psi_i> <psi_i| U_A |phi_j> <phi_j| = sum_{i,j} |psi_i> A~_{ij} <phi_j|. So Pi' U_A Pi, re-expressed in the bases {|psi_i>}, {|phi_j>}, has exactly the matrix of coefficients A~. Consequently the exact encoding requirement Pi' U_A Pi = sum_{i,j} |psi_i> A_ij <phi_j| holds if and only if A~_{ij} = A_ij for all i,j, i.e. A~ = A. Approximate condition: allowing a subnormalization alpha and error eps, U_A is an (alpha,m,eps)-generalized block-encoding of A with respect to (Pi,Pi') iff ||A - alpha A~|| <= eps (operator norm), i.e. the compression alpha A~ = alpha Pi' U_A Pi (in the chosen bases) approximates A. Reduction to the usual definition: set Pi = Pi' = Pi_{0^m} := |0^m><0^m| tensor I and N' = N. Then range(Pi) = range(Pi') is the computational ancilla-0^m subspace; choosing Xi = Xi' = I (identity, whose first N columns are |0^m>|j>) gives Xi_N |e_j> = |0^m>|j> and (Xi')_{N'} |e_i> = |0^m>|i>, so A~_{ij} = <0^m|<i| U_A |0^m>|j>, which is exactly the standard top-left block (<0^m| tensor I) U_A (|0^m> tensor I). Thus ||A - alpha A~|| <= eps becomes the ordinary (alpha,m,eps)-block-encoding condition. The generalization is purely a change of input/output subspaces (via Pi, Pi' and the basis unitaries) from the fixed computational ancilla-flag subspace to arbitrary ones.
Assessment rubric
- Shows A~_{ij} = <psi_i| U_A |phi_j> using that Xi_N, (Xi')_{N'} map standard basis vectors to the chosen orthonormal basis vectors (1 weight)
- Writes Pi = sum_j |phi_j><phi_j|, Pi' = sum_i |psi_i><psi_i| and derives Pi' U_A Pi = sum_{i,j} |psi_i> A~_{ij} <phi_j| (1 weight)
- Concludes the exact encoding Pi' U_A Pi = sum |psi_i> A_ij <phi_j| is equivalent to A~ = A, and states the approximate condition ||A - alpha A~|| <= eps (1 weight)
- Shows the reduction to the computational-basis definition for Pi = Pi' = |0^m><0^m| tensor I, N' = N (A~_{ij} = <0^m|<i|U_A|0^m>|j>) (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: 218e62360e7ad52a64a746b4215a4f484139d2493e407dff8bbf485a38204e1b
Item digest: 25c3a802898fe52a55571fa3631a3925ffbb6c11f24473f29e40723e7f634ad2
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 5. This is not measured graph distance or model difficulty.