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.