I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following:

Bernstein and Vazirani [BV97] show that BQP can simulate any deterministic or probabilistic polynomial-time algorithm and Bennett, Brassard, Bernstein and Vazirani [BBBV97] show that $BQP^{BQP} = BQP$. In other words we can do quantum subroutines and build that directly into the quantum computation.

Now, my question what it means by $BQP^{BQP} = BQP$? For example, BQP is given an oracle to BQP, So I don't see any words that can describe it except that it might mean BQP is closed under its running time, so anything that runs in efficient in quantum computing, calls another an efficient quantum algorithm in quantum computing, then it is always in total an efficient in quantum computing. Does this what it means by $BQP^{BQP} = BQP$?

Note that I understand 'oracle' or 'relativized world' from Sipser's textbook, For example: we can have the following: $P^A = NP^A$ given that A is an NP-complete language.

Thank you.


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.