**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

# I

Glossary

**Abstraction**—A different model (a representation or way of thinking) about a computer system design that allows the user to focus on the critical aspects of the system components to be designed.

**Adiabatic quantum computer**—An idealized analog universal quantum computer that operates at 0 K (absolute zero). It is known to have the same computational power as a gate-based quantum computer.

**Algorithm**—A specific approach, often described in mathematical terms, used by a computer to solve a certain problem or carry out a certain task.

**Analog computer**—A computer whose operation is based on analog signals and that does not use Boolean logic operations and does not reject noise.

**Analog quantum computer**—A quantum computer that carries out a computation without breaking the operations down to a small set of primitive operations (gates) on qubits; there is currently no model of full fault tolerance for such machines.

**Analog signal**—A signal whose value varies smoothly within a range of real or complex numbers.

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

**Asymmetric cryptography** (also **public key cryptography**)—A category of cryptography where the system uses public keys that are widely known and private keys that are secret to the owner; such systems are commonly used for key exchange protocols in the encryption of most of today’s electronic communications.

**Basis**—Any set of linearly independent vectors that span their vector space. The wave function of a qubit or system of qubits is commonly written as a linear combination of basis functions or states. For a single qubit, the most common basis is {| 0⟩, | 1⟩}, corresponding to the states of a classical bit.

**Binary representation**—A series of binary digits where each digit has only two possible values, 0 or 1, used to encode data and upon which machine-level computations are performed.

**Certificate authority**—An entity that issues a digital certificate to certify the ownership of a public key used in online transactions.

**Cipher**—An approach to concealing the meaning of information by encoding it.

**Ciphertext**—The encrypted form of a message, which appears scrambled or nonsensical.

**Classical attack**—An attempt by a classical computer to break or subvert encryption.

**Classical computer**—A computer—for example, one of the many deployed commercially today—whose processing of information is not based upon quantum information theory.

**Coding theory**—The science of designing encoding schemes for specific applications—for example, to enable two parties to communicate over a noisy channel.

**Coherence**—The quality of a quantum system that enables quantum phenomena such as interference, superposition, and entanglement. Mathematically speaking, a quantum system is coherent when the complex coefficients of the contributing quantum states are clearly defined in relation to each other, and the system can be expressed in terms of a single wave function.

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

**Collapse**—The phenomenon that occurs upon measurement of a quantum system where the system reverts to a single observable state, resulting in the loss of contributions from all other states to the system’s wave function.

**Collision**—In hashing, the circumstance where two different inputs are mapped to the same output, or hash value.

**Complexity class**—A category that is used to define and group computational tasks according to their complexity.

**Computational complexity**—The difficulty of carrying out a specific computational task, typically expressed as a mathematical expression that reflects how the number of steps required to complete the task varies with the size of the input to the problem.

**Compute depth**—The number of sequential operations required to carry out a given task.

**Concatenation**—The ordered combination of two sequences in order. In the context of quantum error correction (QEC), this refers to carrying out two or more QEC protocols sequentially.

**Control and measurement plane**—An abstraction used to describe components of a quantum computer, which refers to the elements required to carry out operations on qubits and to measure their states.

**Control processor plane**—An abstraction used to describe components of a quantum computer, which includes the classical processor responsible for determining what signals and measurements are required to implement a quantum program.

**Cryostat**—A device that regulates the temperature of a physical system at very low temperatures, generally in an experimental laboratory.

**Cryptanalysis**—The use of a computer to defeat encryption.

**Cryptography**—The study and practice of encoding information in order to obfuscate its content that relies upon the difficulty of solving certain mathematical problems.

**Cryptosystem**—A method of deploying a specific cryptographic algorithm to protect data and communications from being read by an unintended recipient.

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

**Decoherence**—A process where a quantum system will ultimately exchange some energy and information with the broader environment over time, which cannot be recovered once lost. This process is one source of error in qubit systems. Mathematically speaking, decoherence occurs when the relationship between the coefficients of a quantum system’s contributing states become ill-defined.

**Decryption algorithm**—A set of instructions for returning an encrypted message to its unencrypted form. Such an algorithm takes as input a cipher text and its encryption key, and returns a cleartext, or readable, version of the message.

**Digital gate**—A transistor circuit that performs a binary operation using a number of binary single bit inputs to create a single-bit binary output.

**Digital quantum computer**—A quantum system where the computation is done by using a small set of primitive operations, or gates, on qubits.

**Digital signature**—An important cryptographic mechanism used to verify data integrity.

**Dilution refrigerator**—A specialized cooling device capable of maintaining an apparatus at temperatures near absolute zero.

**Discrete-log problem on elliptic curves**—A specific algebraic problem used as the basis of a specific cryptographic protocol where, given the output, it is computationally hard to compute the inputs.

**Distance**—In an error-correcting code, the number of bit errors that would be required to convert one valid state of a computer to another. When the number of errors is less than (D–1)/2, one can still extract the error-free state.

**Encryption**—The application of cryptography to protect information, currently widely used in computer systems and Internet communications.

**Encryption algorithm**—A set of instructions for converting understandable data to an incomprehensible cipher, or ciphertext. In practice, the algorithm takes as input the message to be encrypted along with an encryption key and scrambles the message according to a mathematical procedure.

**Entanglement**—The property where two or more quantum objects in a system are correlated, or intrinsically linked, such that measurement of

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

one changes the possible measurement outcomes for another, regardless of how far apart the two objects are.

**Error-corrected quantum computer**—An instance of a quantum computer that emulates an ideal, fault-tolerant quantum computer by running a quantum error correction algorithm.

**Fault tolerant**—Resilient against errors.

**Fidelity**—The quality of a hardware operation, sometimes quantified in terms of the probability that a particular operation will be carried out correctly.

**Fundamental noise**—Noise resulting from energy fluctuations arising spontaneously within any object that is above absolute zero in temperature.

**Gate**—A computational operation that takes in and puts out one or more bits (in the case of a classical computer) or qubits (in the case of a quantum computer).

**Gate synthesis**—Construction of a gate out of a series of simpler gates.

**Hamiltonian**—A mathematical representation of the energy environment of a physical system. In the mathematics of quantum mechanics, a Hamiltonian takes the form of a linear algebraic operator. Sometimes, the term is used to denote the physical environment itself, rather than its mathematical representation.

**Host processor**—An abstraction used to describe the components of a quantum computing system, referring to the classical computer components driving the part of the system that is user controlled.

**Key exchange**—A step in cryptographic algorithms and protocols where keys are shared among intended recipients to enable their use in encrypting and decrypting information.

**Logical qubit**—An abstraction that describes a collection of physical qubits implementing quantum error correction in order to carry out a fault-tolerant qubit operation.

**Logic gate**—In classical computing, a collection of transistors that input and output digital signals, and that can be represented and modeled using Boolean logic (rules that combine signals that can be either false, 0, or true, 1).

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

**Lossless**—No energy is dissipated.

**Measurement**—Observation of a quantum system, which yields only a single classical output and collapses the system’s wave function onto the corresponding state.

**Microprocessor**—An integrated circuit that contains the elements of a central processing unit on a single chip.

**Noise**—Unwanted variations in a physical system that can lead to error and unwanted results.

**Noise immunity**—The ability to remove noise (unwanted variations) in a signal to minimize error.

**Noisy intermediate-scale quantum (NISQ) computer**—A quantum computer that is not error-corrected, but is stable enough to effectively carry out a computation before the system loses coherence. A NISQ can be digital or analog.

**Nondeterministic polynomial time (NP)**—A specific computational complexity class.

**One-way functions**—Functions that are easy to compute in one direction while being for all intents and purposes impossible to compute in the other direction.

**Overhead**—The amount of work (for example, number of operations) or quantity of resources (for example, number of qubits or bits) required to carry out a computational task; “cost” is sometimes used synonymously.

**Post-quantum cryptography**—The set of methods for cryptography that are expected to be resistant to cryptanalysis by a quantum computer.

**Primitive**—A fundamental computational operation.

**Program**—An abstraction that refers to the sequence of instructions and rules that a computer must perform in order to complete one or more tasks (or solve one or more tasks) using a specific approach, or algorithm.

**Quantum annealer**—An analog quantum computer that operates through coherent manipulation of qubits by changing the analog values of the system’s Hamiltonian, rather than by using quantum gates. In particular, a

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

quantum annealer performs computations by preparing a set of qubits in some initial state and changing their energy environment until it defines the parameters of a given problem, such that the final state of the qubits corresponds, with a high probability, to the answer of the problem. In general, a quantum annealer is not necessarily universal—there are some problems that it cannot solve.

**Quantum communication**—The transport or exchange of information as encoded into a quantum system.

**Quantum computation**—The use of quantum mechanical phenomena such as interference, superposition, and entanglement to perform computations that are roughly analogous to (although operate quite differently from) those performed on a classical computer.

**Quantum computer**—The general term for a device (whether theoretical or practically realized) that carries out quantum computation. A quantum computer may be analog or gate-based, universal or not, and noisy or fault tolerant.

**Quantum cryptography**—A subfield of quantum communication where quantum properties are used to design communication systems that may not be eavesdropped upon by an observer.

**Quantum information science**—The study of how information is or can be encoded in a quantum system, including the associated statistics, limitations, and unique affordances of quantum mechanics.

**Quantum interference**—When states contributing to coherent superpositions combine constructively or destructively, like waves, with coefficients adding or subtracting.

**Quantum sensing and metrology**—The study and development of quantum systems whose extreme sensitivity to environmental disturbances can be exploited in order to measure important physical properties with more precision than is possible with classical technologies.

**Quantum system**—A collection of (typically very small) physical objects whose behavior cannot be adequately approximated by equations of classical physics.

**Qubit**—A quantum bit, the fundamental hardware component of a quantum computer, embodied by a quantum object. Analogous to a classical

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

bit (or binary digit), a qubit can represent a state corresponding to either zero or one; unlike a classical bit, a qubit can also exist in a superposition of both states at once, with any possible relative contribution of each. In a quantum computer, qubits are generally entangled, meaning that any qubit’s state is inextricably linked to the state of the other qubits, and thus cannot be defined independently.

**Run time**—The amount of time required to carry out a computational task. In practice, the actual time required for a task depends heavily on the design of a device and of its particular physical embodiment, so run time may be described in terms of the number of computational steps.

**Scalable, fault-tolerant, universal gate-based quantum computer**—A system that operates through gate-based operations on qubits, analogous to circuit-based classical computers, and uses quantum error correction to correct any system noise (including errors introduced by imperfect control signals, or unintended coupling of qubits to each other or to the environment) that occurs during the time frame of the calculation.

**SHA256**—A specific hash function that outputs a 256-bit hash value regardless of the input size.

**Shor’s algorithm**— A quantum algorithm developed by Peter Shor in the 1990s that, if implemented on a real quantum computer of sufficient scale, would be capable of breaking the encryption used to protect Internet communications and data.

**Signal**—An electromagnetic field used to convey information in an electronic circuit.

**Software tool**—A computer program that helps a user design and compose a new computer program.

**Standard cell library**—A set of predesigned and tested logic gates.

**Superposition**—A quantum phenomenon where a system is in more than one state at a time. Mathematically speaking, the wave function of a quantum system in a superposition state is expressed as the sum of the contributing states, each weighted by a complex coefficient.

**Surface code**—A quantum error correction code (QECC) that is less sensitive to noise than other established QECCs, but has higher overheads.

**Suggested Citation:**"Appendix I: Glossary." National Academies of Sciences, Engineering, and Medicine. 2019.

*Quantum Computing: Progress and Prospects*. Washington, DC: The National Academies Press. doi: 10.17226/25196.

**Symmetric encryption**—A type of encryption where a secret key, shared by both the sender and the receiver, is used to encrypt and decrypt communications.

**Systematic noise**—Noise resulting from signal interactions that is always present under certain conditions and could in principle be modeled and corrected.

**Transport Layer Security (TLS) handshake**—The most common key exchange protocol, used to protect Internet traffic.

**Unitary operation**—An algebraic operation on a vector that preserves the vector length.

**Universal computer**—A computer that can perform any computation that could be performed by a Turing machine.

**Wave function**—A mathematical description of the state of a quantum system, so named to reflect their wave-like characteristics.

**Wave-particle duality**—The phenomenon where a quantum object is sometimes best described in terms of wave-like properties and sometimes in terms of particle-like properties.