Abstract: We study the computational model where we can access a matrix $\mathbf{A}$ only by computing matrix-vector products $\mathbf{A}\mathrm{x}$ for vectors of the form $\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q$. We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of $\mathbf{A}$. Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries. We further prove that algorithms whose queries come from a small alphabet (e.g., $\mathrm{x}_i \in \\{\pm1\\}^n$) cannot test if $\mathbf{A}$ is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1. In steep contrast to the non-Kronecker case, this shows that sketching $\mathbf{A}$ with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.

Lay Summary:

Scientific problems in areas like quantum physcis or quantum information science often involve large matrices that a stored in some compressed format (like an "MPO" or "PEPS"). The quantum physicists and information scientists are interested in computing some linear-algebraic property of the matrix, like the top eigenvalue, von Neumann entropy, or something in that vein. Because these compressed formats are tensor-structured, the algorithms we design are often equivalent to methods that compute matrix-vector products between this large quantum matrix and vectors that have tensor (Kronecker) structure. Theoretically, the methods that operate in this "Kronecker matrix-vector oracle" require computing exponentially many matrix-vector products in the worst case, though it had not been shown that such an expensive cost is necessary to pay.We tackle this problem by using tools from the high-dimensional statistics and oracle complexity literatures, proving that in many regimes and under extremely mild conditions that algorithms which operate by computing only Kronecker matrix-vector products must in fact compute exponentially many such products to recover reliable calculations of linear algebraic properties.Our results show that if you want to compute linear-algebraic properties of really big tensor-structured matrices, as we do in these quantum information settings, then we must do one of two things:1. Find an alternative computational approach beyond the Kronecker matrix-vector product.2. Make strong assumptions about the properties of the input matrix, yielding a sort of "beyond worst-case analysis"