Quantum circuit Guide, Meaning , Facts, Information and Description
A quantum circuit is a specific form for a quantum computational device. Experiments have already been carried out which can be regarded as implementing a seven qubit quantum circuit that implements Shor's algorithm. Quantum circuits are also theoretically interesting as a tool for understanding the power and limitations of quantum computation.Quantum computing devices operate on data structures called qubits. Qubits can be implemented using any system with an observable quantity A which is conserved under time evolution and such that A has at least two discrete and sufficiently spaced consecutive eigenvalues. An example of such an observable is spin.
| Table of contents |
|
2 Reversible circuits 3 Quantum computations 4 References |
Ordinarily, the logic gates in a classical computer, other than the NOT gate are not reversible. Thus for instance for an AND gate one cannot recover the two input bits from the output bit. 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 are not entropy increasing. 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 x1,x2, ...,xn of length n. The set of n-bit data is the space {0,1}n.
Reversible logic gates
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 a n-bit datum.
The quantized version of classical n-bit space {0,1}n isUsing Dirac ket notation, if x1,x2, ...,xn is a classical bit string, then
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.
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 HQB(n).
- An n-qubit reversible gate is a unitary mapping U from the space HQB(n) of qubits of size n onto itself.
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 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
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 WCNOT). 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θ, WCNOT)}.
So far we have not shown how quantum circuits are used to perform computations. Since many important numerical problems reduce to computing a unitary tranformation 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:
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 HQB(r). U is thus a unitary map
Now
This follows by applying the Chernoff bound.Quantum computations
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.
In order to associate this circuit to a classical mapping on bitstrings, we specify
The contents x = x1, ..., xm 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
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.
Similary, 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λ} indexed on some parameter λ
ranging over a countable set. Similarly, a Y valued observable,
can be associated with a family of pairwise orthogonal projections
{Ey} indexed by elements of Y. such that
Given a mixed state S, there corresponds a probability measure on Y
given by
The function F:X → Y is computed by a circuit
U:HQB(r) → HQB(r) to within ε iff
for all bitstrings x of length m
so that
Theorem. If ε+ δ <1/2, then the probability distribution
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
where γ = 1/2 -ε - δ.