The problems which are calculated, such as finding prime factors of an integer, take non-polynomial (NP) time on a classical computer to solve. But NP problems, as opposed to NP-hard, can by definition be confirm in P (polynomial) time on a classical computer. Therefore, we can easily confirm that the answer is correct using classical computers.
On an aside, I used the example of prime factorization because it is one of the most well known problems that can be accelerated via quantum computing using Shor’s algorithm. Using Shor’s algorithm on a quantum computer, an integer can be factorized in P time. This is opposed to NP time on a classical computer.
One thing bothers me with this… How do we know the results are correct ?
The problems which are calculated, such as finding prime factors of an integer, take non-polynomial (NP) time on a classical computer to solve. But NP problems, as opposed to NP-hard, can by definition be confirm in P (polynomial) time on a classical computer. Therefore, we can easily confirm that the answer is correct using classical computers.
On an aside, I used the example of prime factorization because it is one of the most well known problems that can be accelerated via quantum computing using Shor’s algorithm. Using Shor’s algorithm on a quantum computer, an integer can be factorized in P time. This is opposed to NP time on a classical computer.