understand complexity-theory oracles

silky / research_notes

notes on things i want to learn about

MIT License

0 stars 0 forks source link

understand complexity-theory oracles #17

Open silky opened 9 years ago

silky commented 9 years ago

what is the "unrelativized" setting?
why is it hard to seperate BQP and BPP because, as Bernstein and Vazirani say, BPP <= BQP <= P^{#P} ?

silky commented 9 years ago

re the second part, Shor says (in "Algorithms for quantum computation: Discrete logarithm and factoring") that it's because BPP is not known to be strictly smaller than PSPACE, and this would separate them.