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}$?

  • 9
    $\begingroup$ Could you please define MQ²? $\endgroup$ Commented May 31, 2011 at 10:55
  • 3
    $\begingroup$ As well as AWPP ? $\endgroup$ Commented May 31, 2011 at 21:33
  • 3
    $\begingroup$ $\mathsf{AWPP}$ can be founded in the complexity zoo. $\mathsf{MQ^2}$ is defined in this paper. $\endgroup$ Commented Jun 1, 2011 at 3:44
  • $\begingroup$ Wouldn't it be any NP-Complete problems? $\endgroup$ Commented Jun 6, 2011 at 3:00

1 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.

  • $\begingroup$ By your definition, AWPP = ALL. $\:$ (Proof: Let $g$ and $f$ and $\epsilon$ take the values 1 and 2 and 1/2 respectively, regardless of what $n$ and their inputs are.) $\;\;\;\;$ $\endgroup$
    – user6973
    Commented Apr 17, 2015 at 11:18
  • $\begingroup$ @RickyDemer: right, typo in description of $\varepsilon$, will fix. $\endgroup$ Commented Apr 17, 2015 at 16:23
  • $\begingroup$ By UNIQUE-SAT, do you mean the language or the promise problem? $\:$ If you mean the language, then can you expand on why that language is in AWPP? $\:$ If you mean the promise problem, then one could instead use the promise problem whose AWPP-completeness follows directly from Theorem 1.4. $\;\;\;\;$ $\endgroup$
    – user6973
    Commented Apr 17, 2015 at 19:26
  • $\begingroup$ @RickyDemer: Thanks for the reference! I do mean the promise problem, so that in fact I ought to describe AWPP as a class of decision problems more generally. In this case we could indeed use the native promise problem of AWPP. But, because that native problem doesn't provide any further intuition about what's going on in terms of more widely-known results such as Valiant-Vazirani, I think the exposition in terms of UNIQUE-SAT works better. Indeed, it shows that there are problems in SPP (the littlest of the gap-classes, to which BQP is a cousin) which one should not expect to be in BQP. $\endgroup$ Commented Apr 17, 2015 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.