Theory of Computing ------------------- Title : A Simple PromiseBQP-complete Matrix Problem Authors : Dominik Janzing and Pawel Wocjan Volume : 3 Number : 4 Pages : 61-79 URL : https://theoryofcomputing.org/articles/v003a004 Abstract -------- Let A be a real symmetric matrix of size N such that the number of non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an efficiently computable function. We consider the problem of estimating an arbitrary diagonal entry (A^m)_{jj} of the matrix A^m up to an error of epsilon.b^m , where b is an a priori given upper bound on the norm of A and m and epsilon are polylogarithmic and inverse polylogarithmic in N, respectively. We show that this problem is PromiseBQP-complete. It can be solved efficiently on a quantum computer by repeatedly applying measurements of A to the j-th basis vector and raising the outcome to the m-th power. Conversely, every uniform quantum circuit of polynomial length can be encoded into a sparse matrix such that some basis vector |j> corresponding to the input induces two different spectral measures depending on whether the input is accepted or not. These measures can be distinguished by estimating the m th statistical moment for some appropriately chosen m , i.e., by the j-th diagonal entry of A^m . The problem remains PromiseBQP-hard when restricted to matrices having only -1 , 0 , and 1 as entries. Estimating off-diagonal entries is also PromiseBQP-complete.