The quest for quantum computing

There exist problems so complex, so inscrutable, that to solve them with even an efficient algorithm would take modern computers more time than the current age of the universe—or even longer.

Naturally, many of the most formidable, notorious problems known to science at this point are these kinds of problems, including the Traveling Salesman problem, which seeks to optimize a pathway between a set of points. But what if there was a way to solve such problems not only expediently, but in less time than you can say “quantum computing?”

Quantum computers are a theoretical alternative to traditional computers that have the ability to solve impossibly difficult problems using traditional means. They do so by using qubits (pronounced “cubit”) in lieu of the traditional bits.

Bits, a construct which computers use to perform calculations, can be conceptualized like a binary switch—they are either on or off at any given moment, and are used to represent numbers and other forms of data.

The [computers] we use are binary-based, so all you have is a series of off-on states that you can control very, very rapidly,” said Dr. Eric Nelson, upper school computer science department chair and modern physics teacher. “So computers are useful because you can do things really, really fast, so you do a whole bunch of sequential, deterministic calculations, manipulating bits.”

But even with the speed of computers, some problems still take far too much time to complete. This is where qubits come in. Unlike bits, which can only be in one of two states—zero or one, off or on, false or true—qubits exist as a superposition of states. They are simultaneously partially both zero and one, both off and on, both false and true.

“[Superpositioning is] a really bizarre property of subatomic particles. One way of thinking about it is to imagine you have a quantum coin—[with] a quantum coin, both sides would be heads and tails simultaneously with a 50-50 mix,” Dr. Nelson said. “It’s not flipping back and forth; it just exists as heads and tails on both sides at the same time.”

But whenever a superposed particle is observed, it “collapses” into a single state: it will appear to be only heads or only tails.

Unlike bits, which can only be in one of two states—zero or one, off or on, false or true—qubits exist as a superposition of states. They are simultaneously partially both zero and one, both off and on, both false and true.

By using superpositioning, qubits can simultaneously hold multiple values, while regular bits can only hold one value. As a result, performing calculations using qubits would be equivalent to performing multiple calculations simultaneously.

“Instead of having to run through every single possible [value in a calculation], instead you have a system where all the possible states of that value exist simultaneously in a superposition of states,” Dr. Nelson said. “You then look at this ‘answer,’ for lack of a better word, which has the superposition of all possible answers. You observe the answer millions of times and look and see which ones pop up the most. The ones that are most frequent have the highest probability of being correct.”

The fruition of a quantum computer would also have significant implications for the state of modern cryptography. Current encryption methodologies rely on “trapdoor functions,” functions which are very easy to compute in one direction yet extremely difficult to compute in the other. For example, it is near impossible to determine the two prime factors of the number 4,399 in a reasonable timeframe, but it’s quite trivial to multiply 53 and 83. This exact problem—integer factorization—forms the basis of some public-key cryptography systems, the same systems that protect your digital communications today. But the advent of quantum computers would suddenly “solve” integer factorization and other trapdoor functions, rendering them useless for encryption purposes.

Imagine that all the trapdoors have a nice little elevator built into them,” Dr. Nelson said. “We’ll have to completely rethink our concepts of data encryption once these things become standard on computer systems.”

Quantum computers and quantum cryptography have justifiably attracted attention from governments and companies alike. For instance, Microsoft is currently funding efforts to build a practical quantum computer in its Station Q project, and the Chinese Academy of Science launched the Micius satellite this August with the aim of testing quantum cryptography.

While the creation of a stable, economical quantum computer would probably not affect civilian computers at all—mundane tasks such as sending emails or searching the internet do not need such computational speed—they would revolutionize the scientific community. Complex problems such as determining the structures of proteins and finding large prime numbers would be made much easier with quantum computers.

Though scientists have yet to create a fully functional quantum computer, qubits can be created and applied on a limited scale. But as the technology improves, the possibility of creating a fully-fledged quantum computer approaches—and along with it, solutions to some of the greatest problems ever conceived.