**Science** Quantum Computing: The end of privacy?

## New in Ceasefire, Science* - Posted on Thursday, April 21, 2011 0:00 - 2 Comments*

By **Sebastian Meznaric**

Computing with machines has had a very long history, stretching back to antiquity and the use of abacuses. More recently, in the first half of the 20th century, electric computers started an exponential explosion of computing power that has continued to this very day.

Thus, for the past few decades computing power has been doubling every 18 months, meaning a quadrupling every 36 months and so on, an exponential increase better known as *Moore’s law*, named after Gordon Moore, a co-founder of microchip giant Intel, who first predicted it.

All modern computers work according to the same model, known as the Turing machine. A Turing machine is a mathematical model describing every computation that can be done on a typical computer. For this reason it is also known as the *‘Universal Computer’*.

However, it is precisely on this point that quantum computers break with tradition. Indeed, they can execute algorithms that can *not* be run on *any* Turing machine. Many of these algorithms render problems that would take a ‘normal’ computer a very long time to run much easier to solve.

The way quantum computers work is by making use of small particles that obey the laws of quantum mechanics and can thus be in multiple states at the same time. Whereas today’s computers work with transistors that can only adopt the binary values of 0 or 1 (also known as ‘bits’), quantum computers can be in both ‘state 0’ and ‘state 1’ at the same time and to different extents. If we had multiple bits, then on a classical (normal) computer they could, for example, be in a state such as 01101110. On a quantum computer, however, they could be in a superposition of states, 011100011 *and* 011110010 for instance. Multiple bits being combined in such ‘superpositions’ is a concept also known as ‘entanglement’.

These superpositions are essential to new types of algorithms. As an example, consider that you are given a table with a large number *n* of entries and you needed to find a particular entry. You would have to go through each of these entries until you find the one you are looking for – and this is exactly what a classical computer would do. It would therefore take an average of n/2 steps to find a particular entry.

A quantum computer, however, would construct a superposition of all entries in the database, and then operate on these elements. It would then perform a measurement which, after several runs, would give as the result the searched-for element within the database. It would on average only require *√n* steps to find the result. This algorithm is known as the ‘Grover’s search’ algorithm. No classical algorithm can achieve this.

However, quantum computers could also be dangerous. Most modern encryption methods rely on the principle that factoring large numbers is very difficult. Thus, if one could factor numbers quickly communications that are considered secure today would suddenly cease to be so. Yet this is exactly what quantum computers are able to do.

Communication between you and your bank, between intelligence agencies or activist networks, and pretty much any hitherto secured confidential information would suddenly become accessible to anyone with a quantum computer.

The implications of this are immense, not to mention that the time it will take us to transition to a new kind of encryption would be long enough that for months, possibly years, there would be essentially no secure method of communication anywhere in the world. Period.

In fact, it now seems we may be on the brink of exactly such an encryption-beating machine. The major obstacle so far in constructing a quantum computer has been that quantum states are very, very delicate. Any form of interaction with the environment can disturb them and make them unusable. To make matters worse, the more of these states we have together, the quicker they become unusable – a phenomenon known as ‘decoherence’ (‘coherence’ is another name for superposition).

A team in California has now announced, however, that they may be able to turn some of these interactions off almost completely. UCSB’s John Martinis said this to BBC News: “It’s a problem I’ve been thinking about for three or four years now, how to turn off the interactions. Now we’ve solved it, and that’s great – but there’s many other things we have to do.” The solution to this problem had evaded researchers for more than a decade, and so, unsurprisingly, the research effort conducted by Prof Martinis’s group has been named as the breakthrough of the year by the journal Science.

If their method of turning these interactions off really turns out to be as comprehensive as it is currently believed then we may finally be on the verge of constructing these powerful computers. However, don’t go throwing your Intel or AMD away just yet. They are still likely to be useful in conjunction with quantum devices for many years to come.

**Sebastian Meznaric** is a theoretical physicist and doctoral reseracher at the University of Oxford. His areas of interests include the study of information theory in quantum mechanics. He is also a keen observer of politics and current affairs.

*For those who would like more details, the original article can be found here* (Unfortunately, access to the journal is required to view it)

# 2 Comments

Andy

The rise or fall of encryption systems is a double-edged sword for capital and the state – while they’re obviously hoping it can be used to spy on dissidents, “criminals” and so on, an end to secure encryption might also end e-commerce and prevent governments storing/transmitting ‘classified’ data. I’d guess the NSA’s hope is to be the first ones with quantum computers, giving them a temporary advantage. Very temporary since at the very least other states would have them soon after.

However, if I understand rightly it only affects RSA encryption? There’s about five other methods already available which will be unaffected (e.g. code-, hash-, lattice-based), several others (such as entanglement and quantum keys) which are in development, plus a message with a key longer than the message is undecryptable in principle – is this right? If this is right then it’s not so much that it will stop future encryption as that it will allow ‘backdated’ decrypting of whatever the NSA or whoever have managed to intercept, but not decrypt, up until now.

Thanks for the article, it actually serves as a very useful introduction to quantum computing – you did well to describe it in such accessible terms!

Will be very interesting to see where privacy goes. MD5 encryption, which is used to store our passwords on most of these websites, has already been ‘cracked’ without the use of quantum computing.

One could argue that the new technology will bring with it improved methods of security – depending of course who’s hands it’s in. If the open source community is involved, there could well be a strengthening of existing systems rather than huge vulnerability.