<p>This question is more complicated to state than its predecessor <a href="https://cstheory.stackexchange.com/questions/48253/quantum-complexity-of-tqbf">Quantum complexity of TBQF</a>, but in hindsight it is also way easier to answer.</p>
<p><strong>Theorem:</strong> The complexity is <span class="math-container">$\tilde{O}\left(2^{n/4}\right)$</span>, using a single call to Grover's algorithm to check if there is a path falsifying the oracle.  Moreover, this is optimal in the black box case.</p>
<p>Consider a TBQF query <span class="math-container">$F = \exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots f(x, y)$</span>.  Assume w.l.o.g. that the oracle says <span class="math-container">$F$</span> is true.  The oracle is telling the truth about <span class="math-container">$F$</span> if, when we use the oracle to choose how to play each <span class="math-container">$x_k$</span> move, there is no choice of <span class="math-container">$y$</span>'s that falsifies the oracle.  But this is just a single call to Grover to search through the space of such <span class="math-container">$y$</span>'s.  There are <span class="math-container">$2^{n/2}$</span> <span class="math-container">$y$</span>'s, so the complexity is <span class="math-container">$\tilde{O}\left(\sqrt{2^{n/2}}\right) = \tilde{O}\left(2^{n/4}\right)$</span>.</p>
<p>For the black box lower bound, given a black box boolean function <span class="math-container">$f(y)$</span> defined on <span class="math-container">$n/2$</span> bits <span class="math-container">$y$</span>, we can construct a degenerate TBQF formula <span class="math-container">$F = \exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots f(y)$</span> which simply ignores <span class="math-container">$x$</span>.</p>
<p>(Thanks to Paul Christiano for discussion.)</p>

CC BY-SA 4.0
2021-01-31T10:15:13.170Z
2021-01-31T10:57:10.687Z
2021-01-31T10:57:10.687Z
Geoffrey Irving
<p>This is a follow up to <a href="https://cstheory.stackexchange.com/questions/48253/quantum-complexity-of-tqbf">Quantum complexity of TQBF</a>, trying to model the situation where we have good heuristics.</p>
<p>Let <span class="math-container">$L$</span> be the language of true, fully alternating totally quantified boolean formulas with some number <span class="math-container">$n$</span> of variables and circuit size <span class="math-container">$s = \operatorname{poly}(n)$</span>.  The <a href="https://cstheory.stackexchange.com/questions/5323/are-pspace-complete-problems-inherently-less-tractable-than-np-complete-prob/5337#5337">classical complexity</a> of <span class="math-container">$L$</span> is <span class="math-container">$\tilde{O}\left(2^{0.793n}\right)$</span>, and the <a href="https://cstheory.stackexchange.com/a/48262/13245">quantum complexity</a> is <span class="math-container">$\tilde{O}\left(2^{n/2}\right)$</span>.</p>
<p>Now we assume we have access to an untrusted oracle for all subnodes of a particular formula <span class="math-container">$F \in L$</span>.  That is, if the oracle is honest it will give the correct value of <span class="math-container">$F$</span> where any prefix of quantified variables is replaced by a chosen assignment of <span class="math-container">$\{0,1\}$</span> values.  We seek an algorithm which is correct for all oracles, untrustworthy or not, and ask for its worst-case complexity conditional on the oracle being honest.</p>
<p>In the classical case, I believe alpha-beta pruning is the optimal algorithm, and achieves complexity roughly <span class="math-container">$\tilde{O}\left(2^{n/2}\right)$</span>.  (I'm not certain of this, so confirmation would be appreciated.)  Note that this matches the quantum complexity if we don't have an oracle.</p>
<p><strong>Question</strong>: What is the quantum complexity of <span class="math-container">$L$</span> given an untrusted oracle, where complexity is measured conditional on the oracle being honest?</p>
<p><strong>Motivation</strong>: The goal here is to model the situation where we have some particular TQBF, such as arising from chess or go, where there is enough structure that efficient, accurate heuristics are available but not enough structure to turn those heuristics into a rigorous proof of the game value.  In practice the heuristics would not be perfect (as in the honest oracle case), so this question is trying to get at a lower bound for the practical situation.</p>

<quantum-computing><interactive-proofs><pspace>
Quantum complexity of TQBF with an untrusted oracle
Geoffrey Irving
# Quantum complexity of TQBF with an untrusted oracle

(Asked by: username_0 on 2021-01-27)

This is a follow up to [Quantum complexity of TQBF](https://cstheory.stackexchange.com/questions/48253/quantum-complexity-of-tqbf), trying to model the situation where we have good heuristics.

Let $L$ be the language of true, fully alternating totally quantified boolean formulas with some number $n$ of variables and circuit size $s = \operatorname{poly}(n)$. The [classical complexity](https://cstheory.stackexchange.com/questions/5323/are-pspace-complete-problems-inherently-less-tractable-than-np-complete-prob/5337#5337) of $L$ is $\tilde{O}\left(2^{0.793n}\right)$, and the [quantum complexity](https://cstheory.stackexchange.com/a/48262/13245) is $\tilde{O}\left(2^{n/2}\right)$.

Now we assume we have access to an untrusted oracle for all subnodes of a particular formula $F \in L$. That is, if the oracle is honest it will give the correct value of $F$ where any prefix of quantified variables is replaced by a chosen assignment of $\{0,1\}$ values. We seek an algorithm which is correct for all oracles, untrustworthy or not, and ask for its worst-case complexity conditional on the oracle being honest.

In the classical case, I believe alpha-beta pruning is the optimal algorithm, and achieves complexity roughly $\tilde{O}\left(2^{n/2}\right)$. (I'm not certain of this, so confirmation would be appreciated.) Note that this matches the quantum complexity if we don't have an oracle.

**Question**: What is the quantum complexity of $L$ given an untrusted oracle, where complexity is measured conditional on the oracle being honest?

**Motivation**: The goal here is to model the situation where we have some particular TQBF, such as arising from chess or go, where there is enough structure that efficient, accurate heuristics are available but not enough structure to turn those heuristics into a rigorous proof of the game value. In practice the heuristics would not be perfect (as in the honest oracle case), so this question is trying to get at a lower bound for the practical situation.

**Tags:** quantum-computing, interactive-proofs, pspace

---

## 1 answers

### Answer by username_0 on 2021-01-31. Score: 1 | Accepted answer

This question is more complicated to state than its predecessor [Quantum complexity of TBQF](https://cstheory.stackexchange.com/questions/48253/quantum-complexity-of-tqbf), but in hindsight it is also way easier to answer.

**Theorem:** The complexity is $\tilde{O}\left(2^{n/4}\right)$, using a single call to Grover's algorithm to check if there is a path falsifying the oracle. Moreover, this is optimal in the black box case.

Consider a TBQF query $F = \exists x\_0 \forall y\_0 \exists x\_1 \forall y\_1 \cdots f(x, y)$. Assume w.l.o.g. that the oracle says $F$ is true. The oracle is telling the truth about $F$ if, when we use the oracle to choose how to play each $x\_k$ move, there is no choice of $y$'s that falsifies the oracle. But this is just a single call to Grover to search through the space of such $y$'s. There are $2^{n/2}$ $y$'s, so the complexity is $\tilde{O}\left(\sqrt{2^{n/2}}\right) = \tilde{O}\left(2^{n/4}\right)$.

For the black box lower bound, given a black box boolean function $f(y)$ defined on $n/2$ bits $y$, we can construct a degenerate TBQF formula $F = \exists x\_0 \forall y\_0 \exists x\_1 \forall y\_1 \cdots f(y)$ which simply ignores $x$.

(Thanks to Paul Christiano for discussion.)


---

