3
$\begingroup$

Using quantum computers we can do calculations very fast.

However from a layman's view, I want to know the impact of quantum computers have on Theoretical computer science.

$\endgroup$
0
$\begingroup$

One major impact is that quantum computing gave us a polynomial time algorithm to solve the integer factoring problem which is not known to be efficiently solvable on classic computers. This partially motivated the development of public key cryptography that does not depend on the hardness of factoring problem.

Efficient quantum algorithm for an NP-complete problem would have the greatest impact on TCS since it would give us insights into the fundamental differences between the computational power of classical and quantum algorithms (assuming classic deterministic algorithms can not solve NP-complete problems in polynomial time) .

$\endgroup$
0
$\begingroup$

In general, there is a classical - quantum computer theory seperation and since the fundamental principles of quantum computer theory differ from the classic approach we have new algorithms and interest for theoretical research on this field.

You can check this too:

https://security.stackexchange.com/questions/25251/impact-of-quantum-computers-other-than-new-algorithms

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.