The following is a transcript of an answer that I posted on Stack Overflow in response to the question:
I read a while back that quantum computers can break most types of hashing and encryption in use today in a very short amount of time (I believe it was mere minutes). How is it possible? I’ve tried reading articles about it but I get lost at the “a quantum bit can be 1, 0, or something else”. Can someone explain how this relates to cracking such algorithms in plain English without all the fancy maths?
What’s a quantum computer?
Quantum computers are strange beasts that we really haven’t yet tamed to the point we can make them useful in the real world. The theory that underpins them is very mathematical and somewhat abstract, so any discussion of how quantum computers can be more efficient than classical ones will inevitably be long and involved. You’ll need at least an undergraduate understanding of linear algebra and quantum mechanics to understand the details, but nonetheless I’ll try to convey my limited understanding!
The basic premise of quantum computation is quantum superposition. The idea is that a quantum system (such as a quantum bit, or qubit, the quantum analogue of a normal bit) can exist not only in the 0 and 1 states (called the computational basis states of the system), but also in any combination of the two (so that each has an amplitude associated with it). When the system is observed by someone, the qubit’s state collapses into one of its basis states. You may have heard of the Schrödinger’s cat thought experiment, which is related to this.
Because of this, a register of n qubits has 2^n basis states of its own — these are the states that you could observe the register being in; imagine a classical n-bit integer. Since the register can exist in a superposition of all these states at once, it is possible to apply a computation to all 2^n register states rather than just one of them. This is called quantum parallelism.
Given this property of quantum computers, it may seem like they’re a silver bullet that can solve any problem 2^n times faster than a classical computer. But it’s not that simple: the problem is that once you observe the result of your computation, it collapses (as I mentioned above) into the result of just one of the computations and you lose all of the others.
The field of quantum computation/algorithms is all about trying work around this problem by manipulating quantum phenomena to extract information in fewer operations than would be possible on a classical computer. It turns out that it’s very difficult to contrive a “quantum algorithm” that is faster than any possible classical counterpart.
The example you ask about is that of quantum cryptanalysis. It’s thought that quantum computers might be able to “break” certain ciphers: specifically, asymmetric ciphers such as RSA, which relies on the difficulty of finding the prime factors of very large integers. In particular, Shor’s algorithm can factor integers with polynomial time complexity. By contrast, the best classical algorithm for the problem has (almost) exponential time complexity, and the problem is hence considered “intractable“.
Quantum superposition
To better understand the idea of quantum superposition, think in terms of probabilities. Imagine that you flip a coin and catch it on your hand, covered so that you can’t see it. As a very tenuous analogy, the coin can be thought of as being in a superposition of the heads and tails “states”: each one has a probability of 0.5 (and, naturally, since there are two states, these probabilities add up to 1). When you take your hand away and observe the coin directly, it collapses into either the heads state or the tails state, and so the probability of this state becomes 1, while the other becomes 0. One way to think about it, I suppose, is a set of scales that is balanced until observation, at which point it tips to one side as our knowledge of the system increases and one state becomes the “real” state.
Of course, we don’t think of the coin as a quantum system: for all practical purposes, the coin has a definite state, even if we can’t see it. For genuine quantum systems, however (such as an individual particle trapped in a box), we can’t think about it in this way. Under quantum mechanics, the particle fundamentally has no definite position (disclaimer: this actually depends on the interpretation to which you subscribe), but exists in all possible positions at once. Only upon observation does it take a specific position (though this opens up another can of worms), and even this is purely random and determined only by probability.
By the way, quantum systems are not restricted to having just two observable states (those that do are called two-level systems). Some have a large but finite number, some have a countably infinite number (such as a “particle in a box” or a harmonic oscillator), and some even have an uncountably infinite number (such as a free particle‘s position, which isn’t constrained to individual points in space).