Definitions and Glossary of Quantum Computing Terms
Extract from Deloitte Insights: Technology, Media, and Telecommunications Predictions 2019 and reproduced with the permission of Duncan Stewart, Director of Research and Erica Pretorius, Partner, Risk Advisory, Deloitte Canada.
Classical computer: The traditional form of binary digital electronic computing device, almost always running on silicon semiconductor transistor and integrated-circuit hardware.
Quantum computer (QC): A computer that uses quantum-mechanical phenomena, such as superposition and entanglement, to perform its calculations. Various (more than 10) contending physical implementations are being tried, many of which require ultra-low temperatures. It is not clear at this time which physical implementation will triumph. Quantum computers are not better than classical computers at everything; they can offer spectacular speedups for certain tasks, but do no better at others, or could even be worse.
Superposition and entanglement: This is the secret sauce of how quantum computers do what they do … but it is not necessary to understand these terms to understand quantum computing’s likely market size and timing of commercial availability. For those who wish to know more about superposition and entanglement, many online articles explain them.
Quantum supremacy or superiority: Both terms are used more or less interchangeably to denote the point at which a quantum computer will be able to perform a certain task that no classical computer can execute in a practical amount of time or using a practical amount of resources. It is critical to note that just because a QC has demonstrated supremacy for one problem does not mean that it is superior for all other—or even any other—problems. There are different degrees by which a QC can provide speeds greater than a classical computer (see the below entries on quadratic and exponential speedups).
Quantum advantage: Although quantum supremacy is an important theoretical milestone, it is possible that it will be for a computing problem that is of no or little practical importance. Therefore, many believe that quantum advantage will be the more important breakthrough: when a quantum computer can perform a certain useful task that no classical computer can solve in a practical amount of time or using a practical amount of resources
Quadratic speedup: There are certain computational problems, such as searching an unordered list[i], where a QC would outperform a classical computer by a quadratic amount: If it takes a classical computer N steps to run the process, the QC can do it in √N. (Grover’s algorithm is the most famous example of a technique that QCs could use to show a quadratic speedup.) For example, if a given calculation would take 365 days on a classical computer, it would take only 19.1 days on a QC. However, there are few real-world computing tasks done today that take a year, so it is more realistic to say that, if a computation takes eight hours on a classical machine, then it could be done in less than three hours on a QC. That may be a big enough speedup to justify using a quantum computer that costs millions of dollars and requires specialists to run and program it … or it might not. The business case for using a QC when the speedup is only quadratic is not always compelling.
Exponential speedup: The real case for QCs comes when they provide an exponential speedup, as is the case for certain problems such as breaking public key encryption or simulating chemical and biological systems. If a classical machine would take nine billion years to crack a public key by brute force, a quadratic speedup that reduces the calculation time to 3 billion years is not useful. But an exponential speedup that cracks the code in minutes, or even seconds, is potentially transformative. However, it is unclear just how often QCs will be able to offer exponential speedups. Only a small number of problems are known today where QCs would offer exponential speedups, but optimists note that more will become known over time.
Physical qubit: Any two-level quantum-mechanical system can be used as a qubit. These systems include, but are not limited to, photons, electrons, atomic nuclei, atoms, ions, quantum dots, and superconducting electronic circuits. As of 2018, most large QCs use either superconducting qubits or trapped ion technologies.
Logical qubit: A logical qubit uses multiple unreliable physical qubits to produce one reliable logical qubit that is both fault-tolerant and error-corrected. As of 2018, no one has built a logical qubit. The assumption is that a large number of physical qubits will be required to make a logical qubit; the current consensus is that hundreds or even thousands of physical qubits will be required. Large numbers of logical qubits are necessary for a universal or general QC that can solve a wide range of problems.
Noisy Intermediate Scale Quantum (NISQ) computing: Although a device composed of hundreds of logical qubits is the ultimate goal, devices with large numbers of physical qubits are likely to have some commercially interesting uses. These could be thought of as single-task QCs or simulators.
According to a leading quantum researcher, Dr. John Preskill, “The 100-qubit quantum computer will not change the world right away—[but] we should regard it as a significant step toward the more powerful quantum technologies of the future[ii].”
Quantum simulation: The subjects of certain problems, such as chemical processes, molecular dynamics, and the electronic properties of materials, are actually quantum systems. Classical computers are notoriously ill-suited to performing simulations of quantum systems, and they must rely on crude approximations. Since QCs are also governed by the rules of quantum mechanics, they are well-suited to performing efficient simulations of other quantum systems.
Simulation of quantum computers by classical computers: Everything that can be done by today’s early-stage QCs can be also be done about as quickly on a classical machine simulating quantum computing. Many researchers believe that, at some specific number of physical qubits, a classical machine will be unable to match the QC device—the achievement of quantum supremacy. The twist, however, is that the technology behind the classical simulation of quantum devices is advancing more or less as quickly as the number of physical qubits in QCs is growing. In 2017, when the state of the art was a 20-physical-qubit machine, it was thought that a classical machine could match a 42-physical-qubit QC—but not a 48-physical-qubit QC—for a particular problem. In 2018, as machines with more physical qubits were in development, a mathematical advance was made that showed that a classical computer could now match the 48-physical-qubit device via simulation. So, at least for that specific problem, the “supremacy bar” has been raised, and supremacy will likely not be achieved without a 60-physical-qubit QC. But the supremacy bar cannot be raised indefinitely: For a classical computer merely to store the mathematical representation of a modestly sized (100-qubit) QC would require a hard drive made of all the atoms in the universe!
[i] Scott Aaronson, “When exactly do quantum computers provide a speedup?,” PowerPoint presentation, MIT, accessed October 18, 2018.
[ii] John Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2 (2018): p. 79, DOI: https://doi. org/10.22331/q-2018-08-06-79.