Exercise PLAN-210

A diagonal entry-amplitude oracle gives a unit-scale block; for nonzero A the sharp existence scale is ||A||, whereas A=0 admits all positive scales with unattained infimum0. No efficient synthesis inferred.

1. U_A|0>|j> = (A_jj|0> + sqrt(1-|A_jj|^2)|1>)|j>.
2. <0|<i|U_A|0>|j> = A_jj <0|0><i|j> + sqrt(1-|A_jj|^2)<0|1><i|j>, and <0|1>=0 kills the second term.
3. <i|j> = delta_ij gives <0|<i|U_A|0>|j> = A_ii delta_ij, so U_A in BE_{1,1}(A) with this construction's alpha = 1.
4. For diagonal A the sparsity permutation is c(j)=j, so O_c = I and no permutation oracle is required.
5. Any block encoding needs alpha >= ||A||; alpha = 1 saturates this iff ||A|| = 1, and for 0 < ||A|| < 1 a smaller alpha = ||A|| for nonzero A is achievable, so alpha = 1 is not globally optimal there.

Apply U_A = O_A to |0>|j>: U_A |0>|j> = (A_jj |0> + sqrt(1-|A_jj|^2)|1>)|j>. Now take the overlap with <0|<i|: <0|<i| U_A |0>|j> = A_jj <0|0> <i|j> + sqrt(1-|A_jj|^2) <0|1> <i|j>. The second term vanishes because <0|1> = 0. The first term is A_jj <i|j> = A_jj delta_ij. When i = j this equals A_jj = A_ii; when i != j it is 0. Hence <0|<i| U_A |0>|j> = A_ii delta_ij, which is precisely the (i,j) entry of the diagonal matrix A. By the definition of block encoding, (<0| tensor I) U_A (|0> tensor I) = A exactly, with one ancilla qubit (m = 1) and subnormalization alpha = 1, so U_A is in BE_{1,1}(A). No permutation oracle is needed because for a DIAGONAL matrix the row index equals the column index: the single nonzero entry in column j sits at row c(j) = j, i.e. the sparsity permutation c is the identity. In the general 1-sparse case the unique nonzero entry of column j lives at row c(j) != j, so one must apply an index permutation O_c |j> = |c(j)> to move the amplitude-carrying basis state from |j> to |c(j)>; for the diagonal case c = id, so O_c = I and U_A = O_A alone suffices. Optimality -- stated carefully. The general lower bound is that any (alpha,m)-block-encoding of A must satisfy alpha >= ||A|| (operator norm), because the encoded top-left block equals A/alpha and a sub-block of a unitary has operator norm at most 1, forcing ||A||/alpha <= 1. For a diagonal A, ||A|| = max_i |A_ii|. The present construction FIXES alpha = 1 regardless of the entries; this value saturates the lower bound (hence is globally optimal) ONLY in the case ||A|| = max_i |A_ii| = 1, e.g. when some |A_ii| = 1. If instead 0 < max_i |A_ii| = r < 1 strictly, then alpha = 1 is a VALID but NOT optimal subnormalization: the lower bound only demands alpha >= r, and a smaller alpha = r is mathematically achievable -- for example by encoding A/r (whose max entry has modulus 1) with this very construction to obtain an (r,1)-block-encoding of A. Thus alpha = 1 is a property of THIS fixed construction, globally optimal exactly when ||A|| = 1, and for ||A|| < 1 merely a valid upper bound rather than the minimum. The honest statement: the construction yields alpha = 1; it meets the alpha >= ||A|| floor iff ||A|| = 1, and is not subnormalization-optimal when ||A|| < 1. At A=0, every strictly positive scale is feasible (a zero clean block), but scale0 is not an admissible positive normalization; the infimum0 is not an attained positive minimum, and division by the zero norm is never used.

1. Applies U_A = O_A to |0>|j> and expands the overlap <0|<i| U_A |0>|j> (1 weight)
2. Uses <0|1> = 0 to kill the second term and <i|j> = delta_ij to obtain A_ii delta_ij, concluding U_A in BE_{1,1}(A) (this construction's alpha = 1) (1 weight)
3. Explains the sparsity permutation is the identity for a diagonal matrix (c(j)=j), so no O_c is needed, unlike the general 1-sparse case (1 weight)
4. States alpha >= ||A|| and correctly limits optimality: alpha = 1 is globally optimal ONLY when ||A|| = max_i|A_ii| = 1; for 0 < ||A|| < 1 it is valid but NOT optimal (a smaller alpha = ||A|| when ||A||>0 is achievable, e.g. by encoding A/||A||) (1 weight)

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.

Read the Lean track and existing diagnostic warmups

• website/research/sources.json

  lin-wiebe-2026-qasc

  Source SHA-256: 9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae · MIT metadata only
• Primary source

Contract: b769f109045e94e05f993cd19e2c229928093b0ec29bfaa1c75c53a1fd0603d0

Item digest: 1f65e62ee73cdfa4f023076fc698fed90d81a1dbaf24524784aa24219df9cfe4

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 5. This is not measured graph distance or model difficulty.