An Inconvenient Truth!
As per the Quantum Strong Church-Turing Thesis (QSCTT): Any ‘reasonable’ model of computation can be efficiently simulated on a quantum computer (QC).
Bounded Quantum Polynomial problems are the class of problems that can be efficiently solved by a QC.
When do you call a problem “hard”?
Loosely speaking, if a computational task is NOT solving a problem in a polynomial time, we can call it a ‘hard’ problem. If a computational problem is efficiently solved, i.e. the cost of computing is minimal, then it is an optimal algorithm.
However, it is not simple to identity them.
Does adding an RNG with a deterministic computer (our digital computer) solve any problem efficiently?
Does a quantum computer outperform a deterministic computer?
No concrete proof yet. Only empirical evidences are available now.
The problem of finding which problems are difficult, appears to be a difficult problem.
Let us assume 3 cases
(a) quantum computers outperform classical computers,
(b) quantum computers & classical computers are equally powerful and
(c)quantum computers are all powerful.
Case (a): If a quantum computer outperforms the classical deterministic computers, then in addition to solving all that classical computers do, it can solve the BQP problems efficiently. However, it cannot solve NP or NP-complete problems such as Traveling Salesman Problem.
Case (b): If the quantum & the classical computers are equally powerful, then there is no need of the expensive quantum version as the existing classical computers will do with powerful algorithms.
Case (c): If quantum computers are all powerful then they can solve all the NP problems.
It is one of the significant open problems highlighting our dearth of knowledge in this field.
