Ask One Question of Every Quantum Headline: Is It Faster Than Classical?

Lex Fridman opens by defending the philosophical questions he gets criticized for asking world-class scientists: free will, consciousness, whether we live in a simulation. Scott Aaronson, then a professor at UT Austin and director of its Quantum Information Center, does not treat those questions as a waste of a technical hour. Philosophy, he says, is almost by definition the subject concerned with the biggest questions you could possibly ask. The sharper puzzle is why anyone spends a career on narrower ones.

The scientific revolution taught a good reason. Narrower mathematical and empirical questions can actually be answered, and sometimes they reframe the childhood mysteries that got you into intellectual life in the first place. They do not always resolve the philosophical problem, but they can change how you understand it. For Aaronson, philosophy sits in the background as the original motive. Math and science are the tools for making progress, sometimes more than philosophy itself does.

He is not sure computer scientists flee these questions more than other scientists. Alan Turing published one of his two most famous papers in the philosophy journal *Mind*, the one that proposed the Turing test. Aaronson enjoys philosophy conferences and talking with philosophers. He would not want the job, because when the eternal questions get too confusing he wants a field where he can still make progress on something.

In 1939 Turing sat in Wittgenstein's Cambridge course. The transcript, Aaronson says, is one of the more fascinating documents he has ever read. Wittgenstein kept insisting that formal systems were a complete irrelevancy: if a system is irrelevant, who cares, and what does it matter in real life? Turing's reply was concrete. If you use an inconsistent formal system to design a bridge, the bridge may collapse.

In Aaronson's reading, Turing was already thinking decades ahead of the classroom, to a world in which formal systems would run inside computers and actually do things. Wittgenstein was still arguing about whether the systems meant anything. Turing dropped the course halfway through and went to Bletchley Park, stepping from philosophical argument into engineering with immediate stakes. That leap, Fridman notes, is enormous.

A lot of scientists are interested in philosophy and also busy. Their plates are full of concrete questions that look answerable, so they ask why they should break their brains over metaphysically unanswerable ones. Stereotyping a little, Aaronson says philosophers will pounce on a wrong phrase, while scientists try to drag free will or the hard problem of consciousness back to recent work in neurobiology, preferably their own. Even if that work never answers the hard problem, it can take us about as far as we can get toward thinking about it differently. Art and literature do some of the same work. We still return to questions for which we do not even know what an answer would look like.

Aaronson's name for the method is Q′. Given an unanswerable philosophical riddle Q, replace it with a merely scientific or mathematical question that captures part of what people wanted to know when they first asked Q. Then work on Q′. In his essay *Why Philosophers Should Care About Computational Complexity*, he catalogs examples where theoretical computer science has done exactly that.

Turing's 1950 paper is the cleanest case. He starts with "Can machines think?" and, in the first two sentences, throws the question out as too meaningless. He offers a different one: could you program a computer so that you could not tell the difference between it and a human? Gödel did a similar swap. Centuries of argument about the limits of mathematical reasoning became a precise question: are there statements, phrased inside a formal system's rules, that are not provable inside those rules, and can we prove that fact?

He tried the same substitution on free will in an essay he calls one of the crazier things he has written, *The Ghost in the Quantum Turing Machine*. Instead of arguing for centuries about what freedom means, or whether it is compatible with determinism, ask how well, in principle, a person's behavior could be predicted without destroying the brain in the process. That question drops you into meaty issues: what is the computational substrate of the brain, and is the neural-network abstraction enough, or do you have to go down to molecules, even to the quantum level?

If you want to predict a person, you need a model of their brain, and the question becomes how accurate that model can get. Laplace's demon, the thought-experiment mind that knows the complete state of the universe, does not trouble Aaronson much, because he has never met such a demon and there are reasons to think it could not exist as part of our world. A machine you could actually step into is different. If it wrote every paper you will ever write, and every thought you are having about the machine itself, that would threaten the internal sense of free will in a much more visceral way. The discussion then becomes empirical: is such a machine possible, and if not, what in the laws of physics or the brain prevents it?

An obvious candidate, noticed by Eddington and others almost as soon as quantum mechanics was discovered in the 1920s, is noise in the brain. Sodium ion channels behave chaotically, governed by differential equations with a stochastic term. That randomness ultimately comes from molecular-scale quantum events, amplified by a butterfly effect, and it can decide whether a neuron fires. Even with the complete quantum state of someone's brain, you could at best predict probabilities. Aaronson thinks that part is relatively uncontroversial. The controversial question is whether it matters philosophically. If all quantum mechanics does is inject randomness into an otherwise mechanistic process, who cares? A machine that listed every action with a 10 percent chance, and then watched you do exactly a tenth of them, would feel about as freedom-killing as a deterministic predictor.

A subtler obstacle is measurement itself. Measuring a quantum state is destructive: a particle in a superposition of positions is localized the moment you look. Building a model accurate enough for well-calibrated probabilistic predictions might require measurements so precise they fundamentally alter the brain. Or maybe a swarm of nanorobots watching neurons at a macroscopic scale would suffice. Either way, Aaronson says, we are now asking a question where it is possible to envision what progress would look like. If the prediction machine could actually be built, even the leftover metaphysical argument would take place in a transformed world. He adds that seeing the envelopes in advance would change his subjective experience of deciding, and might drive him insane.

Fridman turns the conversation to quantum computing, which Aaronson calls a proposal for a new way to harness nature to do computation, based on principles in place since 1926. What is new is how we want to use them. Physicists over the generations convinced people that what quantum mechanics says about the world is unbelievably complicated. Aaronson lets non-physicists in on a secret: it becomes a lot simpler if, as in quantum information theory, you take the physics out of it and treat the theory as a generalization of the rules of probability.

You might say there is a 30 percent chance of snow. You would never say there is a negative 30 percent chance, still less a square-root-of-minus-one percent chance. The central discovery of quantum mechanics is that the world is described by amplitudes, numbers that are like probabilities in some ways and not in others. They can be positive, negative, or complex. A superposition simply means you assign one of those amplitudes to every configuration you might see on measuring the system. When you look, the amplitudes convert to probabilities by taking the square of their absolute value, and the system is forced to pick.

While the system stays isolated, amplitudes change by rules alien to everyday experience, and they can interfere. In the double-slit experiment, an electron fired at two slits never appears at certain spots on a second screen, yet closing off one slit lets it appear there. Decreasing the number of paths can increase the chance of arrival, because you add the amplitudes for every path, and a positive amplitude plus a negative one can cancel to zero. Close one path and the leftover amplitude is no longer cancelled. That interference trick, Aaronson says, is the one trick of quantum mechanics, and a quantum computer is a machine that tries to exploit superposition, amplitudes, and interference to solve certain problems faster than we know how to solve them otherwise.

The basic building block is a qubit: a bit with some amplitude for being 0 and some amplitude for being 1. The key point is what happens when you have many of them. If you have a thousand qubits, the rules of quantum mechanics are unequivocal: you do not just need an amplitude for each qubit separately. In general you need an amplitude for every possible setting of all thousand bits, which is 2^1000 amplitudes. Writing that many complex numbers down in a conventional computer's memory would not fit in the entire observable universe.

This is where almost every popular article goes off the rails. They recap the exponential state space and then say a quantum computer works by trying every possible answer in parallel. That sounds too good to be true, and unfortunately it kind of is. You can easily make a superposition over every possible answer, even 2^1000 of them. For a computer to be useful you eventually have to look at it, and measuring a superposition over every answer yields a random answer. If you just wanted a random answer, you could have picked one yourself with a lot less trouble.

The entire trick, in every quantum algorithm, is to choreograph a pattern of interference. For each wrong answer, some of the paths leading there should have positive amplitudes and others negative, so they cancel. Paths leading to the right answer should reinforce, with amplitudes pointing the same direction. Designing algorithms in this space, Aaronson agrees with Fridman, is precisely the choreography of interference.

Information sits at the core of the picture. The bit has been the basic unit since Claude Shannon's 1948 paper popularized the name. The basic unit of quantum information is the qubit: any object that can be maintained and manipulated in a superposition of 0 and 1. People ask what a qubit is physically, and several implementations are being pursued in parallel. Google's then-recent supremacy experiment used superconducting coils, cooled to about a hundredth of a degree above absolute zero, in which current can flow in two energy states, or in a superposition of both. Another kind is an atomic nucleus, spinning clockwise, counterclockwise, or both.

In the classical world you can be a virtuoso programmer without knowing what a transistor is, or even that the machine uses electricity. You care about the logic. Quantum computing aspires to the same split: many physical systems, one logic of qubits. Today, honestly, the layers still interfere, because every quantum computer we can build is very noisy and the qubits are far from perfect. The hope is error-corrected machines whose qubits behave like perfect abstract qubits for as long as we want. In that future, which theorists can already prove theorems about, the logic really does decouple from the hardware.

The fundamental problem in building a quantum computer of any appreciable size is decoherence, recognized from the beginning of the 1990s. It means unwanted interaction between your qubits and the external environment. Measuring a qubit in superposition forces it to choose 0 or 1. The trouble is that it does not have to be you looking. Any leak of the information into the radiation in the room, the air molecules, or the wires connected to the device counts as a measurement. The state collapses, or equivalently becomes entangled with its environment, and from the point of view of someone watching that qubit, the quantum state is gone.

So you have to keep the qubits fanatically isolated, and at the same time you cannot isolate them perfectly, because you need to tell them what to do and make them interact in a precisely choreographed way. Distinguished physicists and computer scientists in the 1990s said this was fundamentally impossible. What changed most people's minds was the theory of quantum error correction and fault tolerance in the mid to late 1990s. You do not need perfect isolation. You need isolation that is really, really good. Encode the information you care about across the collective state of many qubits, monitor for leaks, correct them, and recover from the remaining qubits. You can build a reliable quantum computer out of unreliable parts. That discovery set the engineering agenda from the 1990s to the present.

The cost is overhead. To factor huge numbers and break RSA with known codes, you want several thousand logical qubits, and each of those would itself be encoded in thousands of physical qubits, which puts you at millions of physical qubits. That, Aaronson says, is why quantum computers are not breaking cryptography already. Physicist John Preskill named the current stage NISQ, noisy intermediate-scale quantum: the vacuum-tube era, before the transistor analogue of true error correction. As of Google's supremacy announcement a few months before the taping, even a non-error-corrected device could do something hard for classical computers to simulate. Whether this noisy era can also do something useful is the race of the next decade, involving Google, IBM, startups, labs, and governments.

Preskill coined "quantum supremacy" in 2012. Not everyone likes the name, but no better alternative has stuck. The idea goes back to Feynman and Deutsch in the early 1980s: the point in history when you can first use a quantum computer to do some well-defined task much faster than any known algorithm on available classical machines. Aaronson is careful not to say useful. The task can be completely artificial. It must have right and wrong answers knowable independently of the device. Everything a quantum computer can do, a classical computer can eventually do by storing all the amplitudes and updating them with linear algebra, just exponentially more slowly. Quantum computers do not leave Turing's definition of computation. What they change, we think, is what is efficiently computable.

Aaronson wants three things at once: a literal wall-clock win, a problem whose quantum scaling is believed to be polynomial while the classical scaling is exponential, and an observed speedup that is only explainable by that scaling, a 50-qubit state of 2^50 amplitudes that a classical simulation would have to track. Supremacy does not require error correction. It is already enough, he says, to refute skeptics who claimed a quantum computer would never outperform a classical one for anything. Around 2011, he and his student Alex Arkhipov, independently of Bremner, Jozsa, and Shepherd, realized that if you only want to prove a speedup, sampling problems beat factoring. The goal is to output a sample from a distribution over, say, 50-bit strings. Many outputs are valid; the machine may never produce the same one twice; some are supposed to be likelier than others.

Google's device had 53 qubits, so 2^53 possible outputs, about nine quadrillion. A randomly chosen but precisely recorded sequence of interactions creates very specific garbage: all outputs exponentially unlikely, some two or three times unlikelier than others. Google's linear cross-entropy benchmark takes the samples and, classically, computes the probabilities they should have had, asking whether the device is biased toward the strings it should prefer. The test itself is a 2^53 calculation, just barely possible on Summit at Oak Ridge National Lab. Ironically, this kind of experiment does not want 100 qubits, because then you could not verify. Fifty-three is the scale that makes the biggest classical machines sweat and still lets them check. Past that, sampling experiments lose interest and you have to switch tasks.

How do we know a classical computer could not have spoofed the same output? We do not know for sure. The question sits at the magnitude of P versus NP. What theorists can do is pass the blame: if this sampling task is easy classically, then other things you were more confident were hard would be easy too. Those reductions, the same strategy as NP-completeness and cryptography since the 1970s, are not as satisfactory as they should be. Improving them is one of the biggest open problems in the area. Empirically, known classical simulation methods also have to be checked against Google's actual parameters to confirm they still scale exponentially.

Fridman quotes a tweet from presidential candidate Andrew Yang: because of quantum computing, no code is uncrackable. Aaronson, who says he likes Yang's candidacy, calls the tweet premature, then plainer: wrong. Peter Shor's discovery twenty-six years earlier, the result that made quantum computing an autonomous field, was that a full-scale quantum computer could efficiently factor huge numbers, compute discrete logarithms, and solve a few other very special problems. Those problems are almost certainly not NP-complete. It so happens that most of the public-key cryptography protecting the internet is based on the belief that they are hard. Shor showed that scalable quantum computers would make that belief false.

Before anyone panics, two points. First, Google's 53 physical qubits are very, very far from the machine that would threaten public-key cryptography. With known error-correction methods you are talking millions of physical qubits, of much higher quality than any that exist now. Aaronson does not think that is coming soon. People whose secrets need to stay secret for twenty years are already worried, for a good reason: intelligence agencies are presumed to be scooping up data now, hoping to decrypt it once quantum computers arrive.

Second, there are other public-key systems we do not know how to break even with quantum computers. The field is post-quantum cryptography, and the best-known candidates are lattice-based. The United States was about to hold a competition to create standards, the first step toward getting every web browser and router to upgrade. The migration will be long, but it had already started. Shor's algorithm could be a big deal for whichever intelligence agency first gets a scalable machine, especially if no one else knows they have it. Eventually, if the internet moves to post-quantum cryptography, we are more or less back where we started. That is not, in Aaronson's view, the application that will change the world in a sustainable way.

The biggest practical application we know about, by far, is simulating quantum mechanics in order to learn about chemical reactions and maybe design new processes, materials, drugs, solar cells, and superconductors. People will race over the next decade to do useful simulations even with the 100- or 200-qubit machines expected in that window. That might be the first realized application, or it might prove too difficult and still need fault tolerance. Aaronson is sure of the comparison with crypto: the best shot in the next decade is not Shor's algorithm, because the error-correction burden is too high. It is a simulation that tells a materials scientist, chemist, or nuclear physicist something useful they did not already know. One or two successes could move billion-dollar industries.

Fertilizer is still made with the Haber-Bosch process from a century ago, a many-body quantum mechanics problem no one really understands. A better way to make fertilizer is billions of dollars by itself. A Microsoft group had estimated that even about a hundred qubits could teach us something new about that reaction. The trouble is they meant a hundred qubits and about a million layers of quantum gates: a hundred nearly perfect logical qubits. The hard part for the next decade is what you can do with 100 to 200 noisy ones.

People will push on several fronts at once. Qubit fidelities have already improved by several orders of magnitude over the previous decade or two. Better, lower-overhead error-correcting codes are in the works, and short of full recursive error correction there are error-mitigation tricks that might eke out a useful near-term speedup. The algorithms for simulating chemistry and materials are already dramatically more efficient than they were five years earlier. When Aaronson quotes scary numbers like circuit depth of a million, he hopes that because people will care enough, those numbers will come down.

Aaronson spends a lot of effort communicating the science and exposing what Fridman calls the natural charlatanism around the field. Quantum computing, he says, is a little like cryptocurrency or deep learning: there is a core of something genuinely revolutionary, and that core attracts a vast penumbra of utterly ridiculous claims. The main way people go astray is by not focusing on whether they are getting a speedup over a classical computer. Some of the same voices that dismiss supremacy for not being useful will talk up traffic routing and financial optimization, counting on nobody asking how well a classical computer could do the same thing.

Machine learning, AI, and optimization are the application areas companies, investors, and the popular press get most excited about. Even with a perfect, fault-tolerant, scalable quantum computer, the speedups we have known from the beginning are modest. Grover's algorithm can solve many of the problems that arise there, including NP-complete ones, in about the square root of the classical number of steps. A square-root speedup is important and not a game changer on the scale of Shor or of simulating quantum mechanics. In theory it might roughly double the size of the optimization problems you can handle. Because that sounded boring, people invented heuristic algorithms no one really understands, onto which you can project the hope of an exponential speedup you cannot disprove. A worrying amount of the case for building quantum computers now rests on that shaky ground.

Bigger machine-learning speedups might still appear; Aaronson calls that one of the biggest questions for the theory side. In 2016, Kerenidis and Prakash gave a recommendation-sampling algorithm, essentially the Netflix problem, exponentially faster than any known classical algorithm. Aaronson was excited. He gave an 18-year-old undergraduate, Ewin Tang, the project of proving that any classical algorithm would need exponentially more data. After a year she figured out why she could not: the claim was false. There is a classical algorithm with similar performance. She dequantized the quantum machine-learning algorithm, and in the following years a bunch of other proposed quantum ML algorithms were dequantized too. That is a backward step for quantum speedups and a forward step for science, with a silver lining of new classical algorithms. The field is now open to find a better example. What should not happen, he says, is companies and journalists pretending those speedups are already established.

Fridman closes with the absurd question of what gives life meaning. Aaronson offers three answers: trying to discover new things about the world and share them; his friends, family, kids, and students; and trying, when he can, to make the world better in small ways. It depresses him that he cannot do more while the world faces a climate crisis and resurgent authoritarianism, but he tries to stand against the things he finds horrible. Asked what makes him smile, he laughs and says the question itself.