Quantum Computing

by Amit Katwala

  RSA provides a practical method for public-key cryptography, using so-called asymmetric encryption. In public-key cryptography, the instructions for encrypting a message are publicly available, but the information on how to decode that message is kept hidden. It took years for scientists to come up with a way of actually implementing it – but they eventually alighted on a solution in factoring. An individual can create a public key by multiplying two large random prime numbers together. The encoding algorithm on the sender’s device then uses the recipient’s public key to encrypt the message (for instance, by converting the text into binary code and then adding it to the number, although real-world implementations have many more steps).

  So, when you send a WhatsApp message, for instance (the messaging platform uses end-to-end encryption), your phone will first check the recipient’s public key, use that to encrypt your message, and then send the encrypted message to the other person’s phone, which will use the corresponding private key to decrypt it. Decoding the message requires knowing the original prime numbers that were used to create the public key, and those never leave the recipient’s device.

  RSA encryption is virtually unbreakable, as long as it remains difficult to break large numbers down into their primes. But Shor’s algorithm has made that theoretically possible. In December 2018, a report2 by the US National Academies of Sciences, Engineering and Medicine (NAS) estimated that a quantum computer with 2,300 logical qubits could crack a 1,024-bit implementation of RSA encryption in less than 24 hours, using Shor’s algorithm. Other staples of cryptography, such as AES-GCM, are potentially vulnerable to Grover’s algorithm, which can more efficiently search for the correct key from all the possibilities – although again, you’d need a very powerful quantum device to do it.

  When Shor’s and Grover’s algorithms were written in the mid-1990s, the prospect of a quantum computer good enough to run them was a distant possibility. But as well as fuelling funding for research and work into how to build such devices, their discovery also provided enough impetus to kickstart a whole new field of cybersecurity known as post-quantum cryptography.

  There are a number of ways to make encryption algorithms more resistant to quantum attacks. The simplest is to just make the keys harder to break by making them longer – doubling the size of a key squares the number of permutations Grover’s algorithm has to search through to find the correct one. The NAS report suggests that quadrupling the length of a 1,024-bit RSA means you’d need four times as many qubits and 64 times longer to break it. But quantum computers are developing at a rapid pace – so this approach may only buy a little bit of time. So, in 2016, the US National Institute of Standards and Technology (NIST) launched an eight-year competition3 aimed at finding quantum-proof successors to the likes of RSA. It’s thrown up dozens of potential candidates with names like Lizard, Frodo and Falcon, taking a vast array of approaches ranging from lattice-based cryptography to supersingular isogeny key exchange. Generally, it’s about finding new forms of encryption that don’t have the kind of underlying structure quantum computers can take advantage of – which are still exponentially difficult, even for devices with thousands or millions of qubits. ‘We will have to transition to cryptographic standards that are quantum-resistant,’ says Andrea Rocchetto. ‘It will be transformative in this sense.’

  NIST is aiming to have published draft standards for a new encryption algorithm by 2024, and it’s widely expected that companies will begin to roll it out in place of RSA and other vulnerable cryptography in software soon afterwards. That won’t help secure credit card numbers, passwords or government secrets which may have already been stockpiled in the expectation of being broken in future. But by the time a quantum computer good enough to run Shor’s algorithm against RSA encryption actually gets built, there may be nothing new left for it to crack.

  Quantum internet

  In August 2016, China sent the world’s first quantum satellite into space from a launch pad in the Gobi Desert. Micius, which circles the earth at an altitude of 500 kilometres, is a powerful signal of intent – a starting gun for the technological race that could define the next century. Although it remains to be seen whether quantum computers will definitely be able to break new forms of encryption algorithm, scientists aren’t taking a chance. With Micius, Chinese researchers are attempting to use a different type of quantum technology to develop new forms of secure communications that would be completely unbreakable.

  Micius is being used for quantum key distribution, working on the principle that even an all-powerful quantum computer can’t break a key it can’t get access to in the first place. It’s the latest in a long line of research that involves transmitting keys from sender to receiver using photons in a state of quantum superposition, so that it’s impossible to read them without changing what they say. If an attacker tries to intercept, the superposition will collapse into either 1 or 0 – leaving a telltale sign of tampering. With quantum key distribution, the message itself would still be transmitted using normal channels – it’s only the key that would be communicated using quantum technology.

  In theory, this technology could underpin a global network of completely secure communication channels – a quantum internet of uncrackable messages, and a safe haven for governments fearful of Snowden-like leaks (or at least, for governments with enough money to throw at the problem). However, quantum communications face a problem: photons easily get absorbed or deflected by objects in the environment, which means that quantum keys can only be transmitted short distances without extra help. You can’t easily ramp up the power of the signal, because a photon is the smallest possible unit of light – adding more would risk the signal being intercepted by an attacker siphoning off photons using mirrors without you noticing. Traditional communications networks use repeaters at stages along the route to boost the signal by copying it and retransmitting it, but again that doesn’t work for quantum key distribution, because copying the message requires measuring it, which knocks photons out of superposition. Instead, rather than trying to pass on the signal while it’s still in superposition, it’s actually decrypted at each stage before being re-encoded into a new quantum state for the next leg of the journey.

  However, this in turn opens up the seemingly unbreakable system to eavesdropping at the point where the message is unscrambled and re-encrypted. Researchers have been working to develop ‘quantum repeaters’, which would allow the message to remain in superposition while still amplifying it. This technology has been demonstrated in theory, but working prototypes have proved more difficult to get right. It’s also important to note that, just because the message itself is being sent via quantum mechanical means, it doesn’t necessarily mean the entire system is unbreakable.

  Charles Bennett, the IBM researcher whose work was influential in kickstarting the field of quantum cryptography and communications, pointed out a flaw in one of the early physical implementations of quantum key distribution. The cells used to generate the photons in that experiment ran off a power supply that created a faint hum, and that noise changed in volume depending on the voltage being applied. ‘It’s hard for a cryptosystem to be totally secure: you have to be aware of all sorts of possible attacks,’ he told Julian Brown in The Quest for the Quantum Computer. ‘So although you wouldn’t be able to eavesdrop on the photons, you could just listen to the hum to find out what data were going through the system.’

  Those potential flaws haven’t stopped countries, China in particular, making rapid progress on quantum communication. In 2017, it completed a 2,000-kilometre quantum link between Shanghai and Beijing, with 32 stops en route for the signal to be boosted. It’s designed for the secure transmission of government, finance and military information.

  But for truly international quantum networks to be built, a new approach may be needed – and that’s where Micius comes in. Instead of transmitting photons through fibre-optic cables, the satellite beams them through the open air – between the satellite and a
ground station, and then to another ground station. This opens up the possibility of quantum communication over greater distances, although until recently it was limited to transmitting at night due to the excessive interference during daylight hours, which meant that keys had to be built up when it was dark and stored for use during the day.

  In September 2017, scientists set a new record when they used the Micius satellite to hold a quantum-encrypted video call between Chinese and Austrian scientists, over a distance of 7,600 kilometres. It was the first in a number of planned launches for quantum satellites, and a significant step towards building a worldwide ‘quantum internet’. ‘I think we have started a worldwide quantum space race,’ said the project’s lead researcher Jian-Wei Pan when the satellite launched.4

  The ultimate goal for researchers is even more ambitious. While quantum key distribution protects information from being intercepted as it travels, another method being developed means that the information never has to actually travel at all. Quantum teleportation relies on the quantum phenomenon of entanglement, where two photons are linked even if they’re separated by a great distance. By creating entangled pairs of photons – one going to the sender of a message and one to the receiver – quantum teleportation means that a message can be transmitted without any data ever actually being sent. When a message is imprinted onto one of the pair of photons, by allowing it to interact with a ‘memory qubit’ that stores the message being sent, it instantly changes the state of the other photon. The information is effectively ‘teleported’ from sender to receiver. Messages sent in this way would be genuinely, completely unbreakable.

  Quantum hegemony

  Cybersecurity experts live in fear of ‘Q-Day’, or ‘Y2Q’ – the date when a quantum computer is developed that can break most modern cryptographic standards. If one country gets there first, it could cause problems – the CNAS report talks of ‘quantum surprise’, when one country develops technology that others don’t even know about. It’s a race that China is desperate to win. The Chinese government has made quantum the focus of a ‘megaproject’, and set its sights on major breakthroughs in quantum communications and quantum computing. It is reportedly investing $10 billion in building the National Laboratory for Quantum Information Sciences in Hefei. ‘In the last five years, China has invested very heavily in quantum technologies,’ says Rob Young, director of the Lancaster Quantum Technology Centre, and an adjunct professor at the Institute of Fundamental and Frontier Science in Chengdu. ‘It has taken the lead and it has done so relatively quickly.’

  The number of patents filed by Chinese companies relating to quantum computing has shot up in the last few years. In 2014, there were a similar number of patents filed in the United States and China, but by 2017 China filed almost twice as many, according to Patinformatics. China’s quantum ambition has parallels with similar investments in artificial intelligence, and stems partly from a desire to position the country as the technological leader of the decades to come. ‘China basically missed out on the digital revolution, and that really set them and their economy back,’ says Young. ‘It doesn’t want to be caught napping again.’ Jian-Wei Pan agrees. ‘With modern information science, China has been a learner and a follower,’ he says. ‘Now, with quantum technology, if we try our best we can be one of the main players.’ Pan has been dubbed ‘the father of quantum’ by the scientific journal Nature and, along with Snowden, is one of two key individuals behind China’s advances in quantum technology.

  The NSA leaks are the main reason why the bulk of China’s initial progress has been not in quantum computing hardware, but instead in the field of secure quantum communications – through projects such as the Micius satellite, as well as a ground-based quantum network in the northern province of Shandong. ‘In the field of quantum communications we are ahead of our colleagues over the world,’ says Pan, who has said his work was given new impetus and urgency by Snowden’s disclosures.

  Chinese companies such as Tencent, Alibaba and Baidu have also entered the quantum race, but they’re a little late to the party. ‘Some years ago it was quite difficult to convince these e-commerce companies in China to invest in this kind of research,’ says Pan. ‘But, influenced by Google and IBM or Intel and Microsoft, all the Chinese e-commerce companies now have their own quantum technology projects.’

  Chinese efforts can’t yet match the performance of their US rivals in terms of raw number of qubits. However, in 2018, Chinese scientists did set a world record by linking 18 qubits together in a quantum entanglement, an interconnected state that’s required for quantum computers to actually be used for calculations. That’s in line with the general pattern of developments. ‘There’s no real evidence that the Chinese have made breakthroughs on new ways to generate qubits – that’s fundamental basic science, and there’s only so many ways that’s going to be done,’ says Tony Trippe, the managing director of Patinformatics. ‘The Chinese dominance in patenting within the last four years has primarily been in the area of application.’

  Where China’s financial muscle could prove key is in the next phase of quantum computing. ‘It’s important in terms of creating a quantum environment in China,’ says Artur Ekert, who proposed the theory behind Micius. ‘It’s not good enough to invent a telephone, for example, if it’s just you who has the unit and you have no one to call. You have to have the whole infrastructure, the whole pyramid – not just a bunch of wacky physicists, but also quantum engineers, computer scientists, cryptographers, people who can sell it.’ Ekert compares China’s approach to NASA’s Apollo project, which put a man on the Moon in the 1960s. ‘It’s not clear which particular quantum technology – whether it’s superconducting circuits, trapped ions or something else – is going to work,’ he says. ‘You need to put under one roof many people who have expertise in complementary areas.’

  But perhaps a comparison with Apollo – born from a fierce rivalry between the USA and the USSR – is not the right one to make. It’s tempting to paint the development of quantum computing and cryptography as a zero-sum game – China vs America for the global technological crown. It’s not quite like that. Jian-Wei Pan got his grounding in the technology in Europe, and Chinese researchers have been working closely with others in Austria to develop Micius and related technologies.

  However, there has been a slight shift in attitude as quantum technology has moved from academia into the world of application. ‘Five years ago I would have said that it was collaborative,’ says Ekert, ‘but in the last five years there’s been a bit of a bubble’. ‘A healthy degree of concern would be justified,’ he adds. ‘This field is just too important to have one particular region too far ahead.’ For Young, the challenge is so complex and expensive that it will be hard for any one nation to steal a march on its rivals. ‘I think it’s very difficult these days to keep anything hidden.’

  The field is fragmenting, with different research groups trying varied approaches, and countries putting their resources behind a diverse range of projects. Since 2016, when the Chinese government placed quantum at the heart of its thirteenth five-year plan, Europe and the United States have made their own investments. The European Union is putting €1 billion into its Quantum Technologies Flagship programme, which kicked into gear in 2018 with funding announced for 20 new projects. In the United States, a cross-party team has been working on legislation to inject $1.25 billion into quantum research and development. In China, they’re focusing on building a multi-satellite quantum network, and creating a quantum simulator to tackle scientific problems. In the US, the big tech companies are focused on pushing up the qubit-count and bringing down the error rate on quantum computers. The UK is at the forefront of quantum algorithms. ‘The really exciting thing, and the reason that the Chinese are investing in this, is that they don’t know what the potential will be,’ says Rob Young. ‘It’s clear this is going to be the next revolutionary technology, it’s clear there’s going to be a whole plethora of interesting devices,
and they’re investing in that potential.’

  China’s investments have certainly put it in a strong position, but it’s not clear which approaches will work, and what they could lead to – the big breakthrough could come from the $10 billion quantum hub in Hefei, or from a relatively small investment elsewhere. One country could take the lead, but for quantum to become a truly revolutionary technology will require a global effort. ‘It’s not possible for this to be developed by a single country,’ says Pan. ‘We could have a race, but people need to talk and collaborate with each other.’

  5

  Simulating nature

  The lithium-ion battery is the unsung hero of the modern world. Since it was first commercialised in the early 1990s, it has transformed the technology industry with its ability to store huge amounts of energy in a relatively small amount of space. Without lithium, there would be no iPhone or Tesla – and your laptop would be a lot bigger and heavier.

  But the world is running out of this precious metal – and it could prove to be a huge bottleneck in the development of electric vehicles, and the energy storage solutions we’ll need to switch to renewables. Some of the world’s top scientists are engaged in a frantic race to find new battery technologies that can replace lithium-ion with something cleaner, cheaper and more plentiful. Quantum computers could be their secret weapon.

  It’s a similar story in agriculture, where up to 5 per cent of the world’s consumption of natural gas is used in the Haber–Bosch process, a century-old method for turning nitrogen in the air into ammonia-based fertiliser for crops. It’s hugely important – helping sustain about 40 per cent of the world’s population – but also incredibly inefficient compared to nature’s own methods. Again, quantum computers could provide the answer.