Quantum Computing and Counting Complexity 

Interference

Limitations on BQP

Quantum and Classical

Counting Complexity

Valiant and #P

Counting is Hard

GapP Functions

Robust Class

Basic Closure Properties

Example: The Permanent

Advantages of GapP

Simple Quantum Model

Quantum Acceptance

Simulation by GapP

Counting Classes

More Classes

AWPP contains BQP

Properties of AWPP

Corollaries for BQP

Quantum Machines Can Count

Quantum Acceptance

Further Directions