Questions tagged [forrelation]

For questions related to the "forrelation" problem - given boolean functions f and g, is f correlated with the Fourier transform of g?

Filter by
Sorted by
Tagged with
4 votes
0 answers

Bound on quantum speedups under various models of complexity

What are the bounds on quantum speedups under the various models of complexity? How big or small can they be? Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as ...
user avatar
  • 1,034
3 votes
1 answer

BQP and PH separation

I was reading the Quanta article here which shows that there exists a problem which achieves "oracle separation between BQP and PH". In simple terms, there exists a problem which a quantum ...
user avatar
  • 2,139
8 votes
0 answers

Is there a BQP algorithm for each level of the polynomial hierarchy PH?

This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit naturally into the polynomial hierarchy $\mathrm{PH}$; I'm ...
user avatar
  • 7,454