Glossary of quantum computing

This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.

Bacon–Shor code

is a Subsystem error correcting code.^[1] In a Subsystem code, information is encoded in a subsystem of a Hilbert space. Subsystem codes lend to simplified error correcting procedures unlike codes which encode information in the subspace of a Hilbert space.^[2] This simplicity led to the first demonstration of fault tolerant circuits on a quantum computer.^[3]

BQP

In

polynomial time, with an error probability of at most 1/3 for all instances.^[4] It is the quantum analogue to the complexity class BPP. A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability

and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3.

Classical shadow

is a protocol for predicting functions of a

measurements.^[5]

Given an unknown state ${\displaystyle \rho }$, a tomographically complete set of gates ${\displaystyle U}$ (e.g Clifford gates), a set of ${\displaystyle M}$ observables ${\displaystyle \{O_{i}\}}$ and a quantum channel ${\displaystyle M}$ (defined by randomly sampling from ${\displaystyle U}$, applying it to ${\displaystyle \rho }$ and measuring the resulting state); predict the expectation values ${\displaystyle \operatorname {tr} (O_{i}\rho )}$.^[6] A list of classical shadows ${\displaystyle S}$ is created using ${\displaystyle \rho }$, ${\displaystyle U}$ and ${\displaystyle M}$ by running a Shadow generation algorithm. When predicting the properties of ${\displaystyle \rho }$, a Median-of-means estimation algorithm is used to deal with the outliers in ${\displaystyle S}$.^[7] Classical shadow is useful for direct fidelity estimation, entanglement verification, estimating correlation functions, and predicting entanglement entropy.^[5]

Cloud-based quantum computing

is the invocation of quantum

simulators or processors through the cloud. Increasingly, cloud services are being looked on as the method for providing access to quantum processing. Quantum computers achieve their massive computing power by initiating quantum physics into processing power and when users are allowed access to these quantum-powered computers through the internet it is known as quantum computing

within the cloud.

Cross-entropy benchmarking

(also referred to as XEB), is

quantum benchmarking protocol which can be used to demonstrate quantum supremacy.^[8] In XEB, a random quantum circuit

is executed on a quantum computer multiple times in order to collect a set of ${\displaystyle k}$ samples in the form of

bitstrings

${\displaystyle \{x_{1},\dots ,x_{k}\}}$. The bitstrings are then used to calculate the cross-entropy benchmark fidelity (${\displaystyle F_{\rm {XEB}}}$) via a classical computer, given by

${\displaystyle F_{\rm {XEB}}=2^{n}\langle P(x_{i})\rangle _{k}-1={\frac {2^{n}}{k}}\left(\sum _{i=1}^{k}|\langle 0^{n}|C|x_{i}\rangle |^{2}\right)-1}$,

where ${\displaystyle n}$ is the number of qubits in the circuit and ${\displaystyle P(x_{i})}$ is the probability of a bitstring ${\displaystyle {x_{i}}}$ for an ideal quantum circuit ${\displaystyle C}$. If ${\displaystyle F_{XEB}=1}$, the samples were collected from a noiseless quantum computer. If ${\displaystyle F_{\rm {XEB}}=0}$, then the samples could have been obtained via random guessing.^[9] This means that if a quantum computer did generate those samples, then the quantum computer is too noisy and thus has no chance of performing beyond-classical computations. Since it takes an exponential amount of resources to classically simulate a quantum circuit, there comes a point when the biggest supercomputer that runs the best classical algorithm for simulating quantum circuits can't compute the XEB. Crossing this point is known as achieving quantum supremacy; and after entering the quantum supremacy regime, XEB can only be estimated.^[10]

Eastin–Knill theorem

is a

many-body theory.^[14]

Five-qubit error correcting code

is the smallest quantum error correcting code that can protect a logical qubit from any arbitrary single qubit error.^[15] In this code, 5 physical qubits are used to encode the logical qubit.^[16] With ${\displaystyle X}$ and ${\displaystyle Z}$ being Pauli matrices and ${\displaystyle I}$ the Identity matrix, this code's generators are ${\displaystyle \langle XZZXI,IXZZX,XIXZZ,ZXIXZ\rangle }$. Its logical operators are ${\displaystyle {\bar {X}}=XXXXX}$ and ${\displaystyle {\bar {Z}}=ZZZZZ}$.^[17] Once the logical qubit is encoded, errors on the physical qubits can be detected via stabilizer measurements. A lookup table that maps the results of the stabilizer measurements to the types and locations of the errors gives the control system of the quantum computer enough information to correct errors.^[18]

Hadamard test (quantum computation)

is a method used to create a

real part

${\displaystyle \mathrm {Re} \langle \psi |U|\psi \rangle }$, where ${\displaystyle |\psi \rangle }$ is a quantum state and ${\displaystyle U}$ is a

unitary gate

acting on the space of ${\displaystyle |\psi \rangle }$.^[19] The Hadamard test produces a random variable whose image is in ${\displaystyle \{\pm 1\}}$ and whose expected value is exactly ${\displaystyle \mathrm {Re} \langle \psi |U|\psi \rangle }$. It is possible to modify the circuit to produce a random variable whose expected value is ${\displaystyle \mathrm {Im} \langle \psi |U|\psi \rangle }$.^[19]

Magic state distillation

is a process that takes in multiple noisy

quantum computation. Magic state distillation has also been used to argue ^[21] that quantum contextuality may be the "magic ingredient" responsible for the power of quantum computers.^[22]

Mølmer–Sørensen gate

(or MS gate), is a two

trapped ion quantum computing. It was proposed by Klaus Mølmer and Anders Sørensen.^[23]

Their proposal also extends to gates on more than two qubits.

Quantum algorithm

is an

quantum computer. Although all classical algorithms can also be performed on a quantum computer,^[26]: 126 the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement

.

Quantum computing

is a type of

RSA encryption), substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science

.

Quantum volume

is a metric that measures the capabilities and error rates of a quantum computer. It expresses the maximum size of square quantum circuits that can be implemented successfully by the computer. The form of the circuits is independent from the quantum computer architecture, but compiler can transform and optimize it to take advantage of the computer's features. Thus, quantum volumes for different architectures can be compared.

Quantum error correction

(QEC), is used in

fault-tolerant quantum computation

that can reduce the effects of noise on stored quantum information, faulty quantum gates, faulty quantum preparation, and faulty measurements.

Quantum image processing

(QIMP), is using

quantum information processing to create and work with quantum images.^[29][30]

Due to some of the properties inherent to quantum computation, notably entanglement and parallelism, it is hoped that QIMP technologies will offer capabilities and performances that surpass their traditional equivalents, in terms of computing speed, security, and minimum storage requirements.^[30][31]

Quantum programming

is the process of

open-source software.^[33]

Quantum simulator

Quantum simulators permit the study of

quantum system in a programmable fashion. In this instance, simulators are special purpose devices designed to provide insight about specific physics problems.^[34][35][36] Quantum simulators may be contrasted with generally programmable "digital" quantum computers

, which would be capable of solving a wider class of quantum problems.

Quantum state discrimination

In quantum information science, quantum state discrimination refers to the task of inferring the quantum state that produced the observed measurement probabilities. More precisely, in its standard formulation, the problem involves performing some POVM ${\displaystyle (E_{i})_{i}}$ on a given unknown state ${\displaystyle \rho }$, under the promise that the state received is an element of a collection of states ${\displaystyle \{\sigma _{i}\}_{i}}$, with ${\displaystyle \sigma _{i}}$ occurring with probability ${\displaystyle p_{i}}$, that is, ${\displaystyle \rho =\sum _{i}p_{i}\sigma _{i}}$. The task is then to find the probability of the POVM ${\displaystyle (E_{i})_{i}}$ correctly guessing which state was received. Since the probability of the POVM returning the ${\displaystyle i}$-th outcome when the given state was ${\displaystyle \sigma _{j}}$ has the form ${\displaystyle {\text{Prob}}(i|j)=\operatorname {tr} (E_{i}\sigma _{j})}$, it follows that the probability of successfully determining the correct state is ${\displaystyle P_{\rm {success}}=\sum _{i}p_{i}\operatorname {tr} (\sigma _{i}E_{i})}$.^[37]

Quantum supremacy

or quantum advantage, is the goal of demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time (irrespective of the usefulness of the problem).^[38][39][40] Conceptually, quantum supremacy involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has a superpolynomial speedup over the best known or possible classical algorithm for that task.^[41][42] The term was coined by John Preskill in 2012,^[43][44] but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's (1980)^[45] and Richard Feynman's (1981) proposals of quantum computing.^[46] Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov,^[47] D-Wave's specialized frustrated cluster loop problems,^[48] and sampling the output of random quantum circuits.^[49][50]

Quantum Turing machine

(QTM), or universal quantum computer, is an

quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.^[51][52]

^: 2

Qubit

A qubit (/ˈkjuːbɪt/) or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two states can be taken to be the vertical polarization and the horizontal polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of both states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.

Quil (instruction set architecture)

is a

backend is also supported by other quantum programming environments.^[58][59]

Qutrit

(or quantum trit), is a unit of

quantum states.^[60]

The qutrit is analogous to the classical

trit, just as the qubit, a quantum system described by a superposition of two orthogonal states, is analogous to the classical radix-2 bit

. There is ongoing work to develop quantum computers using qutrits and qubits with multiple states.[61]

Solovay–Kitaev theorem

In quantum information and computation, the Solovay–Kitaev theorem says, roughly, that if a set of single-

MSRI in 2000 but it was interrupted by a fire alarm.^[63] Christopher M. Dawson and Michael Nielsen call the theorem one of the most important fundamental results in the field of quantum computation.^[64]