Given the fact that the qbits have superpositions, and have more representational power compared to circuits, are there any problems that require at least exponential time to guarantee a solution with a quantum computer?
I've checked the Complexity Zoo and couldn't find any complexity class mentioned there that fits this description.
Most problems that require exponential time on a classical computer also require exponential time on a quantum computer. For example EXPTIME-complete problems will require exponential time on either a classical or a quantum computer.
The class of problems solvable in polynomial time on a quantum computer is called BQP. It is believed unlikely that BQP contains the NP-complete problems. Thus the NP-complete problems probably take exponential time on quantum computers.
One of the most interesting problems that is known to be in BQP, but believed not to be in P is the integer factoring problem. But integer factoring is believed unlikely to be NP-complete.
