Limitations on BQP

Limitations on BQP

• Fortnow and Rogers use simple counting upper bound on BQP to show
  • BQP is low for PP, i.e.
  • PPBQP = PP
  • There exists relativized worlds where
    • P = BQP and PH infinite
    • BQP has no complete sets

Previous slide

Next slide

Back to the first slide

View Graphic Version