This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(October 2015) (Learn how and when to remove this message)

Inquantum information theory, aquantum circuit is amodel forquantum computation, similar toclassical circuits, in which a computation is a sequence ofquantum gates,measurements, initializations ofqubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known asDiVincenzo's criteria.

Circuits are written such that the horizontal axis is time, starting at the left hand side and ending at the right. Horizontal lines are qubits, doubled lines represent classicalbits. The items that are connected by these lines are operations performed on the qubits, such as measurements or gates. These lines define the sequence of events, and are usually not physical cables.^[2][3][4]

The graphical depiction of quantum circuit elements is described using a variant of thePenrose graphical notation.^{[citation needed]}Richard Feynman used an early version of the quantum circuit notation in 1986.^[5]

Most elementarylogic gates of a classical computer are notreversible. Thus, for instance, for anAND gate one cannot always recover the two input bits from the output bit; for example, if the output bit is 0, we cannot tell from this whether the input bits are 01 or 10 or 00.

However, reversible gates in classical computers are easily constructed for bit strings of any length; moreover, these are actually of practical interest, since irreversible gates must always increase physicalentropy. A reversible gate is a reversible function onn-bit data that returnsn-bit data, where ann-bit data is astring of bitsx₁,x₂, ...,x_n of lengthn. The set ofn-bit data is the space {0,1}ⁿ, which consists of 2ⁿ strings of 0's and 1's.

More precisely: ann-bit reversible gate is abijective mappingf from the set {0,1}ⁿ ofn-bit data onto itself.An example of such a reversible gatef is a mapping that applies a fixed permutation to its inputs.For reasons of practical engineering, one typically studies gates only for small values ofn, e.g.n=1,n=2 orn=3. These gates can be easily described by tables.

Thequantum logic gates arereversibleunitary transformations on at least one qubit. Multiple qubits taken together are referred to asquantum registers. To define quantum gates, we first need to specify the quantum replacement of ann-bit datum. Thequantized version of classicaln-bit space {0,1}ⁿ is theHilbert space

${\displaystyle H_{\mathrm{QB}(n)}={\ell }^2(\{0,1{\}}^n).}$

This is by definition the space of complex-valued functions on {0,1}ⁿ and is naturally aninner product space.${\displaystyle {\ell }^2}$ means the function is asquare-integrable function. This space can also be regarded as consisting oflinear combinations, orsuperpositions, of classical bit strings. Note thatH_QB(n) is a vector space over thecomplex numbers ofdimension 2ⁿ. The elements of thisvector space are the possible state-vectors ofn-qubit quantum registers.

Using Diracket notation, ifx₁,x₂, ...,x_n is a classical bit string, then

${\displaystyle |x_1,x_2,\cdots ,x_n⟩}$

is a specialn-qubit register corresponding to the function which maps this classical bit string to 1 and maps all other bit strings to 0; these 2ⁿ specialn-qubit registers are calledcomputational basis states. Alln-qubit registers are complex linear combinations of these computational basis states.

Quantum logic gates, in contrast to classical logic gates, are always reversible. One requires a special kind of reversible function, namely aunitary mapping, that is, a linear transformation of a complexinner product space that preserves theHermitian inner product. Ann-qubit (reversible) quantum gate is aunitary mappingU from the spaceH_QB(n) ofn-qubit registers onto itself.

Typically, we are only interested in gates for small values ofn.

A reversiblen-bit classical logic gate gives rise to a reversiblen-bit quantum gate as follows: to each reversiblen-bit logic gatef corresponds a quantum gateW_f defined as follows:

${\displaystyle W_f(|x_1,x_2,\cdots ,x_n⟩)=|f(x_1,x_2,\cdots ,x_n)⟩.}$

Note thatW_f permutes the computational basis states.

Of particular importance is the controlled NOT gate (also calledCNOT gate)W_CNOT defined on a quantized 2 qubit. Other examples of quantum logic gates derived from classical ones are theToffoli gate and theFredkin gate.

However, the Hilbert-space structure of the qubits permits many quantum gates that are not induced by classical ones. For example, a relative phase shift is a 1 qubit gate given by multiplication by thephase shift operator:

so

${\displaystyle P(\phi )|0⟩=|0⟩P(\phi )|1⟩=e^{i\phi }|1⟩.}$

Again, we consider firstreversible classical computation. Conceptually, there is no difference between a reversiblen-bit circuit and a reversiblen-bit logic gate: either one is just an invertible function on the space ofn bit data. However, as mentioned in the previous section, for engineering reasons we would like to have a small number of simple reversible gates, that can be put together to assemble any reversible circuit.

To explain this assembly process, suppose we have a reversiblen-bit gatef and a reversiblem-bit gateg. Putting them together means producing a new circuit by connecting some set ofk outputs off to some set ofk inputs ofg as in the figure below. In that figure,n=5,k=3 andm=7. The resulting circuit is also reversible and operates onn+m−k bits.

We will refer to this scheme as aclassical assemblage (This concept corresponds to a technical definition inKitaev's pioneering paper cited below). In composing these reversible machines, it is important to ensure that the intermediate machines are also reversible. This condition assures thatintermediate "garbage" is not created (the net physical effect would be to increase entropy, which is one of the motivations for going through this exercise).

Note that each horizontal line on the above picture represents either 0 or 1, not these probabilities. Since quantum computations are reversible, at each 'step' the number of lines must be the same number of input lines. Also, each input combination must be mapped to a single combination at each 'step'. This means that each intermediate combination in a quantum circuit is a bijective function of the input.^[6]

Now it is possible to show that theToffoli gate is a universal gate. This means that given any reversible classicaln-bit circuith, we can construct a classical assemblage of Toffoli gates in the above manner to produce an (n+m)-bit circuitf such that

${\displaystyle f(x_1,\dots ,x_n,\underbrace{0,\dots ,0})=(y_1,\dots ,y_n,\underbrace{0,\dots ,0})}$

where there arem underbraced zeroed inputs and

${\displaystyle (y_1,\dots ,y_n)=h(x_1,\dots ,x_n)}$.

Notice that the result always has a string ofm zeros as theancilla bits. No "rubbish" is ever produced, and so this computation is indeed one that, in a physical sense, generates no entropy. This issue is carefully discussed in Kitaev's article.

More generally, any functionf (bijective or not) can be simulated by a circuit of Toffoli gates. Obviously, if the mapping fails to beinjective, at some point in the simulation (for example as the last step) some "garbage" has to be produced.

For quantum circuits a similar composition of qubit gates can be defined. That is, associated to anyclassical assemblage as above, we can produce a reversible quantum circuit when in place off we have ann-qubit gateU and in place ofg we have anm-qubit gateW. See illustration below:

The fact that connecting gates this way gives rise to a unitary mapping onn+m−k qubit space is easy to check. In a real quantum computer the physical connection between the gates is a major engineering challenge, since it is one of the places wheredecoherence may occur.

There are alsouniversality theorems for certain sets of well-known gates; such a universality theorem exists, for instance, for the pair consisting of the single qubit phase gateU_θ mentioned above (for a suitable value of θ), together with the 2-qubitCNOT gateW_CNOT. However, the universality theorem for the quantum case is somewhat weaker than the one for the classical case; it asserts only that any reversiblen-qubit circuit can beapproximated arbitrarily well by circuits assembled from these two elementary gates. Note that there areuncountably many possible single qubit phase gates, one for every possible angle θ, so they cannot all be represented by a finite circuit constructed from {U_θ,W_CNOT}.

So far we have not shown how quantum circuits are used to perform computations. Since many important numerical problems reduce to computing a unitary transformationU on a finite-dimensional space (the celebrateddiscrete Fourier transform being a prime example), one might expect that some quantum circuit could be designed to carry out the transformationU. In principle, one needs only to prepare ann qubit state ψ as an appropriate superposition of computational basis states for the input and measure the outputUψ. Unfortunately, there are two problems with this:

• One cannot measure the phase of ψ at any computational basis state so there is no way of reading out the complete answer. This is in the nature of measurement in quantum mechanics.
• There is no way to efficiently prepare the input state ψ.

This does not prevent quantum circuits for the discrete Fourier transform from being used as intermediate steps in other quantum circuits, but the use is more subtle. In fact quantum computations areprobabilistic.

We now provide a mathematical model for how quantum circuits can simulateprobabilistic but classical computations. Consider anr-qubit circuitU withregister spaceH_QB(r).U is thus a unitary map

${\displaystyle H_{\mathrm{QB}(r)}\to H_{\mathrm{QB}(r)}.}$

In order to associate this circuit to a classical mapping on bitstrings, we specify

• Aninput registerX = {0,1}^m ofm (classical) bits.
• Anoutput registerY = {0,1}ⁿ ofn (classical) bits.

The contentsx =x₁, ...,x_m ofthe classical input register are used to initialize the qubitregister in some way. Ideally, this would be done with the computational basisstate

${\displaystyle |\overrightarrow{x},0⟩=|x_1,x_2,\cdots ,x_m,\underbrace{0,\dots ,0}⟩,}$

where there arer-m underbraced zeroed inputs. Nevertheless,this perfect initialization is completely unrealistic. Let us assumetherefore that the initialization is a mixed state given by some density operatorS which is near the idealized input in some appropriate metric, e.g.

${\displaystyle \mathrm{Tr}\left(||\overrightarrow{x},0⟩⟨\overrightarrow{x},0|-S|\right)\le \delta .}$

Similarly, the output register space is related to the qubit register, by aYvalued observableA. Note that observables in quantum mechanics are usually defined interms ofprojection valued measures onR; if the variablehappens to be discrete, the projection valued measure reduces to afamily {E_λ} indexed on some parameter λranging over a countable set. Similarly, aY valued observable,can be associated with a family of pairwise orthogonal projections{E_y} indexed by elements ofY. such that

${\displaystyle I=\sum _{y\in Y}{\mathrm{E}}_y.}$

Given a mixed stateS, there corresponds a probability measure onYgiven by

${\displaystyle \mathrm{Pr}\{y\}=\mathrm{Tr}(S{\mathrm{E}}_y).}$

The functionF:X →Y is computed by a circuitU:H_QB(r) →H_QB(r) to within ε if and only iffor all bitstringsx of lengthm

${\displaystyle ⟨\overrightarrow{x},0|U^{\ast }{\mathrm{E}}_{F(x)}U|\overrightarrow{x},0⟩=⟨{\mathrm{E}}_{F(x)}U(|\overrightarrow{x},0⟩)|U(|\overrightarrow{x},0⟩)⟩\ge 1-ϵ.}$

Now

${\displaystyle \left|\mathrm{Tr}(S{U}^{\ast }{\mathrm{E}}_{F(x)}U)-⟨\overrightarrow{x},0|U^{\ast }{\mathrm{E}}_{F(x)}U|\overrightarrow{x},0⟩\right|\le \mathrm{Tr}(||\overrightarrow{x},0⟩⟨\overrightarrow{x},0|-S|)\Vert U^{\ast }{\mathrm{E}}_{F(x)}U\Vert \le \delta }$

so that

${\displaystyle \mathrm{Tr}(S{U}^{\ast }{\mathrm{E}}_{F(x)}U)\ge 1-ϵ-\delta .}$

Theorem. If ε + δ < 1/2, then the probability distribution

${\displaystyle \mathrm{Pr}\{y\}=\mathrm{Tr}(S{U}^{\ast }{\mathrm{E}}_{y}U)}$

onY can be used to determineF(x) with an arbitrarily small probability of error by majority sampling, for a sufficiently large sample size. Specifically, takek independent samples from the probability distribution Pr onY and choose a value on which more than half of the samples agree. The probability that the valueF(x) is sampled more thank/2 times is at least

${\displaystyle 1-e^{-2{\gamma }^{2}k},}$

where γ = 1/2 - ε - δ.

This follows by applying theChernoff bound.

Wikimedia Commons has media related toQuantum circuit.

• Abstract index notation
• Angular momentum diagrams (quantum mechanics)
• Circuit complexity andBQP
• Matrix product state usesPenrose graphical notation
• Quantum register
• Spin networks
• Trace diagram

• Biham, Eli;Brassard, Gilles; Kenigsberg, Dan; Mor, Tal (2004), "Quantum computing without entanglement",Theoretical Computer Science,320 (1):15–33,arXiv:quant-ph/0306182,doi:10.1016/j.tcs.2004.03.041,MR 2060181,S2CID 295103.
• Freedman, Michael H.;Kitaev, Alexei;Larsen, Michael J.; Wang, Zhenghan (2003), "Topological quantum computation",Bulletin of the American Mathematical Society,40 (1):31–38,arXiv:quant-ph/0101025,doi:10.1090/S0273-0979-02-00964-3,MR 1943131.
• Hirvensalo, Mika (2001),Quantum Computing, Natural Computing Series, Berlin: Springer-Verlag,ISBN 3-540-66783-0,MR 1931238.
• Kitaev, A. Yu. (1997), "Quantum computations: algorithms and error correction",Uspekhi Mat. Nauk (in Russian),52 (6(318)):53–112,Bibcode:1997RuMaS..52.1191K,doi:10.1070/RM1997v052n06ABEH002155,MR 1611329,S2CID 250816585.
• Nielsen, Michael A.; Chuang, Isaac L. (2000),Quantum Computation and Quantum Information, Cambridge: Cambridge University Press,ISBN 0-521-63235-8,MR 1796805.

• Q-circuitArchived 2019-03-23 at theWayback Machine is a macro package for drawing quantum circuit diagrams in LaTeX.
• Quantum Circuit Simulator (Davy Wybiral) (qcsimulator.github.io onGitHub) a browser-based quantum circuit diagram editor and simulator.
• Quantum Computing Playground (Quantum-Computing-Playground onGitHub) a browser-based quantum scripting environment.
• Quirk - Quantum Circuit Toy (Quirk onGitHub) a browser-based quantum circuit diagram editor and simulator.

• Quantum information science
• Models of computation

• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from October 2015
• All articles lacking in-text citations
• All articles with unsourced statements
• Articles with unsourced statements from October 2021
• Commons category link is on Wikidata
• CS1 Russian-language sources (ru)
• Webarchive template wayback links