Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
