Evidence for Quantum Computers to violate Strong Church-Turning Thesis
- Quantum computers can efficiently factor numbers (Shor’s Algorithm). Factoring is in Class NP for classical computers.
- Random Circuit Sampling is believed to be hard for classical computers but quantum computers can do this easily.
- Boson sampling is theoretically, easy for a quantum device to perform, while hard for a classical device.
In each of the above examples, quantum computers are exponentially faster than the best known classical algorithms. This suggests that quantum computers can efficiently solve problems that are intractable for classical computers or Turing machines, and so quantum computers may overturn the Strong Church-Turing Thesis. These are not proofs, however, because the difficulty for classical computers is not yet proven.