<p>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.</p>

<p>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) .</p>

CC BY-SA 3.0
2013-11-05T13:36:34.167Z
2013-11-05T13:44:21.277Z
2013-11-05T13:44:21.277Z
Mohammad Al-Turkistany
<p>Using quantum computers we can do calculations very fast.</p>

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

CC BY-SA 3.0
2013-11-03T08:59:34.723Z
Related: quantum proofs of classical theorems: http://cstheory.stackexchange.com/questions/8542/quantum-proofs-of-classical-theorems
Suresh Venkat
CC BY-SA 3.0
2013-11-03T14:19:08.113Z
Check this out as well http://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/
Turbo
CC BY-SA 3.0
2013-11-03T14:35:15.657Z
The way it is posed, the question is very vague and, at the best, it should be moved to http://cs.stackexchange.com/
Alessandro Cosentino
CC BY-SA 3.0
2013-11-03T19:45:32.030Z
Please see [about] and [help/on-topic]. Since you are looking from a layman's view this question seems more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2013-11-03T21:40:57.173Z
I agree with @AlessandroCosentino and have voted to close. As written the question is too vague, and doesn't appear to be research level.
Artem Kaznatcheev
<cc.complexity-theory><ds.algorithms><quantum-computing>
Impacts of quantum computing on Theoretical Computer Science
Athiruban
# Impacts of quantum computing on Theoretical Computer Science

(Asked by: username_0 on 2013-11-03)

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.

**Tags:** cc.complexity-theory, ds.algorithms, quantum-computing

> **Comments:**
> **username_1**: Related: quantum proofs of classical theorems: http://cstheory.stackexchange.com/questions/8542/quantum-proofs-of-classical-theorems  
> **username_2**: Check this out as well http://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/  
> **username_3**: The way it is posed, the question is very vague and, at the best, it should be moved to http://cs.stackexchange.com/  
> **username_4**: Please see [about] and [help/on-topic]. Since you are looking from a layman's view this question seems more suitable for [cs.se].  
> **username_5**: I agree with @AlessandroCosentino and have voted to close. As written the question is too vague, and doesn't appear to be research level.  

---

## 1 answers

### Answer by username_6 on 2013-11-05. Score: 0

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) .


---

