Quantum Computers and the End of Privacy
From government to business to regular individuals, encryption is important. It’s how we maintain some level of privacy in our lives. It protects our email and our credit cards. For some, it can be a matter of life and death. And it’s a risky business. We never know if our passwords have been compromised, or if the systems that we use provide some kind of backdoor that allows others to spy on us. But in the future, we may face a much bigger issue: quantum computers.
Encryption depends upon creating mathematical equations that take modern computers an extremely long time to solve — longer than the age of the universe. But quantum computers could change all that.
Just how fast would quantum computers be? Exponentially. To solve a 100bit encryption problem would take a digital computer 2^{50} steps. That’s:
A quantum computer would take only 50 steps to do the same calculation.
So what are these amazing devices? They are computers that harness the power of quantum mechanics. Digital computers store data in bits. They can be 0 or 1. Quantum computers are based on qubits. They are twostate quantum systems — effectively partly 0 and partly 1. This is called quantum superposition. Think: Schrödinger’s cat.
This may not sound like much, but a whole computational system has been built on top of quantum superposition. And the result is an unimaginably faster computer.
Or that would be the result if anyone had been able to build a universal quantum computer. Creating qubits is very hard. And they are unstable. Currently, they only last on the order of nanoseconds. But big institutions like the National Security Agency and Google are working on them. And progress is being made.
So will all our secrets soon be exposed? Will quantum computers bring an end to online privacy?
Get all the details below.
Quantum Computers, Encryption Wars, and the End of Privacy
From law enforcement to criminals, governments to insurgents, and activists to Facebook dabblers, many people have come to rely on encryption to protect their digital information and keep their communications secure. But the current forms of encryption could be obsolete the moment anyone succeeds in building a quantum computer. A what?! Read on about the brave new world awaiting us.
Binary vs Quantum

Binary

Typical computers are binary — they encode information as a series of 1s or 0s
 This applies even to supercomputers, which operate hundreds of thousands,if not millions, of times more quickly than regular computers

These 1s or 0s are called “bits”

A bit has two states:
 On/1
 Off/0

A bit has two states:

Typical computers are binary — they encode information as a series of 1s or 0s

Quantum

A quantum bit is called a “quibit”

Qubits can not only be 1 or 0, they can be both at the same time
 This is called “superposition”
 Certain molecules, atoms, and electrons have been used successfully as qubits

Qubits can not only be 1 or 0, they can be both at the same time

A quantum bit is called a “quibit”

The value of a quantum computer
 One qubit (or bit) by itself isn’t of much use, but the more quibits a computer has, the more complex calculations it can carry out

One of the things quantum computers can do better than regular computers is reach an end goal with an exponentially smaller number of operations
 Factoring large numbers, for example — the basis of much encryption
Encryption and Factoring Large Numbers

Many common forms of encryption, such as RSA, DiffieHellman, and others rely on the difficulty of factoring large numbers for the security of their encryption (though others, such as EC and AES, do not)

Prime numbers are those that can only be divided by 1 and themselves
 1, 5, 7, etc.

All numbers have one prime factorization

This means that every number can be reached by multiplying some primes together
 68 = 2×2×17
 3,654 = 2×3×3×7×29

This means that every number can be reached by multiplying some primes together

For a computer, finding a large prime number is relatively simple

Factoring large numbers is considerably more difficult in that it takes an exceedingly long time to do so
 Normal computers have to go through each set of primes until they reach the correct set
 Even supercomputers — which have many processors working in parallel — have trouble with large enough prime factorizations

Factoring large numbers is considerably more difficult in that it takes an exceedingly long time to do so

If we had a computer that could do long division in a millionth of a second, it would take longer than the lifespan of our sun to factor a 100digit number.
 Our sun has an expected lifespan of 15 billion years.
 The length of time it would take to figure out the key is what makes using prime factorization so useful for cryptography.

Prime numbers are those that can only be divided by 1 and themselves
How Quantum Computers Crack the Code

Even forms of encryption that don’t use prime factorization rely on the fact that bruteforce number crunching requires so many steps that doing so is unfeasible

To find the pattern in an EC cipher, for example, with a 100 bit key would take
 Binary computer: 2^{50} (over 1 quadrillion) steps
 Quantum computer: 50 steps

A normal computer has to work its way through each calculation one at a time

A quantum computer’s qubits allow it to avoid unnecessary calculations
 As a result, it can find the answer faster and with far fewer steps

A quantum computer’s qubits allow it to avoid unnecessary calculations

To find the pattern in an EC cipher, for example, with a 100 bit key would take
Where Can I Get My Own Quantum Computer?

DWave Systems, Inc. markets their DWave Two as a quantum computer, but other computer science experts disagree that it’s a “proper” quantum computer
 The issue is that DWave’s machine takes advantage of some quantum mechanics, but it isn’t a universal quantum computer, able to do any quantum computation

Here are some of the people working to build the quantum computers and qubits of tomorrow:

Google
 Google has been working with DWave Systems since 2009
 In April 2014, John Martinis and a group of UC Santa Barbara physicists successfully operated five qubits together with a low rate of error
 Google hired Martinis and his team to work at their quantum hardware lab in September 2014

The DWave machine that Google uses contains a chip with 512 qubits wired into a quantum annealer
 A quantum annealer solves optimization problems, like “What is the most efficient route for a package to take across town?”

Currently, Google’s DWave machine can only keep qubits in superposition for a few nanoseconds
 According to Martinis, he has built qubits that can last for 30 microseconds (30,000 nanoseconds)

National Security Agency (NSA)

According to documents leaked by Edward Snowden:
 The NSA is building a quantum computer capable of performing cryptography
 It is part of the NSA’s $79.7 million research program called “Penetrating Hard Targets”

According to documents leaked by Edward Snowden:

University of New South Wales in Australia
 In October 2014, two separate teams of researchers at USW successfully created qubits that are more than 99.99 percent accurate

Both teams used Silicon28, an isotope, in the creation of their qubits as it is perfectly nonmagnetic
 One team embedded a phosphorus atom into the silicon
 The other team created and then embedded an artificial atom — essentially a transistor with one electron trapped inside
 The phosphorus atom team set a world record for the length of time quantum information could be preserved in a silicon system before it decoheres: 35 seconds

Google
Quantum Encryption

Although quantum computers would allow users to crack many forms of encryption already out there, they would also foster the creation of new forms of encryption, especially ultrasecure keys

ID Quantique

About ID Quantique
 Based in Geneva, Switzerland
 Founded: 2001

Offers consumers quantum key distribution (QKD)
 Starting in 2004
 QKD involves generating and transmitting an encryption key simultaneously
 Use fiber optic cabling

Because measuring the quantum state of information affects it, this makes “eavesdropping” on a transmission practically impossible.
 If someone tried to measure the photons traveling through the line, the customer would receive an error message, and no key would be created

The system is limited in terms of range
 It only offers ranges of up to 62 miles
 The company has achieved 155 miles in the lab
 248 miles is the theoretical limit for this method
 An emitterreceiver pair costs $97,000

About ID Quantique

The Institute for Quantum Computing (IQC)

About IQC
 Affiliated with University of Waterloo in Ontario, Canada
 Founded: 2002
 One of the few places in the world with a quantum key distributor (QKD)

About QKD

The pieces of the QKD are called “Alice” and “Bob”
 Alice is a machine located at ICQ headquarters
 Bob is a machine located at the nearby Perimeter Institute

The pieces of the QKD are called “Alice” and “Bob”
 Like IQ Quantique, the IDC’s QKD depends on the nature of entangled particles to ensure that no one can “listen in” on the sharing of an encryption key

First, a laser at the University of Waterloo creates entangled photons
 Alice receives half of these photons
 Bob receives the other half

Photons have a measurable quality called “polarization”
 The polarization of any given photon will be random
 If both sets of the device measure their photons, they will have the same polarization
 By assigning 1 or 0 to a certain polarization, Bob and Alice can continue until their randomly generated key is long enough for their encryption

This method is highly secure because:
 Any attempt to “listen in” on the signal will make itself known

There is no way to know what polarization the photons will have ahead of time
 Thus, there is no way to “work backwards” and figure out the keys

About IQC

ID Quantique
Live by the quantum computer, die by the quantum computer? It certainly looks as though eventually, quantum computers will make traditional binary encryption obsolete. But this will happen at the same time that quantum computers create a whole new level of data security. And the encryption arms race will continue.
Sources: arstechnica.com, cacr.uwaterloo.ca, computer.howstuffworks.com, computerworld.com, dwavesys.com, idquantique.com, learncryptography.com, mathworld.wolfram.com, motherboard.vice.com, nature.com, news.ucsb.edu, pumpkinprogrammer.com, quora.com, sciencealert.com, scienceblogs.com, searchsecurity.com, technologyreview.com, tested.com, universetoday.com, uwaterloo.ca, washingtonpost.com, web.stanford.com, webopedia.com, whatis.techtarget.com, wired.com, youtube.com.
Sources
 Your Encryption Will Be Useless Against Hackers With Quantum Computers
 What Are Supercomputers Used For?
 What Makes a Supercomputer?
 Quantum Computing
 Qubit
 A Tale of Two Qubits How Quantum Computers Work
 Bits and Bytes
 Intro to Binary Numbers
 How Does a Quantum Computer Work?
 The Phosphorous Atom Quantum Computing Machine
 Quantum Computing 101
 Prime Factorization
 RSA Algorithm
 DiffieHellman Protocol
 Public Key Cryptography
 Why Is Factoring Numbers Into Primes a Difficult Problem
 What Is the Life Cycle of the Sun
 NSA Seeks to Build Quantum Computer That Could Crack Most Types of Encryption
 The Clock Is Ticking for Encryption
 Confused About the NSA’s Quantum Computing Project? This MIT Computer Scientist Can Explain
 DWave
 Your Encryption Will Be Useless Against Hackers With Quantum Computers
 Superconducting Qubit Array Points Way Quantum Computers
 The Man Who Will Build Google’s Elusive Quantum Computer
 Evidence for Quantum Annealing With More Than One Hundred Qubits
 Google Launches Effort to Build Its Own Quantum Computer
 Australian Researchers Have Created the Most Accurate Quantum Computing Technology
 ID Quantique
 The Case for Quantum Key Distribution (PDF)
Download this infographic.
Join our newsletter & be first to hear when we publish new posts.
“Programming the Universe” by Seth Llyod (Professor of QuantumMechanical Engineering at MIT) does a great job of explaining how quantum computing works.
https://www.goodreads.com/book/show/331680.Programming_the_Universe
October 31st, 2016 at 9:55 am
Thanks for the recommendation. I just ordered it. Should be fun. My real interest is in quantum computation. But who has the time? Time may be an ocean, but it sure feels like a garden hose…
November 1st, 2016 at 6:15 pm