patternModerate
Are there any problems that require exponential time in quantum computing?
Viewed 0 times
areexponentialanyproblemstimethatrequiretherecomputingquantum
Problem
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.
I've checked the Complexity Zoo and couldn't find any complexity class mentioned there that fits this description.
Solution
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.
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.
Context
StackExchange Computer Science Q#51469, answer score: 12
Revisions (0)
No revisions yet.