Scientific Computing
Exercise PLAN-010
primary source nl only. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.
Assumptions and conventions
Question
To certify that an (m+n)-qubit unitary U exactly embeds an n-qubit matrix A as its all-zeros block with unit factor, one checks the entrywise identities <0^m, i| U |0^m, j> = A_{ij} for all computational-basis indices i, j. (a) Explain operationally how each such entry can be read off by preparing the ancilla in all-zeros and the system in basis state j, applying U, and overlapping with the all-zeros-ancilla basis state i, and how a composed unitary U = U_B U_C lets one evaluate the two halves independently before overlapping. (b) Explain why checking all entries equal to A_{ij} is equivalent to the exact operator identity (all-zeros block of U equals A), but why for an APPROXIMATE embedding entrywise closeness of each A_{ij} is NOT the right accuracy notion: give the quantity that the definition of approximate embedding actually controls and explain how it can be large even when every entry error is tiny.
Hint: mathematical route
Entrywise checks certify an exact unit-factor block encoding and equal the operator identity, but approximate embedding is defined by an operator-norm bound that small per-entry errors can violate after dimensional accumulation.
- The entry <0^m,i|U|0^m,j> is read by prepare-apply-overlap, and factors as (U_B-dagger|0^m,i>)-dagger(U_C|0^m,j>) for U = U_B U_C.
- All entry equalities B_{ij} = A_{ij} are equivalent to the exact operator identity B = A.
- Approximate embedding controls ||A - alpha B|| <= epsilon; small entry errors can sum to a large operator norm (up to d*delta).
Reference solution
(a) Preparing |0^m>|j>, applying U and projecting onto <0^m, i| extracts exactly the number <0^m, i| U |0^m, j>, which by construction is the (i,j) entry of the all-zeros block; running over all i, j reads off the whole block. If U = U_B U_C, then <0^m, i| U_B U_C |0^m, j> = (U_B-dagger |0^m, i>)-dagger (U_C |0^m, j>), so one can prepare and evaluate the two states U_B-dagger|0^m,i> and U_C|0^m,j> independently and take their inner product; this is the standard way to verify a product construction entry by entry. (b) The all-zeros block is the operator B with matrix entries B_{ij} = <0^m,i|U|0^m,j>; the full set of equalities B_{ij} = A_{ij} for all i, j is literally the statement B = A as operators, so for EXACT embedding entrywise and operator identity coincide. For APPROXIMATE embedding, however, the definition controls the OPERATOR NORM of the difference, ||A - alpha B|| <= epsilon, not the individual entry errors. Operator norm is not controlled by entrywise size: a d-by-d matrix with every entry equal to a small delta has operator norm up to d*delta (e.g. the all-ones matrix times delta has norm d*delta), which grows with dimension even as each entry error delta stays tiny. Hence many small entry errors can accumulate coherently into a large operator-norm error, so entrywise closeness is neither the quantity the definition uses nor a sufficient accuracy guarantee; the correct certificate is a bound on the spectral/operator norm of A - alpha B.
Assessment rubric
- Describes the state-preparation/overlap procedure that reads <0^m,i|U|0^m,j> and the factored evaluation for U = U_B U_C via (U_B-dagger|0^m,i>)-dagger(U_C|0^m,j>) (1 weight)
- States that the full set of entry equalities B_{ij} = A_{ij} is exactly the operator identity B = A for exact embedding (1 weight)
- Identifies that approximate embedding controls the operator norm ||A - alpha B|| <= epsilon, not per-entry errors (1 weight)
- Gives a dimension example (e.g. all-entries-delta matrix has norm up to d*delta) showing tiny entry errors can produce a large operator-norm error (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)
- Verification and metrology (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: 2434f9619ce11e416298ed6a4f592aff67aa1626ae6dd1817eb42555a6d57e4c
Item digest: 13ff4d7410b8c1c651c0e8a652cb201ded626374ddf50a7f712d2a82784b3abf
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 3. This is not measured graph distance or model difficulty.