Quantum vs. Classical, Computing vs. Physics
The relationship between classical and quantum is quite different in computing from what it is in physics.
The relationship between the classical approach and the quantum approach is quite different in computing from what it is in physics. In fact, the relationship between quantum computing and classical computing is not a simple issue at all.
In contrast, the relationship between quantum physics and classical physics is easy to understand. Essentially, quantum physics is a refinement of classical physics. At the risk of oversimplifying, we can summarize that classical physics is unable to explain certain problems that arise at very small scales. This inability of classical physics led to the quantum-physics revolution in the early 20th century. Quantum physics was able to accurately predict results in the microscopic domain on problems where classical physics gave wrong answers.
Importantly, quantum physics is also compatible with classical physics for situations where classical physics gives accurate predictions. Effectively, quantum physics is the model we use for certain microscopic concerns, and classical physics is the model we use for non-microscopic, everyday concerns. As we look at smaller and smaller entities of interest, the difference between the two approaches increases; correspondingly, as we look at larger and larger entitities of interest, the difference decreases and eventually disappears entirely. Classical physics is the preferred model for our everyday world because it’s easier to get answers – not because it produces different answers.
So quantum physics is a refinement or extension of classical physics. You might easily get the impression that quantum computing is a similar kind of refinement or extension of classical computing. Sometimes that’s even true… depending on what you mean by “classical computing!”
In this kind of quantum/classical discussion, there are at least three kinds of things that get muddled together as “classical computing:”
What computers are physically made of
What problems computers can or can’t solve
How efficiently computers can solve the solvable problems
Let’s take up each of these in turn.
First, let’s consider the materials and technologies that comprise a particular computer. Today’s off-the-shelf computers are entirely built with electronics: primarily, vast quantities of tiny transistors fabricated on modern integrated circuit “chips.” However, quantum computers are not built that way: there’s at least some part of a quantum computer that is using something different from conventional electronic parts.
Indeed, quantum computers are so different from electronic computers (in their input/output characteristics, and the operations that transform inputs to outputs) that it’s really quite hard to align them for comparison. One motivation for quantum computing is the idea of “quantum supremacy,” finding and solving particular problems with a quantum computer that would be impractical for even the fastest classical computer. Something striking about this kind of comparison is that most quantum computation problems don’t really have natural mappings onto electronic computers, and vice-versa. The comparison between styles of computing is a little like comparing a seagull to a salmon: there’s a layer at the top of the ocean where they both operate, but mostly their worlds are disjoint. If we were asked to be excited about “salmon supremacy,” we might well think that it’s missing the point to talk about whether bird or fish is “better.”
Importantly, it’s clear that the quantum implementation is a peer of the electronic “classical” implementation, rather than being some kind of superior or subordinate. In contrast to the relationship in physics, a quantum computer is emphatically not a refinement of this flavor of “classical computer.” Depending on the problem, a quantum computer might do better or worse than a classical computer. However, a quantum computer doesn’t somehow encompass all of the capabilities of a “classical” electronic computer, and more.
Now let’s consider the question of what problems computers can solve. In this context, “classical computing” is what professional computer scientists would call the theory of computability. Computability gives insight into what is computable, indeed what computation is. Here we discover that there’s nothing in the use of quantum physics that really changes computability. The “only” advantage that a quantum computer offers is the possibility of mind-boggling speedup on certain kinds of problems. Meanwhile, problems that are uncomputable in the classical theory (such as the halting problem) remain uncomputable, even with a quantum approach. Computability says that every quantum computer is Turing-equivalent to every other computer, in the sense that what is computable or uncomputable ignoring run time is identical.
Of course, in the real world we’re utterly uninterested in a computation that won’t finish in our lifetime (or perhaps even the universe’s lifetime) -- so that means there are a lot of important differences between classical and quantum that are not captured by the theory of computability. But it’s worth underscoring that in computability, the classical theory is still the universal one. There is no quantum variant, and in particular there is no theoretical advantage to considering the topic from a quantum perspective.
Finally, let’s consider the question of how efficiently a computer can solve a particular solvable problem. In this context, “classical computing” is what computer scientists would call the theory of computational complexity. Computational complexity gives insight into the relationship between the size of a computational problem being solved and the resources (time, space) that are required. If we extend this theory to include quantum computing capabilities, we will have an enlarged theory that enables us to sensibly compare the resource consumption patterns of conventionally-implemented algorithms with those of quantum algorithms. Such a comparison is at the heart of what people mean when they make claims about quantum supremacy. The relationship between classical computational complexity and quantum computational complexity is somewhat like the relationship between classical physics and quantum physics: the quantum aspects are extensions that can be added in as needed, or ignored when unneeded.
In summary:
If we’re talking about what computers are made of, classical and quantum are peers: different approaches to building computing machinery.
If we’re talking about the efficiency of solving a particular problem, quantum is a refinement or extension of classical.
And if we’re talking about whether a problem is solvable at all, the classical theory is universal: all quantum computers are still subject to the identical classical limits.