Shor’s most famous algorithm proposes using qubits to “factor” very large numbers into smaller components. I asked him to explain how it works, and he erased the hexagons from the chalkboard. The key to factoring, Shor said, is identifying prime numbers, which are whole numbers divisible only by one and by themselves. (Five is prime. Six, which is divisible by two and by three, is not.) There are twenty-five prime numbers between one and a hundred, but as you count higher they become increasingly rare. Shor, drawing a series of compact formulas on the chalkboard, explained that certain sequences of numbers repeat periodically along the number line. The distances between these repetitions grow exponentially, however, making them difficult to calculate with a conventional computer.
Shor then turned to me. “O.K., here is the heart of my discovery,” he said. “Do you know what a diffraction grating is?” I confessed that I did not, and Shor’s eyes grew wide with concern. He began drawing a simple sketch of a light beam hitting a filter and then diffracting into the colors of the rainbow, which he illustrated with colored chalk. “Each color of light has a wavelength,” Shor said. “We’re doing something similar. This thing is really a computational diffraction grating, so we’re sorting out the different periods.” Each color on the chalkboard represented a different grouping of numbers. A classical computer, looking at these groupings, would have to analyze them one at a time. A quantum computer could process the whole rainbow at once.
The challenge is to realize Shor’s theoretical work with physical hardware. In 2001, experimental physicists at I.B.M. tried to implement the algorithm by firing electromagnetic pulses at molecules suspended in liquid. “I think that machine cost about half a million dollars,” Shor said, “and it informed us that fifteen equals five times three.” Classical computing’s bits are relatively easy to build—think of a light switch, which can be turned either “on” or “off.” Quantum computing’s qubits require something like a dial, or, more accurately, several dials, each of which must be tuned to a specific amplitude. Implementing such precise controls at the subatomic scale remains a fiendish problem.
Still, in anticipation of the day that security experts call Y2Q, the protocols that safeguard text messaging, e-mail, medical records, and financial transactions must be torn out and replaced. Earlier this year, the Biden Administration announced that it was moving toward new, quantum-proof encryption standards that offer protection from Shor’s algorithm. Implementing them is expected to take more than a decade and cost tens of billions of dollars, creating a bonanza for cybersecurity experts. “The difference between this and Y2K is we knew the actual date when Y2K would occur,” the cryptographer Bruce Schneier told me.
In anticipation of Y2Q, spy agencies are warehousing encrypted Internet traffic, hoping to read it in the near future. “We are seeing our adversaries do this—copying down our encrypted data and just holding on to it,” Dustin Moody, the mathematician in charge of U.S. post-quantum encryption standards, said. “It’s definitely a real threat.” (When I asked him if the U.S. government was doing the same, Moody said that he didn’t know.) Within a decade or two, most communications from this era will likely be exposed. The Biden Administration’s deadline for the cryptography upgrade is 2035. A quantum computer capable of running a simple version of Shor’s algorithm could appear as early as 2029.
At the root of quantum-computing research is a scientific concept known as “quantum entanglement.” Entanglement is to computing what nuclear fission was to explosives: a strange property of the subatomic world that could be harnessed to create technology of unprecedented power. If entanglement could be enacted at the scale of everyday objects, it would seem like a magic trick. Imagine that you and a friend flip two entangled quarters, without looking at the results. The outcome of the coin flips will be determined only when you peek at the coins. If you inspect your quarter, and see that it came up heads, your friend’s quarter will automatically come up tails. If your friend looks and sees that her quarter shows heads, your quarter will now show tails. This property holds true no matter how far you and your friend travel from each other. If you were to travel to Germany—or to Jupiter—and look at your quarter, your friend’s quarter would instantaneously reveal the opposite result.
If you find entanglement confusing, you are not alone: it took the scientific community the better part of a century to begin to understand its effects. Like so many concepts in physics, entanglement was first described in one of Einstein’s Gedankenexperiments. Quantum mechanics dictated that the properties of particles assumed fixed values only once they were measured. Before that, a particle existed in a “superposition” of many states at once, which were described using probabilities. (A famous thought experiment, proposed by the physicist Erwin Schrödinger, imagined a cat trapped in a box with a quantum-activated vial of poison, the cat superpositioned in a state between life and death.) This disturbed Einstein, who spent his later years formulating objections to the “new physics” of the generation that had succeeded him. In 1935, working with the physicists Boris Podolsky and Nathan Rosen, he revealed an apparent paradox in quantum mechanics: if one took the implications of the discipline seriously, it should be possible to create two entangled particles, separated by any distance, that could somehow interact faster than the speed of light. “No reasonable definition of reality could be expected to permit this,” Einstein and his colleagues wrote. In subsequent decades, however, the other predictions of quantum mechanics were repeatedly verified in experiments, and Einstein’s paradox was ignored. “Because his views went against the prevailing wisdom of his time, most physicists took Einstein’s hostility to quantum mechanics to be a sign of senility,” the historian of science Thomas Ryckman wrote.
Mid-century physicists focussed on particle accelerators and nuclear warheads; entanglement received little attention. In the early sixties, the Northern Irish physicist John Stewart Bell, working alone, reformulated Einstein’s thought experiment into a five-page mathematical argument. He published his results in the obscure journal Physics Physique Fizika in 1964. During the next four years, his paper was not cited a single time.
In 1967, John Clauser, a graduate student at Columbia University, came across Bell’s paper while paging through a bound volume of the journal at the library. Clauser had struggled with quantum mechanics, taking the course three times before receiving an acceptable grade. “I was convinced that quantum mechanics had to be wrong,” he later said. Bell’s paper provided Clauser with a way to put his objections to the test. Against the advice of his professors—including Richard Feynman—he decided to run an experiment that would vindicate Einstein, by proving that the theory of quantum mechanics was incomplete. In 1969, Clauser wrote a letter to Bell, informing him of his intentions. Bell responded with delight; no one had ever written to him about his theorem before.
Clauser moved to the Lawrence Berkeley National Laboratory, in California, where, working with almost no budget, he created the world’s first deliberately entangled pair of photons. When the photons were about ten feet apart, he measured them. Observing an attribute of one photon instantly produced opposite results in the other. Clauser and Stuart Freedman, his co-author, published their findings in 1972. From Clauser’s perspective, the experiment was a disappointment: he had definitively proved Einstein wrong. Eventually, and with great reluctance, Clauser accepted that the baffling rules of quantum mechanics were, in fact, valid, and what Einstein considered a grotesque affront to human intuition was merely the way the universe works. “I confess even to this day that I still don’t understand quantum mechanics,” Clauser said, in 2002.
But Clauser had also demonstrated that entangled particles were more than just a thought experiment. They were real, and they were even stranger than Einstein had thought. Their weirdness attracted the attention of the physicist Nick Herbert, a Stanford Ph.D. and LSD enthusiast whose research interests included mental telepathy and communication with the afterlife. Clauser showed Herbert his experiment, and Herbert proposed a machine that would use entanglement to communicate faster than the speed of light, enabling the user to send messages backward through time. Herbert’s blueprint for a time machine was ultimately deemed unfeasible, but it forced physicists to start taking entanglement seriously. “Herbert’s erroneous paper was a spark that generated immense progress,” the physicist Asher Peres recalled, in 2003.
“I’m so glad you’re a foodie.” Cartoon by Liza Donnelly Link copied
Ultimately, the resolution to Einstein’s paradox was not that the particles could signal faster than light; instead, once entangled, they ceased to be distinct objects, and functioned as one system that existed in two parts of the universe at the same time. (This phenomenon is called nonlocality.) Since the eighties, research into entanglement has led to continuing breakthroughs in both theoretical and experimental physics. In October, Clauser shared the Nobel Prize in Physics for his work. In a press release, the Nobel committee described entanglement as “the most powerful property of quantum mechanics.” Bell did not live to see the revolution completed; he died in 1990. Today, his 1964 paper has been cited seventeen thousand times.
At Google’s lab in Santa Barbara, the objective is to entangle many qubits at once. Imagine hundreds of coins, arranged into a network. Manipulating these coins in choreographed sequences can produce astonishing mathematical effects. One example is Grover’s algorithm, developed by Lov Grover, Shor’s colleague at Bell Labs in the nineties. “Grover’s algorithm is about unstructured search, which is a nice example for Google,” Neven, the founder of the lab, said. “I like to think about it as a huge closet with a million drawers.” One of the drawers contains a tennis ball. A human rooting around in the closet will, on average, find the ball after opening half a million drawers. “As amazing as this may sound, Grover’s algorithm could do it in just one thousand steps,” Neven said. “I think the whole magic of quantum mechanics can essentially be seen here.”
Neven has had a peripatetic career. He originally majored in economics, but switched to physics after attending a lecture on string theory. He earned a Ph.D. focussing on computational neuroscience, and was hired as a professor at the University of Southern California. While he was at U.S.C., his research team won a facial-recognition competition sponsored by the U.S. Department of Defense. He started a company, Neven Vision, which developed the technology used in social-media face filters; in 2006, he sold the company to Google, for forty million dollars. At Google, he worked on image search and Google Glass, switching to quantum computing after hearing a story about it on public radio. His ultimate objective, he told me, is to explore the origins of consciousness by connecting a quantum computer to someone’s brain.
Neven’s contributions to facial-analysis technology are widely admired, and if you have ever pretended to be a dog on Snapchat you have him to thank. (You may thank him for the more dystopian applications of this technology as well.) But, in the past few years, in research papers published in the world’s leading scientific journals, he and his team have also unveiled a series of small, peculiar wonders: photons that bunch together in clumps; identical particles whose properties change depending on the order in which they are arranged; an exotic state of perpetually mutating matter known as a “time crystal.” “There’s literally a list of a dozen things like this, and each one is about as science fictiony as the next,” Neven said. He told me that a team led by the physicist Maria Spiropulu had used Google’s quantum computer to simulate a “holographic wormhole,” a conceptual shortcut through space-time—an achievement that recently made the cover of Nature.
