Quantum circuit


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

Reversible classical logic gates

The elementary logic gates of a classical computer, other than the NOT gate, are not 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 0,1 or 1,0 or 0,0.
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 of bits x1,x2,...,xn of length n. The set of n-bit data is the space n, which consists of 2n strings of 0's and 1's.
More precisely: an n-bit reversible gate is a bijective mapping f from the set n 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

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 n is the Hilbert space
This is by definition the space of complex-valued functions on n and is naturally an inner product space. This space can also be regarded as consisting of linear superpositions of classical bit strings. Note that HQB is a vector space over the complex numbers of dimension 2n. The elements of this space are called n-qubits.
Using Dirac ket notation, if x1,x2,...,xn is a classical bit string, then
is a special n-qubit corresponding to the function which maps this classical bit string to 1 and maps all other bit strings to 0; these 2n special n-qubits are called computational basis states. All n-qubits 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 unitary mapping, that is, a linear transformation of a complex inner product space that preserves the Hermitian inner product. An n-qubit quantum gate is a unitary mapping U from the space HQB of n-qubits 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 Wf defined as follows:
Note that Wf permutes the computational basis states.
Of particular importance is the controlled NOT gate WCNOT 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 unitary matrix:
so

Reversible logic circuits

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−k bits.


We will refer to this scheme as a classical assemblage. 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.
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 -bit circuit f such that
where there are m underbraced zeroed inputs and
Notice that the end result always has 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.
More generally, any function f can be simulated by a circuit of Toffoli gates. Obviously, if the mapping fails to be injective, at some point in the simulation 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 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 universality theorems 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θ mentioned above, together with the 2-qubit CNOT gate WCNOT. 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 uncountably many possible single qubit phase gates, one for every possible angle θ, so they cannot all be represented by a finite circuit constructed from.

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, 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:
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 HQB. U is thus a unitary map
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.
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 indexed on some parameter λ
ranging over a countable set. Similarly, a Y valued observable,
can be associated with a family of pairwise orthogonal projections
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 → HQB to within ε if and only if
for all bitstrings x of length m
Now
so that
Theorem. If ε + δ < 1/2, then the probability distribution
on Y can be used to determine F 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 is sampled more than k/2 times is at least
where γ = 1/2 - ε - δ.
This follows by applying the Chernoff bound.