4 ms·

Quantum computers are not just super-fast versions of normal computers. They allow the running of some algorithms that normal computers can't physically run. On

Quantum computers are not just super-fast versions of normal computers. They allow the running of some algorithms that normal computers can't physically run. One particularly important algorithm is Shor's algorithm. Shor's algorithm allows quick factorization of primes. RSA encryption, the main way that things are encrypted today, relies on the assumption that factoring large primes is computationally infeasible. So quantum computers would allow the NSA to read RSA-encrypted data.

weinzierl 13y ago
From a computer science standpoint this incorrect. Regarding computability, quantum computers have exactly the same power as traditional computers.
- gizmo686 13y ago
  Regarding computability yes. Regarding time complexity, it is unproven. What we do know is that there is a known algorithm to factor number in polynomial time on quantum computers and there is not a known algorithm to do so on classical computers. Assuming that factoring numbers is actually a hard problem on classical computers (unproven, but generally accepted), then quantum computers are more powerful than classical ones.
- bo1024 13y ago
  I'm not sure what you're referring to; everything in the parent post is correct. You are right that quantum and classical computers have the same "power" in terms of problems that can be solved, but it is also true that quantum computers may be able to computer certain functions faster than classical computers (using faster algorithms that don't run on classical computers).
  - weinzierl 13y ago
    I'm referring to "They allow the running of some algorithms that normal computers can't physically run." I understood this as, it's impossible to run some algorithms on a traditional computer. You can run Shor's algorithm on a Turing machine, albeit requiring a simulation of qbits. You can run it in javascript and in your browser if you like.
    - mtp0101 13y ago
      True, you can simulate the qbits, so the more precise statement would be they can execute some algorithms in a way that classical computers cannot and this gives them superior efficiency in some situations.
    - darth_aardvark 13y ago
      You're right. I should have specified that they can run certain algorithms with a runtime complexity impossible on a classical computer.
- sp332 13y ago
  If you take into account the probability of breaking a given 4,096-bit RSA cipher before the heat death of the universe, it is correct. However this is an implementation detail, and a hardware problem to boot :p
  - Tloewald 13y ago
    Rather mathematical response to a question requesting an answer for non mathematicians ;-) Since Moore's Law is giving us one more bit of decryption per unit time every 1.5 years, 4096 * 1.5 years is probably going to precede the heat death of the universe handily. But 6000-or-so years of Moore's Law does tax credulity.
weavejester 13y ago
It's worth pointing out that other public-key encryption algorithms don't have the same vulnerability to quantum computers. It's also unlikely (but unproven) that quantum computers can solve NP-complete problems.
- jstalin 13y ago
  Such as AES and PGP?
  - mtp0101 13y ago
    AES uses a symmetric key so it is not a public key system
  - damarquis 13y ago
    AES yes, PGP no. Anything based on the difficulty of discrete logs is done for. There are 2 types that remain secure, schemes based on the difficulty of solving problems in lattices and problems in coding theory. Lattice based cryptography is particularly interesting since all known fully homomorphic encryption schemes use it. If this remains the case, and if FHE matures faster than quantum computers (and it actually has been as far as I can tell) that everyone will switch to lattice based cryptography making quantum computers a little less useful and interesting.
  - weavejester 13y ago
    AES is a symmetric encryption algorithm, which is to say it only has one key for both encryption and decryptions. PGP is a piece of software, and not an algorithm. I believe it uses RSA and AES by default, but I could be wrong :) AFAIK RSA, DSA, Diffie-Hellman, and ECC are all known to be vulnerable to Shor's Algorithm (which, granted, do make up a lot of the crypto in common use), but there are lesser-used algorithms like McEliece and NTRU that are not vulnerable. That said, quantum computers are still very far from breaking modern cryptography. We're playing around with a handful of qubits, but to break something like a 4096 bit RSA key would take trillions of quantum gates.
- deleted 13y ago
  [deleted]

weinzierl 13y ago

From a computer science standpoint this incorrect. Regarding computability, quantum computers have exactly the same power as traditional computers.

gizmo686 13y ago
Regarding computability yes. Regarding time complexity, it is unproven. What we do know is that there is a known algorithm to factor number in polynomial time on quantum computers and there is not a known algorithm to do so on classical computers. Assuming that factoring numbers is actually a hard problem on classical computers (unproven, but generally accepted), then quantum computers are more powerful than classical ones.
bo1024 13y ago
I'm not sure what you're referring to; everything in the parent post is correct. You are right that quantum and classical computers have the same "power" in terms of problems that can be solved, but it is also true that quantum computers may be able to computer certain functions faster than classical computers (using faster algorithms that don't run on classical computers).
- weinzierl 13y ago
  I'm referring to "They allow the running of some algorithms that normal computers can't physically run." I understood this as, it's impossible to run some algorithms on a traditional computer. You can run Shor's algorithm on a Turing machine, albeit requiring a simulation of qbits. You can run it in javascript and in your browser if you like.
  - mtp0101 13y ago
    True, you can simulate the qbits, so the more precise statement would be they can execute some algorithms in a way that classical computers cannot and this gives them superior efficiency in some situations.
  - darth_aardvark 13y ago
    You're right. I should have specified that they can run certain algorithms with a runtime complexity impossible on a classical computer.
sp332 13y ago
If you take into account the probability of breaking a given 4,096-bit RSA cipher before the heat death of the universe, it is correct. However this is an implementation detail, and a hardware problem to boot :p
- Tloewald 13y ago
  Rather mathematical response to a question requesting an answer for non mathematicians ;-) Since Moore's Law is giving us one more bit of decryption per unit time every 1.5 years, 4096 * 1.5 years is probably going to precede the heat death of the universe handily. But 6000-or-so years of Moore's Law does tax credulity.

weavejester 13y ago

It's worth pointing out that other public-key encryption algorithms don't have the same vulnerability to quantum computers. It's also unlikely (but unproven) that quantum computers can solve NP-complete problems.

jstalin 13y ago
Such as AES and PGP?
- mtp0101 13y ago
  AES uses a symmetric key so it is not a public key system
- damarquis 13y ago
  AES yes, PGP no. Anything based on the difficulty of discrete logs is done for. There are 2 types that remain secure, schemes based on the difficulty of solving problems in lattices and problems in coding theory. Lattice based cryptography is particularly interesting since all known fully homomorphic encryption schemes use it. If this remains the case, and if FHE matures faster than quantum computers (and it actually has been as far as I can tell) that everyone will switch to lattice based cryptography making quantum computers a little less useful and interesting.
- weavejester 13y ago
  AES is a symmetric encryption algorithm, which is to say it only has one key for both encryption and decryptions. PGP is a piece of software, and not an algorithm. I believe it uses RSA and AES by default, but I could be wrong :) AFAIK RSA, DSA, Diffie-Hellman, and ECC are all known to be vulnerable to Shor's Algorithm (which, granted, do make up a lot of the crypto in common use), but there are lesser-used algorithms like McEliece and NTRU that are not vulnerable. That said, quantum computers are still very far from breaking modern cryptography. We're playing around with a handful of qubits, but to break something like a 4096 bit RSA key would take trillions of quantum gates.
deleted 13y ago
[deleted]