View source for Quantum circuit

{{Short description|Model of quantum computing}}
{{more footnotes needed|date=October 2015}}
[[File:Quantum teleportation circuit.svg|300px|thumb|right|Circuit that performs [[Quantum teleportation|teleportation]] of a qubit.<ref>{{Cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac|date=2010|publisher=[[Cambridge University Press]]|isbn=978-1-10700-217-3|location=Cambridge|oclc=43641333|author-link=Michael Nielsen|author-link2=Isaac Chuang|url=https://www.cambridge.org/9781107002173|pages=26–28}}</ref> This circuit consists of both [[quantum gate]]s and [[Measurement in quantum mechanics|measurements]]. Measurement is a quantum phenomenon that does not occur in [[Circuit (computer science)|classical circuits]].]]
In [[quantum information theory]], a '''quantum circuit''' is a [[Model of computation|model]] for [[quantum computation]], similar to [[Circuit (computer science)|classical circuits]], in which a computation is a sequence of [[quantum gate]]s, [[Measurement in quantum mechanics|measurements]], initializations of [[qubit]]s 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 as [[DiVincenzo'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 classical [[bit]]s. 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.<ref name="Williams">{{cite book|author=Colin P. Williams |year=2011 |title=Explorations in Quantum Computing |publisher=[[Springer Science+Business Media|Springer]] |isbn=978-1-84628-887-6|pages=123–200}}</ref><ref name="Nielsen-Chuang">{{Cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac|date=2010|publisher=[[Cambridge University Press]]|isbn=978-1-10700-217-3|location=Cambridge|oclc=43641333|author-link=Michael Nielsen|author-link2=Isaac Chuang|url=https://www.cambridge.org/9781107002173|pages=171–215}}</ref><ref name="Oemer">{{cite thesis|last=Ömer |first=Bernhard |date=2000-01-20 |title=Quantum Programming in QCL|publisher=Institute for Theoretical Physics, Vienna University of Technology|url=http://tph.tuwien.ac.at/~oemer/doc/quprog.pdf |pages=37–38 |access-date=2021-10-12}}</ref>

The graphical depiction of quantum circuit elements is described using a variant of the [[Penrose graphical notation]].{{citation needed|date=October 2021}} [[Richard Feynman]] used an early version of the quantum circuit notation in 1986.<ref name="feynman">{{cite journal | last=Feynman | first=Richard P. | title=Quantum mechanical computers | journal=Foundations of Physics | publisher=Springer Science and Business Media LLC | volume=16 | issue=6 | year=1986 | issn=0015-9018 | doi=10.1007/bf01886518 | pages=507–531| bibcode=1986FoPh...16..507F | s2cid=122076550 }}</ref>

== Reversible classical logic gates ==
Most elementary [[logic gate]]s of a classical computer are not [[Reversible computing|reversible]]. Thus, for instance, for an [[AND 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 physical [[entropy]]. A reversible gate is a reversible function on  ''n''-bit data that returns  ''n''-bit data,  where an ''n''-bit data is a [[string (computer science)|string]] of bits ''x''<sub>1</sub>,''x''<sub>2</sub>, ...,''x''<sub>''n''</sub>  of length  ''n''.   The set of ''n''-bit data is the space {0,1}<sup>''n''</sup>, which consists of 2<sup>''n''</sup> strings of 0's and 1's.

More precisely: an ''n''-bit reversible gate is a [[bijective]] mapping ''f'' from the set {0,1}<sup>''n''</sup> of ''n''-bit data onto itself.
An example of such a reversible gate ''f'' is a mapping that applies a fixed permutation to its inputs.
For reasons of practical engineering, one typically studies gates only for small values of ''n'', e.g. ''n''=1, ''n''=2 or ''n''=3.  These gates can be easily described by tables.

== Quantum logic gates ==
The [[quantum logic gate]]s are [[reversible computation|reversible]] [[unitary transformation]]s on at least one qubit. Multiple qubits taken together are referred to as [[quantum register]]s. To define quantum gates, we first need to specify the quantum replacement of an ''n''-bit datum. The ''quantized version'' of classical ''n''-bit space {0,1}<sup>''n''</sup> is the [[Hilbert space]]

:<math>H_{\operatorname{QB}(n)}= \ell^2(\{0,1\}^n).</math>

This is by definition the space of complex-valued functions on {0,1}<sup>''n''</sup> and is naturally an [[inner product space]]. <math>\ell^2</math> means the function is a [[square-integrable function]]. This space can also be regarded as consisting of [[linear combination]]s, or [[Quantum superposition|superposition]]s, of classical bit strings. Note that  ''H''<sub>QB(''n'')</sub> is a vector space over the [[complex number]]s of [[dimension]] 2<sup>''n''</sup>. The elements of this [[vector space]] are the possible state-vectors of ''n''-[[qubit]] quantum registers.

Using Dirac [[bra-ket|ket]] notation, if ''x''<sub>1</sub>,''x''<sub>2</sub>, ...,''x''<sub>''n''</sub> is a classical bit string, then 
:<math> | x_1, x_2, \cdots,x_n \rangle \quad </math>
is a special  ''n''-qubit register corresponding to the function which maps this classical bit string to 1 and maps all other bit strings to 0; these 2<sup>''n''</sup> special ''n''-qubit registers are called ''computational basis states''. All ''n''-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 a [[unitarity (physics)|unitary]] mapping, that is, a linear transformation of a complex [[inner product space]] that preserves the [[Hermitian inner product]].  An ''n''-qubit (reversible) quantum gate is a [[unitary operators|unitary mapping]] ''U'' from the space  ''H''<sub>QB(''n'')</sub> of ''n''-qubit registers onto itself.

Typically, we are only interested in gates for small values of ''n''.

A reversible ''n''-bit classical logic gate gives rise to a reversible ''n''-bit quantum gate as follows:  to each reversible ''n''-bit logic gate ''f''  corresponds a quantum gate ''W''<sub>''f''</sub> defined as follows:
:<math> W_f( | x_1, x_2, \cdots,x_n \rangle) = |f(x_1, x_2, \cdots, x_n) \rangle. </math>
Note that ''W''<sub>''f''</sub> permutes the computational basis states.

Of particular importance is the controlled NOT gate (also called [[Controlled NOT gate|CNOT]] gate) ''W''<sub>CNOT</sub> defined on a quantized 2 qubit.  Other examples of quantum logic gates derived from classical ones are the [[Toffoli gate]] and the [[Fredkin 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 the [[Quantum logic gate#Phase shift gates|phase shift operator]]:
:<math> P(\varphi) =\begin{bmatrix} 1 & 0 \\ 0 & e^{i\varphi} \end{bmatrix}, </math>
so 
:<math> P(\varphi)| 0 \rangle =   | 0 \rangle \quad P(\varphi)| 1 \rangle = e^{i\varphi}| 1 \rangle. </math>

== Reversible logic circuits ==
{{main|reversible computing}}

Again, we consider first ''reversible'' classical computation.  Conceptually, there is no difference between a reversible ''n''-bit  circuit and a reversible ''n''-bit logic gate: either one is just an invertible function on the space of ''n'' 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 reversible ''n''-bit gate ''f'' and  a reversible  ''m''-bit gate ''g''.  Putting them together means producing a new circuit by connecting some set of ''k'' outputs of ''f'' to some set of ''k'' inputs of ''g'' as in the figure below.  In that figure, ''n''=5, ''k''=3 and ''m''=7. The resulting circuit is also reversible and operates on ''n''+''m''&minus;''k'' bits.

[[Image:Reversible circuit composition.svg|center|175px]]

We will refer to this scheme as a ''classical assemblage'' (This concept corresponds to a technical definition in [[Alexei Kitaev|Kitaev]]'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 that  ''intermediate'' "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.<ref name="Ryan O’Donnell">{{cite web|url=https://www.cs.cmu.edu/~odonnell/quantum15/QuantumComputationScribeNotesByRyanODonnellAndJohnWright.pdf|title=Introduction to the Quantum Circuit Model}}</ref>

Now it is possible to show that the [[Toffoli gate]] is a universal gate. This means that given any reversible classical ''n''-bit circuit ''h'', we can construct a classical assemblage of Toffoli gates in the above manner to produce an  (''n''+''m'')-bit circuit ''f'' such that
:<math> f(x_1, \ldots, x_n, \underbrace{0, \dots, 0}) = (y_1, \ldots, y_n, \underbrace{0, \ldots , 0})</math>
where there are ''m'' underbraced zeroed inputs and 
:<math>(y_1, \ldots, y_n) = h(x_1, \ldots, x_n)</math>.
Notice that the result always has a string of ''m'' zeros as the [[ancilla (quantum computing)|ancilla]] 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 function ''f'' (bijective or not) can be simulated by a circuit of Toffoli gates. Obviously, if the mapping fails to be [[injective]], 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 any ''classical assemblage'' as above, we can produce a reversible quantum circuit when in place of ''f'' we have an ''n''-qubit gate ''U'' and in place of ''g'' we have an ''m''-qubit gate ''W''. See illustration below:

[[Image:Quantum circuit composition.svg|center|300px]]

The fact that connecting gates this way gives rise to a unitary mapping on ''n''+''m''&minus;''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 where [[decoherence]] may occur.

There are also [[Quantum gate#Universal quantum gates|universality theorem]]s for certain sets of well-known gates; such a universality theorem exists, for instance, for the pair consisting of the single qubit phase gate ''U''<sub>θ</sub> mentioned above (for a suitable value of θ), together with the 2-qubit [[controlled NOT gate|CNOT gate]] ''W''<sub>CNOT</sub>. However, the universality theorem for the quantum case is somewhat weaker than the one for the classical case; it asserts only that any reversible ''n''-qubit circuit can be ''approximated'' arbitrarily well by circuits assembled from these two elementary gates. Note that there are [[uncountable|uncountably]] many possible single qubit phase gates, one for every possible angle θ, so they cannot all be represented by a finite circuit constructed from {''U''<sub>θ</sub>, ''W''<sub>CNOT</sub>}.

== Quantum computations ==

So far we have not shown how quantum circuits are used to perform computations.  Since many important numerical problems reduce to computing a unitary transformation ''U'' on a finite-dimensional space (the celebrated [[discrete Fourier transform]] 
being a prime example), one might expect that some quantum circuit could be designed to carry out the transformation ''U''. In principle, one needs only to prepare an ''n'' qubit state ψ as an appropriate superposition of computational basis states for the input and measure the output ''U''ψ.  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 are ''probabilistic''.

We now provide a mathematical model for how quantum circuits can simulate
''probabilistic'' but classical computations.  Consider an ''r''-qubit circuit ''U'' with
register space ''H''<sub>QB(''r'')</sub>. ''U'' is thus a unitary map
:<math>H_{\operatorname{QB}(r)} \rightarrow
H_{\operatorname{QB}(r)}.</math>

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

* An ''input register'' ''X'' = {0,1}<sup>''m''</sup> of ''m'' (classical) bits.
* An ''output register'' ''Y'' = {0,1}<sup>''n''</sup> of ''n'' (classical) bits.

The contents ''x'' = ''x''<sub>1</sub>, ..., ''x''<sub>''m''</sub> of
the classical input register are used to initialize the qubit
register in some way.  Ideally, this would be done with the computational basis
state 
:<math> |\vec{x},0\rangle= | x_1, x_2, \cdots, x_{m}, \underbrace{0, \dots, 0} \rangle, </math>
where there are ''r''-''m'' underbraced zeroed inputs.  Nevertheless,
this perfect initialization is completely unrealistic.  Let us assume
therefore that the initialization is a mixed state given by some density operator ''S'' which is near the idealized input in some appropriate metric, e.g.
:<math> \operatorname{Tr}\left(\big||\vec{x},0\rangle \langle \vec{x},0 | - S\big|\right) \leq \delta. </math>

Similarly, the output register space is related to the qubit register, by a ''Y''
valued observable ''A''. Note that observables in quantum mechanics are usually defined in
terms of ''projection valued measures'' on '''R'''; if the variable
happens to be discrete, the projection valued measure reduces to a
family {E<sub>λ</sub>} indexed on some parameter λ
ranging over a countable set.  Similarly, a ''Y'' valued observable,
can be associated with a family of pairwise orthogonal projections
{E<sub>''y''</sub>} indexed by elements of ''Y''.  such that
:<math> I = \sum_{y \in Y} \operatorname{E}_y. </math>

Given a mixed state ''S'', there corresponds a probability measure on ''Y''
given by 
:<math> \operatorname{Pr}\{y\} = \operatorname{Tr}(S \operatorname{E}_y ). </math>

The function ''F'':''X'' → ''Y'' is computed by a circuit
''U'':''H''<sub>QB(''r'')</sub> → ''H''<sub>QB(''r'')</sub> to within ε if and only if
for all bitstrings ''x'' of length ''m''
:<math>\left\langle \vec{x},0 \big| U^* \operatorname{E}_{F(x)} U
\big|\vec{x},0 \right\rangle = \left\langle \operatorname{E}_{F(x)} U( |\vec{x},0\rangle) \big|  U( |\vec{x},0\rangle) \right\rangle \geq 1 - \epsilon.</math>

Now 
:<math> \left| \operatorname{Tr} (S U^* \operatorname{E}_{F(x)} U) - \left\langle \vec{x},0 \big| U^* \operatorname{E}_{F(x)} U
\big|\vec{x},0 \right\rangle\right|\leq \operatorname{Tr} (\big||\vec{x},0\rangle \langle \vec{x},0 | - S\big|) \| U^* \operatorname{E}_{F(x)} U \| \leq \delta </math>
so that
:<math>\operatorname{Tr} (S U^* \operatorname{E}_{F(x)} U) \geq 1 - \epsilon - \delta.</math>

'''Theorem'''.  If  ε + δ < 1/2, then  the probability distribution 
:<math> \operatorname{Pr}\{y\} = \operatorname{Tr} (S U^* \operatorname{E}_{y} U)</math>
on ''Y'' can be used to determine ''F''(''x'') with an arbitrarily  small probability of error by majority sampling, for a sufficiently large sample size. Specifically, take ''k'' independent samples from the probability distribution Pr on ''Y'' and choose a value on which more than half of the samples agree. The probability that the value ''F''(''x'') is sampled more than ''k''/2 times is at least
:<math> 1 - e^{- 2 \gamma^2 k}, </math>
where γ = 1/2 - ε - δ.

This follows by applying the [[Chernoff bound]].

==Accelerating Quantum Computing Simulations with FPGAs==
With the advent of quantum computing, there has been a significant surge in both the number of developers and available tools.<ref>{{cite web | url=https://medium.com/@josephmeng96/accelerating-quantum-simulations-w-fpgas-84b09569ad0f | title=Accelerating Quantum Simulations w/ FPGAs | date=19 August 2020 }}</ref> However, the slow pace of technological advancement and the high maintenance costs associated with quantum computers have limited broader participation in this field. In response, developers have turned to simulators, such as IBM's [[Qiskit]], to model quantum behavior without relying solely on real quantum hardware. Nevertheless, simulators, being classical computers, are constrained by computation speed. The fundamental advantage of quantum computers lies in their ability to process qubits, leveraging properties like entanglement and superposition simultaneously. By running quantum simulations on classical computers, the inherent parallelism of quantum computing is taken away. Moreover, as the number of simulated qubits increases, the simulation's speed decreases proportionally.

In a quantum circuit, the vectors are used to represent the state of the qubits and different matrices are used to represent the gate that is applied on the qubits. Since linear algebra is a major component of the quantum simulation, Field Programmable Gate Arrays ([[FPGAs]]) could be used to accelerate the simulation of quantum computing. FPGA is a kind of hardware that excels at executing operations in parallel, supports pipelining, has on-chip memory resources with low access latency, and offers the flexibility to reconfigure the hardware architecture on-the-fly which make it a well suited tool to handle matrix multiplication. 

The main idea of accelerating quantum computing simulations is to offload some of the heavy computation to special hardware like FPGA in order to speed up the whole simulation process. And the bigger quantum circuits (more qubits and more gates) we simulate, the more speedup we gain from offloading to FPGA compared with software simulations on CPU. The data flow of the simulation is explained below. First, the user inputs all the information of the quantum circuit including initial state and various gates through the user interface. Then, all this information is compressed and sent to the FPGA through some hardware communication protocols like AXI. Then, all the information is stored in the on-chip memory in the FPGA. And the simulation starts when the data is read from the memory and sent to the Matrix multiplication module. After all the calculation is done, the result will be sent back to the memory and to the CPU. 

Suppose we are simulating 5-qubit circuits, then we need to store the vector that holds 32 (2⁵) 16-bit values, each of which represents the square-root probability of a possible existing state. We also need to store the 32x32 matrix that represents the gate. In order to parallel this computation, we can store the 32 rows of the matrix separately and replicate 32 row_vec_mult hardware such that each row can calculate the multiplication in parallel. This will dramatically speed up the simulation with a price of more hardware and memory usage in FPGA. <ref>{{cite web | url=https://medium.com/@josephmeng96/accelerating-quantum-simulations-w-fpgas-84b09569ad0f | title=Accelerating Quantum Simulations w/ FPGAs | date=19 August 2020 }}</ref>

It has been discovered that with careful hardware design, it's possible to achieve a hardware architecture with O(n) time complexity, where 'n' denotes the number of qubits. In contrast, the runtime of Numpy approaches O(2^2^n). This finding underscores the feasibility of leveraging FPGAs to accelerate quantum computing simulations. <ref>{{cite web | url=https://medium.com/@josephmeng96/accelerating-quantum-simulations-w-fpgas-84b09569ad0f | title=Accelerating Quantum Simulations w/ FPGAs | date=19 August 2020 }}</ref>

==See also==
{{Commons category |Quantum circuit}}
* [[Abstract index notation]]
* [[Angular momentum diagrams (quantum mechanics)]]
* [[Circuit complexity]] and [[BQP]]
* [[Matrix product state]] uses [[Penrose graphical notation]]
* [[Quantum register]]
* [[Spin network]]s
* [[Trace diagram]]

== References ==
{{Reflist}}
*{{citation
 | last1 = Biham | first1 = Eli | author1-link = Eli Biham
 | last2 = Brassard | first2 = Gilles | author2-link = Gilles Brassard
 | last3 = Kenigsberg | first3 = Dan
 | last4 = Mor | first4 = Tal
 | arxiv = quant-ph/0306182
 | doi = 10.1016/j.tcs.2004.03.041
 | issue = 1
 | journal = Theoretical Computer Science
 | mr = 2060181
 | pages = 15–33
 | title = Quantum computing without entanglement
 | volume = 320
 | year = 2004| s2cid = 295103 }}.
*{{citation
 | last1 = Freedman | first1 = Michael H. | author1-link = Michael Freedman
 | last2 = Kitaev | first2 = Alexei | author2-link = Alexei Kitaev
 | last3 = Larsen | first3 = Michael J. | author3-link = Michael J. Larsen
 | last4 = Wang | first4 = Zhenghan
 | arxiv = quant-ph/0101025
 | doi = 10.1090/S0273-0979-02-00964-3
 | issue = 1
 | journal = Bulletin of the American Mathematical Society
 | mr = 1943131
 | pages = 31–38
 | title = Topological quantum computation
 | volume = 40
 | year = 2003}}.
*{{citation
 | last = Hirvensalo | first = Mika
 | isbn = 3-540-66783-0
 | location = Berlin
 | mr = 1931238
 | publisher = Springer-Verlag
 | series = Natural Computing Series
 | title = Quantum Computing
 | year = 2001}}.
*{{citation
 | last = Kitaev | first = A. Yu. | author-link = Alexei Kitaev
 | doi = 10.1070/RM1997v052n06ABEH002155
 | issue = 6(318)
 | journal = Uspekhi Mat. Nauk
 | language = ru
 | mr = 1611329
 | pages = 53–112
 | title = Quantum computations: algorithms and error correction
 | volume = 52
 | year = 1997|bibcode = 1997RuMaS..52.1191K | s2cid = 250816585 }}.
*{{citation
 | last1 = Nielsen | first1 = Michael A. | author1-link = Michael Nielsen
 | last2 = Chuang | first2 = Isaac L.
 | isbn = 0-521-63235-8
 | location = Cambridge
 | mr = 1796805
 | publisher = Cambridge University Press
 | title = Quantum Computation and Quantum Information
 | year = 2000}}.

==External links==
*[https://cquic.unm.edu/resources/ Q-circuit] {{Webarchive|url=https://web.archive.org/web/20190323101451/https://cquic.unm.edu/resources/ |date=2019-03-23 }} is a macro package for drawing quantum circuit diagrams in LaTeX.
*[https://qcsimulator.github.io/ Quantum Circuit Simulator (Davy Wybiral)] ({{GitHub|qcsimulator/qcsimulator.github.io}}) a browser-based quantum circuit diagram editor and simulator.
*[https://www.quantumplayground.net/ Quantum Computing Playground] ({{GitHub|gwroblew/Quantum-Computing-Playground}}) a browser-based quantum scripting environment.
*[https://algassert.com/quirk Quirk - Quantum Circuit Toy] ({{GitHub|Strilanc/Quirk}}) a browser-based quantum circuit diagram editor and simulator.

{{Electronic components}}
{{Quantum computing}}
{{Quantum mechanics topics}}
{{emerging technologies|quantum=yes|other=yes}}

[[Category:Quantum information science]]
[[Category:Models of computation]]