Thisglossary of quantum computing is a list of definitions of terms and concepts used inquantum computing, its sub-disciplines, and related fields.

Bacon–Shor code

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

BQP

Incomputational complexity theory, bounded-error quantum polynomial time (BQP) is the class ofdecision problems solvable by aquantum computer inpolynomial time, with an error probability of at most 1/3 for all instances.^[4] It is the quantum analogue to thecomplexity classBPP. A decision problem is a member of BQP if there exists aquantum algorithm (analgorithm that runs on a quantum computer) that solves the decision problemwith 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 aquantum state using only alogarithmic number ofmeasurements.^[5] Given an unknown state${\displaystyle \rho }$, atomographically complete set ofgates${\displaystyle U}$ (e.gClifford gates), a set of${\displaystyle M}$observables${\displaystyle \{O_i\}}$ and aquantum channel${\displaystyle M}$ (defined by randomly sampling from${\displaystyle U}$, applying it to${\displaystyle \rho }$ and measuring the resulting state); predict theexpectation values${\displaystyle \mathrm{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 fordirect fidelity estimation, entanglement verification, estimatingcorrelation functions, and predictingentanglement entropy.^[5]

Cloud-based quantum computing

is the invocation of quantumemulators,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 initiatingquantum physics into processing power and when users are allowed access to these quantum-powered computers through the internet it is known asquantum computing within the cloud.

Cross-entropy benchmarking

(also referred to as XEB), isquantum benchmarking protocol which can be used to demonstratequantum supremacy.^[8] In XEB, a randomquantum circuit is executed on a quantum computer multiple times in order to collect a set of${\displaystyle k}$ samples in the form ofbitstrings${\displaystyle \{x_1,\dots ,x_k\}}$. The bitstrings are then used to calculate the cross-entropy benchmark fidelity (${\displaystyle F_{\mathrm{X}\mathrm{E}\mathrm{B}}}$) via aclassical computer, given by

${\displaystyle F_{\mathrm{X}\mathrm{E}\mathrm{B}}=2^n⟨P(x_i){⟩}_k-1=\frac{2^n}{k}\left(\sum _{i=1}^k|⟨0^n|C|x_i⟩{|}^2\right)-1}$,

where${\displaystyle n}$ is the number ofqubits 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_{\mathrm{X}\mathrm{E}\mathrm{B}}=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 ano-go theorem that states: "Noquantum error correcting code can have acontinuous symmetry which acts transversely on physical qubits".^[11] In other words, no quantum error correcting code can transversely implement auniversal gate set. Since quantum computers are inherently noisy, quantum error correcting codes are used to correct errors that affect information due todecoherence. Decoding error corrected data in order to perform gates on the qubits makes it prone to errors. Fault tolerant quantum computation avoids this by performing gates on encoded data. Transversal gates, which perform a gate between two "logical" qubits each of which is encoded inN "physical qubits" by pairing up the physical qubits of each encoded qubit ("code block"), and performing independent gates on each pair, can be used to perform fault tolerant but not universal quantum computation because they guarantee that errors don't spread uncontrollably through the computation. This is because transversal gates ensure that each qubit in a code block is acted on by at most a single physical gate and each code block is corrected independently when an error occurs. Due to the Eastin–Knill theorem, a universal set like{H,S,CNOT,T} gates can't be implemented transversally. For example, theT gate can't be implemented transversely in theSteane code.^[12] This calls for ways ofcircumventing Eastin–Knill in order to perform fault tolerant quantum computation. In addition to investigating fault tolerant quantum computation, the Eastin–Knill theorem is also useful for studyingquantum gravity via theAdS/CFT correspondence and incondensed matter physics viaquantum reference frame^[13] ormany-body theory.^[14]

Five-qubit error correcting code

is the smallestquantum error correcting code that can protect alogical qubit from any arbitrary single qubit error.^[15] In this code, 5physical qubits are used to encode the logical qubit.^[16] With${\displaystyle X}$ and${\displaystyle Z}$ beingPauli matrices and${\displaystyle I}$ theIdentity matrix, this code'sgenerators are${\displaystyle ⟨XZZXI,IXZZX,XIXZZ,ZXIXZ⟩}$. Its logical operators are${\displaystyle \overline{X}=XXXXX}$ and${\displaystyle \overline{Z}=ZZZZZ}$.^[17] Once the logical qubit is encoded, errors on the physical qubits can be detected via stabilizer measurements. Alookup 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 arandom variable whoseexpected value is the expectedreal part${\displaystyle \mathrm{R}\mathrm{e}⟨\psi |U|\psi ⟩}$, where${\displaystyle |\psi ⟩}$ is a quantum state and${\displaystyle U}$ is aunitary gate acting on the space of${\displaystyle |\psi ⟩}$.^[19] The Hadamard test produces a random variable whoseimage is in${\displaystyle \{\pm 1\}}$ and whose expected value is exactly${\displaystyle \mathrm{R}\mathrm{e}⟨\psi |U|\psi ⟩}$. It is possible to modify the circuit to produce a random variable whose expected value is${\displaystyle \mathrm{I}\mathrm{m}⟨\psi |U|\psi ⟩}$.^[19]

Magic state distillation

is a process that takes in multiple noisyquantum states and outputs a smaller number of more reliable quantum states. It is considered by many experts^[20] to be one of the leading proposals for achievingfault tolerantquantum computation. Magic state distillation has also been used to argue^[21] thatquantum contextuality may be the "magic ingredient" responsible for the power of quantum computers.^[22]

Mølmer–Sørensen gate

(or MS gate), is a twoqubitgate used intrapped ionquantum computing. It was proposed byKlaus Mølmer and Anders Sørensen.^[23] Their proposal also extends to gates on more than two qubits.

Quantum algorithm

is analgorithm which runs on a realistic model ofquantum computation, the most commonly used model being thequantum circuit model of computation.^[24][25] A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classicalcomputer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on aquantum 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 asquantum superposition orquantum entanglement.

Quantum computing

is a type ofcomputation whose operations can harness the phenomena ofquantum mechanics, such assuperposition,interference, andentanglement. Devices that perform quantum computations are known as quantum computers.^[27][28] Though current quantum computers are too small to outperform usual (classical) computers for practical applications, larger realizations are believed to be capable of solving certaincomputational problems, such asinteger factorization (which underliesRSA encryption), substantially faster than classical computers. The study of quantum computing is a subfield ofquantum information science.

Quantum volume

is a metric that measures the capabilities and error rates of aquantum computer. It expresses the maximum size of squarequantum 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 inquantum computing to protectquantum information from errors due todecoherence and otherquantum noise. Quantum error correction is theorised as essential to achievefault-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 usingquantum computing orquantum information processing to create and work withquantum images.^[29][30]Due to some of the properties inherent to quantum computation, notablyentanglement andparallelism, 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 ofassembling sequences of instructions, called quantum programs, that are capable of running on aquantum computer. Quantumprogramming languages help expressquantum algorithms using high-level constructs.^[32] The field is deeply rooted in theopen-source philosophy and as a result most of the quantum software discussed in this article is freely available asopen-source software.^[33]

Quantum simulator

Quantum simulators permit the study ofquantum system in a programmable fashion. In this instance, simulators are special purpose devices designed to provide insight about specificphysics 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

Inquantum 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 somePOVM${\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)=\mathrm{tr}(E_i{\sigma }_j)}$, it follows that the probability of successfully determining the correct state is${\displaystyle P_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}}=\sum _i{p}_i\mathrm{tr}({\sigma }_i{E}_i)}$.^[37]

Quantum supremacy

orquantum 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 thecomputational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has asuperpolynomial speedup over the best known or possible classical algorithm for that task.^[41][42] The term was coined byJohn Preskill in 2012,^[43][44] but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back toYuri Manin's (1980)^[45] andRichard Feynman's (1981) proposals of quantum computing.^[46] Examples of proposals to demonstrate quantum supremacy include theboson sampling proposal ofAaronson and Arkhipov,^[47]D-Wave's specialized frustrated cluster loop problems,^[48] and sampling the output of randomquantum circuits.^[49][50]

Quantum Turing machine

(QTM), or universal quantum computer, is anabstract machine used to model the effects of aquantum computer. It provides a simple model that captures all of the power of quantum computation—that is, anyquantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalentquantum circuit is a more common model.^{[51][52]: 2}

Qubit

A qubit (/ˈkjuːbɪt/) orquantum bit is a basic unit ofquantum information—the quantum version of the classic binarybit physically realized with a two-state device. A qubit is atwo-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include thespin of the electron in which the two levels can be taken as spin up and spin down; or thepolarization of a singlephoton 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 coherentsuperposition of both states simultaneously, a property that is fundamental toquantum mechanics andquantum computing.

Quil (instruction set architecture)

is aquantuminstruction set architecture that first introduced a shared quantum/classical memory model. It was introduced by Robert Smith, Michael Curtis, and William Zeng inA Practical Quantum Instruction Set Architecture.^[43] Manyquantum algorithms (includingquantum teleportation,quantum error correction, simulation,^[53][54] and optimization algorithms^[55]) require ashared memory architecture. Quil is being developed for the superconducting quantum processors developed byRigetti Computing through the Forestquantum programming API.^[56][57] APython library calledpyQuil was introduced to develop Quil programs with higher level constructs. A Quilbackend is also supported by other quantum programming environments.^[58][59]

Qutrit

(orquantum trit), is a unit ofquantum information that is realized by a 3-level quantum system, that may be in asuperposition of three mutually orthogonalquantum states.^[60]The qutrit is analogous to the classicalradix-3trit, just as thequbit, a quantum system described by a superposition of two orthogonal states, is analogous to the classical radix-2bit.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-qubitquantum gates generates adensesubset ofSU(2) then that set is guaranteed to fill SU(2) quickly, which means any desired gate can be approximated by a fairly short sequence of gates from the generating set.Robert M. Solovay initially announced the result on an email list in 1995, andAlexei Kitaev independently gave an outline of its proof in 1997.^[62] Solovay also gave a talk on his result atMSRI in 2000 but it was interrupted by a fire alarm.^[63] Christopher M. Dawson andMichael Nielsen call the theorem one of the most important fundamental results in the field ofquantum computation.^[64]

• Models of computation
• Quantum cryptography
• Information theory
• Computational complexity theory
• Classes of computers
• Theoretical computer science
• Open problems
• Glossaries of technology

• CS1 maint: multiple names: authors list
• Wikipedia articles incorporating text from the National Institute of Standards and Technology
• CS1 Russian-language sources (ru)
• Articles with short description
• Short description with empty Wikidata description
• CS1 maint: location missing publisher
• Wikipedia glossaries using description lists