<p>The best quantum algorithm for QBF on n variable formulas of size s runs in about <span class="math-container">$2^{n/2}poly(s)$</span> steps, regardless of quantifier alternations. This is due to a series of advances on quantum algorithms for game tree search in the early 2000s.</p>
<p>Here is the first reference I found from googling; there are more: <a href="https://arxiv.org/abs/0907.1623" rel="noreferrer">https://arxiv.org/abs/0907.1623</a></p>

CC BY-SA 4.0
2021-01-27T20:23:44.637Z
Thank you!  I'm also curious about the case where heuristics are available, which I tried to formalize in a followup: https://cstheory.stackexchange.com/questions/48270/quantum-complexity-of-tqbf-with-an-untrusted-oracle.
Geoffrey Irving
CC BY-SA 4.0
2021-01-27T02:40:15.300Z
2021-01-27T02:40:15.300Z
Ryan Williams
<p>There is no classical algorithm for <span class="math-container">$n$</span>-bit TQBF with better than <span class="math-container">$O(2^n)$</span> complexity.  Is that also the best known bound for quantum algorithms / circuits?</p>
<p><strong>Edit:</strong> As pointed out by Huck Bennett, in the full alternation subset of TQBF we can in fact beat <span class="math-container">$O(2^n)$</span> via randomized tree search.  This is the case I care about most, so I would also be curious for the best exponent for a quantum algorithm if there are all <span class="math-container">$n-1$</span> quantifier flips.</p>

CC BY-SA 4.0
2021-01-26T16:42:13.880Z
I would be surprised if you can't get some speedup. Intuition: If you have no quantifier alternations you can get a $2^{n/2}$-time quantum algorithm via Grover, and if you have $n-1$ quantifier alternations you can get a $2^{0.793n}$-time classical algorithm, as noted in https://cstheory.stackexchange.com/a/5337/969. So it seems likely that there's a way to interpolate between the two regimes (although of course maybe this intuition is wrong).
Huck Bennett
CC BY-SA 4.0
2021-01-26T20:06:53.827Z
Ah, very true, I was momentarily forgetting that alpha/beta works even in the worst case.  I’m most curious about the full-alternation case, so I’ll edit appropriately.
Geoffrey Irving
<quantum-computing><pspace>
Quantum complexity of TQBF
Geoffrey Irving
# Quantum complexity of TQBF

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

There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity. Is that also the best known bound for quantum algorithms / circuits?

**Edit:** As pointed out by Huck Bennett, in the full alternation subset of TQBF we can in fact beat $O(2^n)$ via randomized tree search. This is the case I care about most, so I would also be curious for the best exponent for a quantum algorithm if there are all $n-1$ quantifier flips.

**Tags:** quantum-computing, pspace
> **Comments:**
> **username_1**: I would be surprised if you can't get some speedup. Intuition: If you have no quantifier alternations you can get a $2^{n/2}$-time quantum algorithm via Grover, and if you have $n-1$ quantifier alternations you can get a $2^{0.793n}$-time classical algorithm, as noted in https://cstheory.stackexchange.com/a/5337/969. So it seems likely that there's a way to interpolate between the two regimes (although of course maybe this intuition is wrong).  
> **username_0**: Ah, very true, I was momentarily forgetting that alpha/beta works even in the worst case.  I’m most curious about the full-alternation case, so I’ll edit appropriately.  

---

## 1 answers

### Answer by username_2 on 2021-01-27. Score: 6 | Accepted answer

The best quantum algorithm for QBF on n variable formulas of size s runs in about $2^{n/2}poly(s)$ steps, regardless of quantifier alternations. This is due to a series of advances on quantum algorithms for game tree search in the early 2000s.

Here is the first reference I found from googling; there are more: <https://arxiv.org/abs/0907.1623>

> **Comments:**
> **username_0**: Thank you!  I'm also curious about the case where heuristics are available, which I tried to formalize in a followup: https://cstheory.stackexchange.com/questions/48270/quantum-complexity-of-tqbf-with-an-untrusted-oracle.  

---

