# Quantum complexity of TQBF

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.

• 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 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 Jan 26 at 16:42
• 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 Jan 26 at 20:06

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.