Sparse SDP matrix access and computational model

For $d\times d$ matrices with at most $s$ nonzero entries in each row, fix a padded slot set $\{1,\dots ,s\}$ and an invalid-slot sentinel $\mathrm{\perp }$. The index oracle is the basis permutation $O_I\mathrm{\mid }k,\mathrm{\ell },z⟩=\mathrm{\mid }k,\mathrm{\ell },z<mrow><mi\; mathvariant="normal">X</mi><mi\; mathvariant="normal">O</mi><mi\; mathvariant="normal">R</mi></mrow>j_{k,\mathrm{\ell }}⟩,$ where $j_{k,\mathrm{\ell }}$ is the encoded column of the $\mathrm{\ell }$th nonzero in row $k$, or $\mathrm{\perp }$ for padding. The value oracle XORs the finite binary encoding of the real and imaginary parts of the matrix entry into a target register. Specify the completion on invalid row/slot encodings, arithmetic precision/rounding, and whether inverse/controlled calls and reverse-location queries are supplied. Sparse sums ${\sum }_j{y}_j{A}_j$ require a separate access implementation; entry oracles do not automatically supply it.

Record matrix sparsity and norms, classical input/preprocessing/output time, matrix-entry queries, sparse-sum and QRAM access, circuit gates, width, ancillas, state preparation, and coefficient-bit costs separately. If QRAM is used, state its unitary address/memory action and charge its construction, updates and queries. Query complexity is not standard-gate complexity without an implementation of each oracle.