In the paper Strength and Weakneses of Quantum Computers (https://arxiv.org/abs/quant-ph/9701001) by Bennet, Bernstein, Brassard and Vazirani, it is shown the statement in the title (Theorem 3.5 in the Arxiv version). I'm confused on the logic of the proof in Theorem 3.5

Given an oracle $A$, define the language $L_A = \{y: \exists x, A(x)=y\}$. It is clear that the language is in $NP^A$. Now, given $T(n)=o(2^{n/2})$, the authors show that a poly time quantum Turing machine gives the wrong answer for $1^n$ with probability at least $\frac{1}{8}$ where the probability is taken over random oracles with fixed answers over bitstrings of length distinct from $n$. I don't understand why proving this is enough for proving the result. In the previous paragraph they mention that they want to show that with probability $1$, $M^A$ running in time $T(n)$ does not accept $L_A$, but I cannot see how the this is implied by the previously mentioned result.


Your Answer

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

Browse other questions tagged or ask your own question.