7
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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). $\endgroup$
    – Huck Bennett
    Jan 26, 2021 at 16:42
  • $\begingroup$ 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. $\endgroup$
    – Geoffrey Irving
    Jan 26, 2021 at 20:06

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.