Entangled spies: Why the NSA wants a quantum computer

The US National Security Agency wants a quantum computer – and has dedicated $79.7 million to the technology, according to the latest top secret government documents leaked by former NSA contractor Edward Snowden tothe Washington Post.

It is no surprise that the NSA is pursuing such a potentially powerful technology, nor does the revelation pose an immediate privacy threat – the documents suggest that the agency is no closer to perfecting the technology than university researchers around the world. But if the agency does eventually realise its goal, what do citizens need to watch out for? And is there technology that would allow people to stay safe from quantum spooks?

Quantum computers promise to vastly outperform even the best ordinary computers at specific tasks by exploiting the weird properties of quantum mechanics. While a regular PC computes with bits that are either 0s or 1s, quantum machines use quantum bits, or qubits, which can be both simultaneously, and offer a computational speed-up.

Cracking the internet

One area quantum computers should excel in is factoring numbers into their prime building blocks. That could make them capable of breaking the internet's most commonly used encryption methods, which depend on the fact that ordinary computers can't find prime factors quickly. So in principle, the NSA could use a quantum computer to read secret data – without the need to collude with tech firms, which they have done in the past.

The NSA programme, called "Penetrating Hard Targets", apparently aims to build a quantum computer big enough to outperform the conventional variety. However, the Snowden documents, which are dated 2011, only mention aspirations for a machine consisting of two working qubits – far too small to factorise the large numbers that ordinary computers struggle with. It is also smaller than some of the quantum computers that university researchers are working with.

It is possible that the NSA has made progress since then, or has other technologies not mentioned in the documents. But Scott Aaronson, a quantum computer researcher at the Massachusetts Institute of Technology told the Washington Post that he is doubtful that they could be taking the lead yet. "It seems improbable that the NSA could be that far ahead of the open world without anybody knowing it," he said.

Another quantum tool that might interest the NSA is Grover's algorithm, a database search algorithm that is theoretically much faster than any ordinary software. Snowden's leaks have revealed that the NSA runs vast data collection programmes, so any way to sift through the noise and quickly identify targets would benefit their efforts.

Safety in physics

However, the biggest Grover implementation so far, on a system of three qubits, can only search through eight database elements – in other words, this algorithm is nowhere near outperforming ordinary computers given existing, known quantum hardware.

However, if the NSA does ever manage to build a much bigger quantum computer, there is still one technology that could help keep data secure, and it also relies on quantum mechanics. Quantum key distribution uses photons to generate a sequence of 0s and 1s that serve as an encryption key. Anyone attempting to intercept the key will unavoidably disturb the photons, revealing that the data has been tampered with – the laws of physics keep you safe.

This ultra-secure cryptography is already commercially available, and was even used to secure a Swiss election in 2007. But there are limits – building a global quantum network to rival the internet, rather than a small local network, would require technologies that do not exist yet.

Even if we end up with a secure quantum internet, it is still possible that the NSA might find a way to snoop. Although the underlying physics is secure, physical systems might not be. Quantum hacking is possible by predicting and exploiting flaws that are likely to exist in the way the hardware implements the physics – and the NSA knows it. According to the Snowden documents, one of its research goals is to "support the development of novel Quantum Key Distribution (QKD) attacks and assess the security of new QKD system designs".