11 November 2015, by Chris Arnott
How do they work?
Hopefully you are already familiar with the fundamentals of a classical computer. You take a load of 1’s and 0’s and combine them using logic gates to do calculations, represent data, etc. Quantum computers take quantum states and use quantum gates to act upon the data. The result can then be read to generate a classical value.
The difference between a normal bit (1 or 0) and a quantum bit, is that the quantum bit is a superposition of both 1 and 0 at the same time. When reading the value of a quantum bit there’s a possibility of getting either 1 or 0, with certain probabilities. It follows from this that classical states are also quantum states, where the probabilities are 1 and 0 of each of the two states.
Why is this useful? Well, if you consider a simple function
f(x), in a classical system, if you want to find out if
f(0) = f(1), you will need to put both 1 and 0 into the function, measure the output and see if they are the same. However, in a quantum system, x can be a superposition of both 0 and 1. This means that the output of the gate can indicate whether the
f(0) = f(1) from only one application of the function. The proof of this is Deutsh’s Algorithm, which is well worth reading about further if you would like to learn more about this.
What can they do?
The above is great, but what practical applications does this have? Well, it turns out there are certain classes of problems that quantum computers are able to solve more quickly than classical problems.
- Deutsh’s Algorithm (above)
- Period finding. Which is the ability to to find the period,
a, of a periodic function – one that satisfies
f(x) = f(x+a)
- Shor’s Algorithm. Which is the ability to find factors of a non-prime integer.
Those of you who are up to date on your security algorithms will know that RSA encryption is based on how hard it is to find factors of large non-primes. This means that a quantum computer would be able to break many modern security systems. Fortunately, the dawn of any quantum age will result in new techniques of security, so all is not lost.
An interesting story of note is that recently security experts have been warning about “Capture now, decrypt later“. This is a method where hackers capture encrypted traffic today, and intend on decrypting it years later when decryption time will be much faster.
Where can I get one?
While technically available, you’ll need a great deal of money, as commercial quantum computers are expensive. In order to build a quantum computer, you need large entangled states (for your input), states that do not interact with the environment (to reduce noise in the computations) and the ability to manipulate and measure individual systems. Common methods for achieving this are:
- Ion traps, which use electron energy levels as the quantum bits. The downside of this method is that interaction between atoms is difficult to control and slow.
- Linear optics, which use polarization (or position) of photons. Unfortunately, it is difficult to generate single photons and detectors often struggle to measure such low levels of light (which can distort results).
- Atoms in an optical lattice, which uses sublevels of neutral atoms as quantum bits. The difficulty of this method is measuring individual quantum bits.
If you really do want to get a quantum computer without doing this yourself, D-Wave might be able to sell you one. The D-Wave Two has 512 qbits, but can only solve very specific quantum problems.
When discussing the abilities of quantum computers, I mentioned that they break many common security practices. Fortunately all is not lost; quantum computers are designed to solve very specific problems, and many brilliant security researchers have come up with alternative methods of keeping our data safe that they can’t break.
The core idea is to make a problem that’s difficult to solve for both classical and quantum computers, for example:
- Lattice based cryptography uses a sequence of points in a high dimensional space. A message is then represented by the distance to one of those points. This is difficult to calculate unless you have the required secret key.
- McEliece encryption uses vectors to encrypt messages with intentional errors. The decryption algorithm then uses the inverse of parts of the public key to correct the errors inserted and calculate the message that was encrypted.
Has this piqued your interest in post-quantum encryption? If you’re interested to learn more, a good place to start would be investigating the options listed on wikipedia.