This is the third in my Quantum Computing series. Last time I indicated that the two main areas in which quantum computers will be very much faster than digital computers are searching and factoring. The average individual and almost every company will rarely need the incredible searching capabilities of a large quantum computer, and I suspect that specialized companies will be created in the next twenty years or so to handle the special cases that do come up.
But everyone should be concerned about a quantum computer’s capability to almost instantaneously factor large numbers. To understand why, we have to understand how encryption is actually done in our digital world. There are two main types of encryption: symmetric-key encryption and public-key encryption.
Symmetric-key encryption uses the same key for both encryption and decryption. Both parties must have the same key in order to communicate securely. We use symmetric-key encryption every day: whenever you see https:// (instead of just http://) in an Internet URL, you are using symmetric-key encryption. Symmetric-key encryption algorithms are subject to various attacks based on the process that generates the symmetric key, but the biggest issue is how to securely transmit the key between the two parties. That key sharing usually involves some form of public-key encryption.
Public-key encryption has two keys: a published key that anyone can use to encrypt messages and a private decryption key that only the receiver has. While the process to generate the pair of keys is mathematically amusing, the key component of the process is to multiply two very large prime numbers together. The public key is that product plus another calculated value based on the two primes that form the product. The security of public-key encryption is based on the time it takes with current digital technology to determine the two prime factors that are used to compute the public and private keys. This factoring time goes up exponentially as the key gets larger, so that today by the time some organization could break a code, the data would be of historical interest only.
However, Peter Shor at MIT has shown that a quantum computer could factor large numbers easily, meaning very quickly. Oops.
Quantum computers could end the predominance of public-key encryption algorithms, which would also seriously impact symmetric-key encryption.
The ideal cryptographic protocol is the “one-time pad,” first described in 1882. A one-time pad is a random secret key that is only used once. It was original an actual pad of paper that contained the key, or more likely a set of keys. The pads were then physically carried from one party to the other, often using clandestine methods. The KGB created one-time pads that could fit inside a walnut shell. Today, most symmetric-key algorithms create a one-time use key in real time for short-term use. For example, https security creates a new key for each communication session. If you are communicating with https to multiple sites at the same time from the same browser, each of those communications has a different symmetric key.
Quantum computing to the rescue: Quantum Key Distribution (QKD) allows for the distribution of completely random keys at a distance solving the biggest security problem with symmetric-key encryption. A key generator creates two entangled qubits (perhaps a photon), and sends one to each party. Each party looks at one attribute of the qubit (say polarity), and assigns a bit (0 or 1) based on the attribute value. Due to entanglement, both parties will get the same answer. Repeating this process can generate a symmetric key of any appropriate length, normally no larger than 256 bits.
More importantly, the parties can tell if anyone intercepted their qubit. If someone does intercept the qubit distribution, that interception will disturb the entanglement and the keys will no longer match. Problem solved.
The last word:
Perhaps one of the strangest potential uses of a quantum computer is to simulate quantum systems. This will allow scientists to understand what is really happen at the quantum level, and could perhaps lead to amazing new products in a variety of areas.
We have no idea what the quantum computer will eventually do. Howard Aiken was a pioneer computer engineer and the original conceptual designer behind the IBM Harvard Mark I computer in 1944. In 1952, he said, “Originally one thought that if there were a half dozen large computers in this country, hidden away in research laboratories, this would take care of all requirements we had throughout the country.”
Keep your sense of humor.