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$

closed as off-topic by Artem Kaznatcheev, David Eppstein, Vijay D, András Salamon, Kaveh Nov 8 '13 at 19:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Artem Kaznatcheev, David Eppstein, Vijay D, András Salamon, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

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.