ℓ2 sample/query access to vectors and matrices

For a finite complex vector $v=(v_1,\dots ,v_n)\in {\mathbb{C}}^n$, put $\mathrm{\parallel }v{\mathrm{\parallel }}_2=({\sum }_{i=1}^n\mathrm{\mid }{v}_i{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$, where $\mathrm{\mid }\cdot \mathrm{\mid }$ is the complex modulus of Real and imaginary parts, complex conjugation, and modulus. Its squared-entry distribution is $D_v(i)=\mathrm{\mid }{v}_i{\mathrm{\mid }}^2\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$ on $[n]$ when $\mathrm{\parallel }v{\mathrm{\parallel }}_2>0$. A vector has ℓ2 sample/query access when the interface supplies: (a) an entry query returning $v_i$; (b) its norm $\mathrm{\parallel }v{\mathrm{\parallel }}_2$; and (c) a sample distributed according to $D_v$. For any finite adaptive sequence of sample calls, conditioned on the preceding history and the current requested sampler, each returned index has the declared law and uses fresh randomness independent of that history; in particular, repeated calls to a fixed sampler are mutually independent in the sense of Pairwise and mutual independence of finite-valued random variables. Every draw is charged. The interface states the cost and precision of every query, norm computation, and sample, and any preprocessing or storage cost. If $v=0$, $D_v$ is undefined and the sampler returns the explicit status ZERO; it does not return a fictitious normalized sample.

For a finite real matrix $A\in {\mathbb{R}}^{m\times n}$, put $\mathrm{\parallel }A{\mathrm{\parallel }}_F=({\sum }_{i=1}^m{\sum }_{j=1}^n{A}_{ij}^2{)}^{1\mathrm{/}2}$, the Frobenius norm of The Frobenius norm $\parallel A{\parallel }_F=({\sum }_{i,j}\mathrm{\mid }{a}_{ij}{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$ on real or complex matrices. Row and column ℓ2 access supplies entry queries, row and column norms, and samplers for each nonzero row and column according to its squared-entry distribution. These real rows and columns are instances of the vector interface above. It also declares preprocessing, storage, and whether their costs are amortized. The common row sampler $i\sim D_A$ has law $\mathbb{P}(i)=\mathrm{\parallel }{A}_{i,\ast }{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$ for $A\mathrm{\ne }0$, and the column sampler $j\sim D_{A^T}$ has law $\mathbb{P}(j)=\mathrm{\parallel }{A}_{\ast ,j}{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$; zero rows and columns have probability zero. An all-zero matrix returns ZERO for a request for a norm-normalized sample. All row-vector, column-vector, matrix-level row, and matrix-level column samplers obey the same conditional fresh-randomness rule; every draw is charged. Access to entries alone does not imply either sampler. The access and output costs are recorded separately under Classical output, quantum-state output, and access costs, and the distributions are finite probability laws as in Finite probability spaces, outcome weights, events, and event probabilities.

This is an input-data structure assumption. It is not a quantum circuit, state-preparation oracle, QRAM, or an assertion that the preprocessing needed to implement it is sublinear. The Tang matrix algorithms on this page specialize to real matrices; no complex-matrix extension of those algorithms is asserted.