Received: October 22, 2006
Published: March 30, 2007
DOI: 10.4086/toc.2007.v003a004
Abstract: [Plain Text Version]
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 (Am)jj of the matrix Am up to an error of εbm, where b is an a priori given upper bound on the norm of A and m and ε 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 jth basis vector and raising the outcome to the mth 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 mth statistical moment for some appropriately chosen m, i.e., by the jth diagonal entry of Am. 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.