3

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.

Athiruban
  • 139
  • 2
  • 2
    Related: quantum proofs of classical theorems: http://cstheory.stackexchange.com/questions/8542/quantum-proofs-of-classical-theorems – Suresh Venkat Nov 03 '13 at 08:59
  • 1
    Check this out as well http://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/ – Turbo Nov 03 '13 at 14:19
  • 4
    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 Nov 03 '13 at 14:35
  • 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 Nov 03 '13 at 19:45
  • 3
    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 Nov 03 '13 at 21:40

2 Answers2

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
0

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

Community
  • 1