Today’s encryption techniques will be no match for quantum computers.
Around the world, scientists are developing a new breed of computer so powerful that it could solve problems in a few days that would take today’s machines billions of years. Quantum computers could revolutionise our society and bring many benefits, such as new life saving medical treatments and capabilities that will transform industry sectors.
But they also pose a significant threat to all of today’s encrypted information, from bank transactions to nuclear codes. Most of the information we want to keep secret is encrypted using mathematical problems that seem hard for conventional computers, such as factoring. But these just happen to be problems that quantum computers will be very good at. My colleague Natalie Fratto recently explained that ‘Quantum computers will affect the security of the entire finance and banking industry’.
To give an idea of exactly how powerful these machines are likely to be, imagine you were searching for a certain phrase in a library of a trillion trillion books. Dr Jonathan Barrett, Associate Professor of Computer Science at Oxford University, explains that if you make some reasonable assumptions about the speed of operation, a quantum computer could find the phrase in 116 days, while it would take a classical computer, 158 billion years.
Building quantum computers
Over the last 50 years we have seen the impact of Moore’s Law (a doubling of the number of transistors on a chip approximately every two years) that has led to an almost unthinkable scaling of classical computing. However, a transistor is now so small (the smallest are around 1/1000th the width of a human hair) that many experts believe we are approaching the physical limit of Moore’s Law and, therefore, our ability to build more powerful classical computers.
Quantum computing is fundamentally different in two ways. First, it removes the binary processing limitations of classical computing (i.e. 0 or 1) enabling us to compute over continuous variables (i.e. any number or fraction of a number).
Second, classical computers are limited by the way they scale. For every transistor you add to a chip, you get an equivalent increase in performance. For example; if you add a single transistor to a chip containing 100 transistors, you get a processing power improvement of one percent. Whereas every qubit you add to a quantum system doubles the performance. This exponential scaling is the power of quantum computing and enables the processing of incredible amounts of data and the ability to compute things that are simply impossible with any current or future classical computer.
Nobody is certain when the first large scale quantum computer will begin operating and organisations ranging from universities to Google, Microsoft and IBM are all developing the technology. But Professor Winfried Hensinger, who leads a project to build one of the first ones, at the University of Sussex, is developing an approach that may allow the construction of such a machine in the next five to 10 years.
However, quantum computing is expected to evolve slowly, and it could still be many years before its codebreaking abilities are fully realised. It’s a completely new kind of machine based on quantum effects such as ‘superposition’ – the fact that objects at the level of atoms and molecules can be in two places at once – and the complexities mean it will take time to perfect.
Nevertheless, the prospect of such processing power becoming a reality, and the danger of encrypted information with long-term significance being collected now and decoded when the machines are ready, has added urgency to the search for new encryption methods.
In fact, quantum cryptography systems, which could lock out quantum computers, already exist. They aren’t based on difficult mathematical problems at all, but instead involve a single photon – a tiny particle of light – containing information. Quantum theory means the photon would be impossible to tamper with, without being noticed immediately.
Dr Barrett explains: “You do need special quantum hardware to send quantum encrypted messages and it may just not be practical to deploy it in every single circumstance where we want security. For example, we can do internet banking on our phones and they encrypt everything in the usual classical way. But it’s going to be quite some time before everyone has special quantum hardware in their office, in their phone and at home.
“So although there is a solution involving quantum cryptography it’s not clear that it’s practical enough because of this need for special hardware to be deployed absolutely everywhere for every situation that we might want it.”
Some researchers are working on an alternative that would involve developing a new kind of classical cryptography that isn’t based on factorisation, or related problems, but on a new mathematical question that even a quantum computer isn’t likely to solve. However, it’s unclear whether quantum algorithms could be developed in future to solve even this new problem.
The need for a workable solution will become increasingly urgent over the next few years as quantum computing comes every closer and begins to present real-world cyber security issues.