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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.