CS502 Fundamentals of Algorithms GDB Solution Spring 2014

Quantum Computing is the theory that can solve all NP classes’ problems in Polynomial Time.” Support or contradict the above statement. Consider all aspects and describe precisely but not more than 100 words.


 There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

The capacity of a quantum computer to accelerate classical algorithms has rigid limits—upper bounds of quantum computation’s complexity. The overwhelming part of classical calculations cannot be accelerated on a quantum computer.A similar fact takes place for particular computational tasks, like the search problem, for which Grover’s algorithm is optimal.

Although quantum computers may be faster than classical computers, those described above can’t solve any problems that classical computers can’t solve, given enough time and memory (however, those amounts might be practically in-feasible).