pdf icon
Volume 3 (2007) Article 4 pp. 61-79
A Simple PromiseBQP-complete Matrix Problem
Received: October 22, 2006
Published: March 30, 2007
Download article from ToC site:
[PDF (208K)] [PS (354K)] [Source ZIP]
Keywords: quantum computation, complexity, BQP, completeness, PromiseBQP, PromiseBQP-complete problem, ``non-quantum'' characterization of BQP
ACM Classification: F.1.3, G.1.3
AMS Classification: 15A18, 15A60, 65F50, 65F15

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 $(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\rangle$ 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.