When large scale quantum computers come along, algorithms based off of the new principles will have an impact on how we encrypt data, with Shor's algorithm rendering RSA vulnerable and Grover's algorithm halving the effective keysizes for AES.

What I'm wondering is how having an actual quantum computer will affect the computation thereafter.

Using Grover's algorithm, AES-256 will be rendered as secure as AES-128 is today. But will a quantum computer be able to search that new space substantially quicker too? As such, would we need to more than double keysizes as a defence?

  • A day when fiddling goofy small potatoes stuff like factoring primes is no longer useful for encrypting data. Dec 11, 2012 at 0:38
  • If Quantum computers can solve the above problems, people will eventually come up with MORE problems that CAN be achieved with a Quantum computer, but CANNOT be solved by a quantum computer.
    – sudhacker
    Dec 11, 2012 at 1:56

3 Answers 3


The thing with quantum computing is that we don't know yet.

A few thoughts:

  • If we do ever achieve a true quantum computer, it is likely to be significantly faster than classical computers, when speed is measured in a similar way.
  • If it is going to be faster, we don't know how much faster until we build one. Current prototypes are far from complete, and even "landmark" demonstrations of the technology are questionable.
  • Quantum computing offers a potential short-cut for certain operations, in that it can use various forms of quantum mechanics trickery to produce previously "unknowable" results out of input values.
  • However, quantum results are probabilistic; it's not actually as concrete as saying "it's fast", because you have to make it fast and right. Not easy to do.
  • If you can find a quantum short-cut to a problem, and build a quantum computer, and implement that short-cut within the computer, and find a way to get it the result with p>0.5, you're on track.
  • The big "potential" is for Shor's algorithm, which might reduce the computational complexity of semiprime factoring to a low enough class for us to feasibly factor very large numbers in a shorter time than with classical algorithms.
  • It's a big "if". We don't know if it'll actually reduce computational complexity, nor do we know if an efficient implementation is possible. Even if we can achieve both of those, we don't know how much of a reduction in complexity we will get. The hope is that we'll get O((log N)3), but we don't actually know if we can ever reach that in a real implementation. And even if that is the case, it still requires massive amount of computation, which brings us back to the second point I made: we don't know how fast quantum computers can really be.
  • Even we break semiprime factoring problems like RSA, quantum crypto brings new problems that can't be solved easily, which means we'll still have a new way to keep things secure.

I did not fully understand your question, but I will give it a try. As far as I remember, that quantum computer will allow you to efficiently solve a class of problem that is BQP (by the current knowledge factoring is in BQP), which is larger than P, but does not consist all NP. So they will not allow you to solve NP efficiently.

Grovers algorithm will give a sqrt(n) speedup for NP-complete problems. So if you had 2^n states, by applying Grovers algorithm you will be able to decrease it to 2^(n/2), which is really good, but still exponential.


There are other algorithms that can be used already. While relative prime factorization is the most commonly used problem for asymmetric cryptography, there are a number of other known problems (which I can't remember off the top of my head at the moment) which do not currently have a known quantum algorithm to solve. So in the short term, if/when quantum computers exist we still have a number of algorithms that are believed to be secure.

The flip side of that is that if they become widespread, we might be able to make use of wide spread quantum cryptography such as Quantum Key Distribution. The basic idea as I understand it is that you can use quantum mechanic principals to guarantee that there is only one transmitter and only one receiver of the information so that it actually becomes physically impossible for an attacker to gain meaningful access to the information since if there were two people reading the data, it would become a garbled mess.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .