Questions tagged [bbbv]

For questions related to the theorem of Bennettl, Bernstein, Brassard, and Vazirani, which states that, relative to a random oracle, a quantum computer can achieve, at best, a quadratic speedup over a classical computer.

Filter by
Sorted by
Tagged with
4 votes
1 answer

Can we efficiently run HHL on a computational basis state without violating the BBBV theorem?

Recall that the linear systems algorithm of Harrow, Hassidim, and Lloyd purports to find a quantum state $|x\rangle$ proportional to $\vec x$, where $\vec x$ satisfies $A\vec x=\vec b$. In addition ...
Mark Spinelli's user avatar
5 votes
1 answer

Proof using hybrid method that inverting a permutation requires exponential queries for BQP machines

Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(000\cdots1)$ is even and $0$ if $\sigma^{-1}(000\cdots1)$ is odd. It can ...
BlackHat18's user avatar
  • 1,313