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.