<h2>The relationship of <span class="math-container">$\mathsf{AWPP}$</span> to <span class="math-container">$\mathsf{BQP}$</span></h2>
<blockquote>
<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#awpp" rel="nofollow noreferrer"><span class="math-container">$\mathsf{AWPP}$</span></a> is the class of languages <span class="math-container">$L$</span> for which, for each <span class="math-container">$\varepsilon \in 2^{-O(\mathop{\mathrm{poly}} n)}$</span>,
there is <span class="math-container">$g \in \mathsf{GapP}$</span> and <span class="math-container">$f \in \mathsf{FP}$</span>,
such that</p>
<ul>
<li>for <span class="math-container">$x \notin L$</span> we have <span class="math-container">$0 \leqslant \frac{g(x)}{f(x)} \leqslant \varepsilon$</span> and</li>
<li>for <span class="math-container">$x \in L$</span> we have <span class="math-container">$1-\varepsilon \leqslant \frac{g(x)}{f(x)} \leqslant 1$</span>.</li>
</ul>
</blockquote>
<p>This is a [technical but relatively well-known] upper bound for the class <span class="math-container">$\mathsf{BQP}$</span>. Its relationship to other &quot;gap-defined classes&quot; could be summarised as
<span class="math-container">$$ \mathsf{SPP \subseteq LWPP \subseteq WPP \subseteq AWPP \subseteq PP}, $$</span>
where <span class="math-container">$\mathsf{LWPP}$</span> is notable as a [once more technical but relatively-well known] upper bound on <span class="math-container">$\mathsf{EQP}$</span> (with algebraic coefficients over any constant set), and <span class="math-container">$\mathsf{SPP}$</span> is the gap-definable version of <span class="math-container">$\mathsf{UP}$</span>. Thus all of these contain <span class="math-container">$\mathrm{UNIQUE\text-SAT}$</span>.</p>
<p>By Valiant-Vazirani and the closure of <span class="math-container">$\mathsf{BQP}$</span> under subroutines, if <span class="math-container">$\mathrm{UNIQUE\text-SAT} \in \mathsf{BQP}$</span>, we then have <span class="math-container">$\mathsf{NP \subseteq PH \subseteq BQP}$</span>. We may reasonably consider this to be unlikely, so <span class="math-container">$\mathrm{UNIQUE\text-SAT}$</span> is an easy example of a problem in <span class="math-container">$\mathsf{AWPP}$</span> which one may consider unlikely to be in <span class="math-container">$\mathsf{BQP}$</span> (albeit a problem which belongs to classes which &quot;seem much smaller&quot; than <span class="math-container">$\mathsf{AWPP}$</span> as well).</p>
<h2>The relationship of <span class="math-container">$\mathsf{MQ^2}$</span> to <span class="math-container">$\mathsf{BQP}$</span></h2>
<p>The class <span class="math-container">$\mathsf{AWPP}$</span> also upper bounds the following (not generally well-known) class defined by Tušarová [<a href="http://arxiv.org/abs/cs/0507057" rel="nofollow noreferrer">arXiv:cs/0507057</a>]:</p>
<blockquote>
<p><a href="http://arxiv.org/abs/cs/0507057" rel="nofollow noreferrer"><span class="math-container">$\mathsf{MQ^2}$</span></a> is the class of languages <span class="math-container">$L$</span> for which there is</p>
<ul>
<li><p>a [concisely] poly-time computable family <span class="math-container">$\bigl\{ T_n \bigr\}_{n \geqslant 1}$</span> of unitary matrices [<em>i.e.</em> a family of matrices <span class="math-container">$T_n$</span> such that the function <span class="math-container">$(j,k,n) \mapsto \left\langle j \:\!\right\vert \!\!\; T_n \!\!\;\left\vert \:\!k \right\rangle$</span> 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]</p>
</li>
<li><p>a poly-time computable string-valued function <span class="math-container">$I$</span>, and</p>
</li>
<li><p>a poly-time computable predicate <span class="math-container">$\alpha$</span> on strings,</p>
</li>
</ul>
<p>such that <span class="math-container">$\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}$</span>  [the exponent on the <span class="math-container">$T$</span> is significant here].</p>
</blockquote>
<p>(In the definition above, we let <span class="math-container">$L(x) \in \{0,1\}$</span> denote the characteristic function of <span class="math-container">$L$</span>.)</p>
<p>The functions <span class="math-container">$I$</span> and <span class="math-container">$\alpha$</span> 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 <span class="math-container">$\lvert I(x) \rangle$</span> is a standard basis state which could be efficiently computed by deterministic classical computation, and <span class="math-container">$\alpha$</span> serves to deterministically compute whether a possible measurement outcome <span class="math-container">$\lvert c \rangle$</span> is a possible &quot;accepting state&quot; for the problem instance <span class="math-container">$x$</span>.</p>
<p>It is not clear that <span class="math-container">$\mathsf{MQ^2}$</span> is comparable to <span class="math-container">$\mathsf{BQP}$</span>. The operator <span class="math-container">$T$</span> in the definition of <span class="math-container">$\mathsf{MQ^2}$</span> is specified by its coefficients rather than as a tensor network, so Solovay–Kitaev does not suffice to allow <span class="math-container">$\mathsf{BQP}$</span> 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.</p>
<p>The class <span class="math-container">$\mathsf{MQ^2}$</span> 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 <span class="math-container">$\mathsf{MQ^2}$</span> — that of simulating (the square of) an exponentially large matrix with efficiently specifiable coefficients — is in <span class="math-container">$\mathsf{BQP}$</span>, the techniques used to show this may have important implications for quantum circuit synthesis, and may shed light on the question of <span class="math-container">$\mathsf{BQP \mathrel{?\!\!\:=} BPP^{BQNC}}$</span>. Thus, if not unlikely, this result would be quite interesting.</p>

CC BY-SA 3.0
2015-04-17T16:23:16.120Z
@RickyDemer: right, typo in description of $\varepsilon$, will fix.
Niel de Beaudrap
CC BY-SA 3.0
2015-04-17T20:07:58.580Z
@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
CC BY-SA 3.0
2015-04-17T08:50:59.533Z
2015-04-17T16:44:34.123Z
2020-06-17T09:38:08.363Z
Niel de Beaudrap
<p>Is there any known problem which is in $\mathsf{AWPP}$ but conjectured to be not in $\mathsf{BQP}$? What about relative to an oracle?</p>

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

CC BY-SA 3.0
2011-05-31T10:55:06.173Z
Could you please define MQ²?
Martin Schwarz
CC BY-SA 3.0
2011-05-31T21:33:07.480Z
As well as AWPP ?
Suresh Venkat
CC BY-SA 3.0
2011-06-01T03:44:00.610Z
$\mathsf{AWPP}$ can be founded in the [complexity zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#awpp). $\mathsf{MQ^2}$ is defined in [this paper](http://arxiv.org/PS_cache/cs/pdf/0507/0507057v1.pdf).
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-06T03:00:28.807Z
Wouldn't it be any NP-Complete problems?
Joshua Herman
<cc.complexity-theory><complexity-classes><quantum-computing>
Is there any problem which is in AWPP but conjectured to be not in BQP?
Quantum Physicist
# Is there any problem which is in AWPP but conjectured to be not in BQP?

(Asked by: username_0 on 2011-05-31)

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

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing
> **Comments:**
> **username_1**: Could you please define MQ²?  
> **username_2**: As well as AWPP ?  
> **username_3**: $\mathsf{AWPP}$ can be founded in the [complexity zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#awpp). $\mathsf{MQ^2}$ is defined in [this paper](http://arxiv.org/PS_cache/cs/pdf/0507/0507057v1.pdf).  
> **username_4**: Wouldn't it be any NP-Complete problems?  

---

## 1 answers

### Answer by username_5 on 2015-04-17. Score: 4

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

> [$\mathsf{AWPP}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#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](http://arxiv.org/abs/cs/0507057)]:

> [$\mathsf{MQ^2}$](http://arxiv.org/abs/cs/0507057) 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.

> **Comments:**
> **username_5**: @RickyDemer: right, typo in description of $\varepsilon$, will fix.  
> **username_5**: @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.  

---

