| Abstract: |
We use the powerful tools of counting complexity and generic oracles to
help understand the limitations of the complexity of quantum computation. We show several
results for the the probabilistic quantum class BQP:
- BQP is low for PP, i.e., PP^BQP=PP.
- There exists a relativized world where P=BQP and the polynomial-time hierarchy is
infinite.
- There exists a relativized world where P=BQP but P <> UP intersect coUP and
one-way functions exist. This gives a relativized answer to an open question of Simon.
|