Quantum circuit

Quantum circuit

In quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of reversible transformations on a quantum mechanical analog of an "n" bit register. This analogous structure is referred to as an "n"-qubit register.

Reversible logic gates

Ordinarily, in a classical computer, the logic gates other than the NOT gate are not reversible. Thus, for instance, for an AND gate one cannot generally recover the two input bits from the output bit; the case "both" input bits are 1 is the exception. However, as a first step in describing a quantum computing device it is instructive to observe that reversible gates are theoretically possible; moreover, these are actually of practical interest, since they do not increase entropy. A reversible gate is a reversible function on "n"-bit data that returns "n"-bit data, where an "n"-bit datum is a string of bits "x"1,"x"2, ...,"x""n" of length "n". The set of "n"-bit data is the space {0,1}"n".

* An "n"-bit reversible gate is a bijective mapping "f" from the set {0,1}"n" of "n"-bit data to itself.

In fact we are only interested in maps "f" which are different from the identity, and for reasons of practical engineering we are only interested in gates for small values of "n", e.g. "n"=1, "n"=2 or "n"=3. These gates can be easily described by tables. Examples of these logic gates which have been studied are the controlled NOT gate (also called CNOT gate), the Toffoli gate and the Fredkin gate.

To consider 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}"n" is

:H_{operatorname{QB}(n)}= ell^2({0,1}^n).

This is by definition the space of complex-valued functions on {0,1}"n" and is naturally an inner product space. This space can also be regarded as consisting of linear superpositions of classical bit strings.

Using Dirac ket notation, if "x"1,"x"2, ...,"x""n" is a classical bit string, then : | x_1, x_2, cdots,x_n angle quad is an "n"-qubit; these special "n"-qubits (of which there are 2"n") are called "computational basis states". All "n"-qubits are complex linear combinations of computational basis states. Note that "H"QB("n") has complex dimension 2"n".

For a quantum computer we are also interested in reversible gates, but this time we are interested in unitary mappings, that is those that preserve the inner product on "H"QB("n").

* An "n"-qubit reversible gate is a unitary mapping "U" from the space "H"QB("n") of qubits of size "n" onto itself.

Again we are only interested in unitary operators "U" which are different from the identity and we are only interested in gates for small values of "n". In fact, reversible classical "n"-bit logic gates give rise to reversible "n"-bit quantum gates as follows: to each reversible n-bit logic gate "f" corresponds a quantum gate "W""f" defined as follows:: W_f( | x_1, x_2, cdots,x_n angle) = |f(x_1, x_2, cdots, x_n) angle. Of particular importance is the quantized 2 qubit CNOT gate "W"CNOT. Of course there are many other, properly quantum gates. For example, a relative phase shift is a 1 qubit gate given by multiplication by the unitary matrix:: U_ heta =egin{bmatrix} e^{i heta} & 0 \ 0 & 1 end{bmatrix}, so : U_ heta | 0 angle = e^{i heta} | 0 angle quad U_ heta | 1 angle = | 1 angle.

Reversible circuits

Again we consider first "reversible" classical computation. Conceptually there is no difference between a reversible "n" bit circuit and a reversible "n" bit logical gate: it is just an invertible function on the space of "n" bit data. However, as we mentioned in the previous section, for engineering reasons we would like to have a small number of 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 "k" < "n" of the 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" -"k" bits.



We will refer to this scheme as a "classical assemblage"; (Remark: this concept corresponds to a technical definition in Kitaev's pioneering paper cited below.) In composing these reversible machines, it is important to insure 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). 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: f(x_1, ldots, x_n, underbrace{0, dots, 0}) = (y_1, ldots, y_n, underbrace{0, ldots , 0})where there are "m" underbraced zeroed inputs and : (y_1, ldots, y_n) = h(x_1, ldots, x_n) Notice that at the end result has always a string of "m" zeros as the 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.

It follows immediately from this result that 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:

The fact that connecting gates this way gives rise to a unitary mapping on "n"+"m" -"k" qubit space is an easy check, which should not concern the non-expert reader. It should also be noted that 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 actually occur.

There is also a universality theorem for sets of well known gates; such a universality theorem exists for instance, for the pair consisting of the single qubit phase gate "U"θ mentioned above for some reasonable value of θ together with the 2 qubit CNOT gate "W"CNOT). However the universality theorem is somewhat weaker in the case of quantum computation, namely that any reversible "n" qubit circuit can be "approximated" arbitrarily well by circuits assembled from these two elementary gates. Note that there are uncountably many possible single qubit phase gates, one for every possible angle θ, so uncountably many of these gates cannot be represented by any finite circuit constructed from {"U"θ, "W"CNOT)}.

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 a "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" withregister space "H"QB("r"). "U" is thus a unitary
H_{operatorname{QB}(r)} ightarrowH_{operatorname{QB}(r)}.

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

* An "input register" "X" = {0,1}"m" of "m" (classical) bits.

* An "output register" "Y" = {0,1}"n" of "n" (classical) bits.

The contents "x" = "x"1, ..., "x""m" ofthe classical input register are used to initialize the qubitregister in some way. Ideally, this would be done with the computational basisstate : |vec{x},0 angle= | x_1, x_2, cdots, x_n, underbrace{0, dots, 0} angle where there are "r"-"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 operator "S" which is near the idealized input in some appropriate metric, e.g.: operatorname{Tr}left(ig||vec{x},0 angle langle vec{x},0 | - Sig| ight) leq delta

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 interms of "projection valued measures" on R; if the variablehappens to be discrete, the projection valued measure reduces to afamily {Eλ} 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"y"} indexed by elements of "Y". such that: I = sum_{y in Y} operatorname{E}_y.

Given a mixed state "S", there corresponds a probability measure on "Y"given by : operatorname{Pr}{y} = operatorname{Tr}(S operatorname{E}_y )

The function "F":"X" → "Y" is computed by a circuit"U":"H"QB("r") → "H"QB("r") to within ε if and only iffor all bitstrings "x" of length "m":leftlangle vec{x},0 ig| U^* operatorname{E}_{F(x)} Uig|vec{x},0 ight angle = leftlangle operatorname{E}_{F(x)} U( |vec{x},0 angle) ig| U( |vec{x},0 angle) ight angle geq 1 - epsilon

Now : left| operatorname{Tr} (S U^* operatorname{E}_{F(x)} U) - leftlangle vec{x},0 ig| U^* operatorname{E}_{F(x)} Uig|vec{x},0 ight angle ight|leq operatorname{Tr} (ig||vec{x},0 angle langle vec{x},0 | - Sig|) | U^* operatorname{E}_{F(x)} U | leq delta so that:operatorname{Tr} (S U^* operatorname{E}_{F(x)} U) geq 1 - epsilon - delta

Theorem. If ε+ δ <1/2, then the probability distribution : operatorname{Pr}{y} = operatorname{Tr} (S U^* operatorname{E}_{y} U)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: 1 - e^{- 2 gamma^2 k} where γ = 1/2 -ε - δ.

This follows by applying the Chernoff bound.

References

* E. Biham, G. Brassard, D. Kenigsberg, T. Mor, "Quantum Computing without Entanglement", arXiv:quant-ph/0306182 v1, 2003.

* M. Freedman, A, Kitaev, M. Larsen and Z. Wang, "Topological Quantum Computation", Bulletin of the AMS, 40:1,pp 31-38, 2002

* M. Hirvensalo, "Quantum Computing", Springer, 2001.

* A. Kitaev, "Quantum Computations: Algorithms and Error Correction", Russian Mathematical Surveys, 52:6, pp 1191-1249, 1997.

* M. Nielsen and I. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Quantum programming — is a set of computer programming languages that allow the expression of quantum algorithms using high level constructs. The point of quantum languages is not so much to provide a tool for programmers, but to provide tools for researchers to… …   Wikipedia

  • Quantum cellular automata — (QCA) refers to any one of several models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann. It may also refer to quantum dot cellular automata, which is a proposed… …   Wikipedia

  • Quantum Turing machine — A Quantum Turing machine (QTM) is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a… …   Wikipedia

  • Quantum Fourier transform — The quantum Fourier transform is the discrete Fourier transform with a particular decomposition into a product of simpler unitary matrices. Using this decomposition, the discrete Fourier transform can be implemented as a quantum circuit… …   Wikipedia

  • Quantum computer — A quantum computer is a device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, information is… …   Wikipedia

  • Quantum information — For the journal with this title, see Historical Social Research. In quantum mechanics, quantum information is physical information that is held in the state of a quantum system. The most popular unit of quantum information is the qubit, a two… …   Wikipedia

  • Quantum channel — In quantum information theory, a quantum channel is a communication channel which can transmit quantum information, as well as classical information. An example of quantum information is the state of a qubit. An example of classical information… …   Wikipedia

  • Quantum finite automata — In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be… …   Wikipedia

  • Quantum digital signature — A Quantum Digital Signature (QDS) refers to the quantum mechanical equivalent of either a classical digital signature or, more generally, a handwritten signature on a paper document. Like a handwritten signature, a digital signature is used to… …   Wikipedia

  • Quantum gate — A quantum gate or quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the analogues for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”