Sparse access need not give a short term list

Fix $N=2^n$, equip ${\mathbb{C}}^N$ with its standard inner product, and let $\mathrm{\mid }x⟩$ denote its standard basis. For any function $f:[N]\to \{-1,+1\}$ define $H_f={\sum }_{x=1}^{N}f(x)\mathrm{\mid }x⟩⟨x\mathrm{\mid }$. This diagonal matrix is Hermitian and each row has exactly one nonzero entry; the row-location oracle returns $x$ at the nonzero slot, and the entry-value oracle returns $f(x)$ on the diagonal query $(x,x)$. Thus the input is $1$-sparse in [F1].

The canonical ordered rank-one list is $H_f={\sum }_{x=1}^{N}f(x)\mathrm{\mid }x⟩⟨x\mathrm{\mid }$, with $N$ terms, and is determined by $(f(1),\dots ,f(N))$. There are $2^N$ such lists but only $2^N-1$ binary strings of length less than $N$, so any lossless binary encoding has a worst-case length of at least $N$ bits. If a deterministic exact recovery procedure makes fewer than $N$ classical row-value queries, some row $x$ is unqueried; changing only $f(x)$ preserves every reply in its transcript but changes the canonical list, so that transcript cannot determine the list for both inputs.

Since $N=2^n$, this canonical list's description and exact classical recovery costs grow exponentially in the index length $n$. The sparse model supplies only the row/value calls by [F1], whereas the term-list model additionally requires the list and term-evolution access by [F2]; those extra promises therefore cannot be inferred from the sparse interface. No lower bound for every possible alternative decomposition, quantum query procedure, or circuit implementation is asserted.