Is there any problem which is in AWPP but conjectured to be not in BQP?

Question

Is there any known problem which is in $\mathsf{AWPP}$ but conjectured to be not in $\mathsf{BQP}$? What about relative to an oracle?

Is there any known problem in $\mathsf{MQ^2}$ which is conjectured to be not in $\mathsf{BQP}$?

Answer 1

The relationship of $\mathsf{AWPP}$ to $\mathsf{BQP}$

$\mathsf{AWPP}$ is the class of languages $L$ for which, for each $\varepsilon \in 2^{-O(\mathop{\mathrm{poly}} n)}$, there is $g \in \mathsf{GapP}$ and $f \in \mathsf{FP}$, such that

• for $x \notin L$ we have $0 \leqslant \frac{g(x)}{f(x)} \leqslant \varepsilon$ and
• for $x \in L$ we have $1-\varepsilon \leqslant \frac{g(x)}{f(x)} \leqslant 1$.

This is a [technical but relatively well-known] upper bound for the class $\mathsf{BQP}$. Its relationship to other "gap-defined classes" could be summarised as $$ \mathsf{SPP \subseteq LWPP \subseteq WPP \subseteq AWPP \subseteq PP}, $$ where $\mathsf{LWPP}$ is notable as a [once more technical but relatively-well known] upper bound on $\mathsf{EQP}$ (with algebraic coefficients over any constant set), and $\mathsf{SPP}$ is the gap-definable version of $\mathsf{UP}$. Thus all of these contain $\mathrm{UNIQUE\text-SAT}$.

By Valiant-Vazirani and the closure of $\mathsf{BQP}$ under subroutines, if $\mathrm{UNIQUE\text-SAT} \in \mathsf{BQP}$, we then have $\mathsf{NP \subseteq PH \subseteq BQP}$. We may reasonably consider this to be unlikely, so $\mathrm{UNIQUE\text-SAT}$ is an easy example of a problem in $\mathsf{AWPP}$ which one may consider unlikely to be in $\mathsf{BQP}$ (albeit a problem which belongs to classes which "seem much smaller" than $\mathsf{AWPP}$ as well).

The relationship of $\mathsf{MQ^2}$ to $\mathsf{BQP}$

The class $\mathsf{AWPP}$ also upper bounds the following (not generally well-known) class defined by Tušarová [arXiv:cs/0507057]:

$\mathsf{MQ^2}$ is the class of languages $L$ for which there is

• a [concisely] poly-time computable family $\bigl\{ T_n \bigr\}_{n \geqslant 1}$ of unitary matrices [i.e. a family of matrices $T_n$ such that the function $(j,k,n) \mapsto \left\langle j \:\!\right\vert \!\!\; T_n \!\!\;\left\vert \:\!k \right\rangle$ can be computed in polynomial time, and where we probably want to impose the restriction to functions computing coefficients over a finite-degree extension of the rational numbers]

• a poly-time computable string-valued function $I$, and

• a poly-time computable predicate $\alpha$ on strings,

such that $\displaystyle\sum_{c : \alpha(c,x) = L(x)} \Bigl\vert\langle c \:\!\lvert\;\! T^2 \!\!\:\ \rvert I(x) \rangle\Bigr\vert^2 \geqslant \tfrac{2}{3}$  [the exponent on the $T$ is significant here].

(In the definition above, we let $L(x) \in \{0,1\}$ denote the characteristic function of $L$.)

The functions $I$ and $\alpha$ serve the role of classical pre-processing and post-processing, respectively, in a quantum algorithm in which we have somehow managed to perform a quite possibly complicated unitary, twice in succession. The input state $\lvert I(x) \rangle$ is a standard basis state which could be efficiently computed by deterministic classical computation, and $\alpha$ serves to deterministically compute whether a possible measurement outcome $\lvert c \rangle$ is a possible "accepting state" for the problem instance $x$.

It is not clear that $\mathsf{MQ^2}$ is comparable to $\mathsf{BQP}$. The operator $T$ in the definition of $\mathsf{MQ^2}$ is specified by its coefficients rather than as a tensor network, so Solovay–Kitaev does not suffice to allow $\mathsf{BQP}$ to simulate such operators; and clearly we do not expect the coefficients of a tensor network such as a quantum circuit family to be easily evaluated, so the reverse containment would also be surprising.

The class $\mathsf{MQ^2}$ is itself not really well-known enough for there to be any common conjectures about it. (This question is the only place I'm aware of it being discussed, apart from the eprint by Tušarová.) But I get the impression that if the native problem of $\mathsf{MQ^2}$ — that of simulating (the square of) an exponentially large matrix with efficiently specifiable coefficients — is in $\mathsf{BQP}$, the techniques used to show this may have important implications for quantum circuit synthesis, and may shed light on the question of $\mathsf{BQP \mathrel{?\!\!\:=} BPP^{BQNC}}$. Thus, if not unlikely, this result would be quite interesting.