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

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

• Could you please define MQ²? – Martin Schwarz May 31 '11 at 10:55
• As well as AWPP ? – Suresh Venkat May 31 '11 at 21:33
• $\mathsf{AWPP}$ can be founded in the complexity zoo. $\mathsf{MQ^2}$ is defined in this paper. – Hsien-Chih Chang 張顯之 Jun 1 '11 at 3:44
• Wouldn't it be any NP-Complete problems? – Joshua Herman Jun 6 '11 at 3:00

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

• 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.) $\;\;\;\;$ – user6973 Apr 17 '15 at 11:18
• @RickyDemer: right, typo in description of $\varepsilon$, will fix. – Niel de Beaudrap Apr 17 '15 at 16:23
• 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. $\;\;\;\;$ – user6973 Apr 17 '15 at 19:26
• @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. – Niel de Beaudrap Apr 17 '15 at 20:07