7

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.

Geoffrey Irving
  • 3,253
  • 15
  • 29
  • 3
    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 Jan 26 '21 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 '21 at 20:06

1 Answers1

6

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

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
  • 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 Jan 27 '21 at 20:23