Quantum circuit

Last updated

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.

Quantum mechanics branch of physics dealing with phenomena at scales of the order of the Planck constant

Quantum mechanics, including quantum field theory, is a fundamental theory in physics which describes nature at the smallest scales of energy levels of atoms and subatomic particles.

In quantum computing, a quantum register is a system comprising multiple qubits. It is the quantum analog of the classical processor register. Quantum computers perform calculations by manipulating qubits within a quantum register.

The bit is a basic unit of information used in computing and digital communications. A binary digit can only have one of two values, and may be physically represented with a two-state device. These state values are most commonly represented as either a 0or1.


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 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.

In electronics, a logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and unlimited fan-out, or it may refer to a non-ideal physical device.

Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the relation of the mapping from (nonzero-probability) states to their successors must be one-to-one. Reversible computing is a form of unconventional computing.

The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If none or not all inputs to the AND gate are HIGH, a LOW output results. The function can be extended to any number of inputs.

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 {0,1}n, which consists of 2n strings of 0's and 1's.

Entropy physical property of the state of a system, measure of disorder

In statistical mechanics, entropy is an extensive property of a thermodynamic system. It is closely related to the number Ω of microscopic configurations that are consistent with the macroscopic quantities that characterize the system. Under the assumption that each microstate is equally probable, the entropy is the natural logarithm of the number of microstates, multiplied by the Boltzmann constant kB. Formally,

String (computer science) sequence of characters, data type

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed. A string is generally considered a data type and is often implemented as an array data structure of bytes that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence data types and structures.

More precisely: an n-bit reversible gate is a bijective mapping f from the set {0,1}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 {0,1}n is the Hilbert space

Hilbert space inner product space that is metrically complete; a Banach space whose norm induces an inner product (follows the parallelogram identity)

The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions. A Hilbert space is an abstract vector space possessing the structure of an inner product that allows length and angle to be measured. Furthermore, Hilbert spaces are complete: there are enough limits in the space to allow the techniques of calculus to be used.

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. Note that HQB(n) is a vector space over the complex numbers of dimension 2n. The elements of this space are called n-qubits.

Inner product space vector space with an additional structure called an inner product

In linear algebra, an inner product space is a vector space with an additional structure called an inner product. This additional structure associates each pair of vectors in the space with a scalar quantity known as the inner product of the vectors. Inner products allow the rigorous introduction of intuitive geometrical notions such as the length of a vector or the angle between two vectors. They also provide the means of defining orthogonality between vectors. Inner product spaces generalize Euclidean spaces to vector spaces of any dimension, and are studied in functional analysis. The first usage of the concept of a vector space with an inner product is due to Peano, in 1898.

Dimension minimum number of independent coordinates needed to specify any point within a mathematical space

In physics and mathematics, the dimension of a mathematical space is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it – for example, the point at 5 on a number line. A surface such as a plane or the surface of a cylinder or sphere has a dimension of two because two coordinates are needed to specify a point on it – for example, both a latitude and longitude are required to locate a point on the surface of a sphere. The inside of a cube, a cylinder or a sphere is three-dimensional because three coordinates are needed to locate a point within these spaces.

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 (reversible) quantum gate is a unitary mapping U from the space HQB(n) 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 (also called CNOT 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:


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+mk bits.

Reversible circuit composition.svg

We will refer to this scheme as a classical assemblage (This concept corresponds to a technical definition in 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).

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

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 (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:

Quantum circuit composition.svg

The fact that connecting gates this way gives rise to a unitary mapping on n+mk qubit space is easy to check. 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 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 (for a suitable value of θ), 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 {Uθ, WCNOT)}.

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:

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(r). 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 {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:XY is computed by a circuit U:HQB(r)HQB(r) to within ε if and only if 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 - ε - δ.

This follows by applying the Chernoff bound.

Related Research Articles

Quantum teleportation is a process by which quantum information can be transmitted from one location to another, with the help of classical communication and previously shared quantum entanglement between the sending and receiving location. Because it depends on classical communication, which can proceed no faster than the speed of light, it cannot be used for faster-than-light transport or communication of classical bits. While it has proven possible to teleport one or more qubits of information between two (entangled) atoms, this has not yet been achieved between anything larger than molecules.

In quantum computing, a qubit  or quantum bit is the basic unit of quantum information—the quantum version of the classical binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include: the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two states can be taken to be the vertical polarization and the horizontal polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of both states/levels simultaneously, a property which is fundamental to quantum mechanics and quantum computing.

Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization, formulated in 1994. Informally, it solves the following problem: Given an integer , find its prime factors.

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.

Toffoli gate Universal reversible logic gate, applied in quantum computing

In logic circuits, the Toffoli gate, invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates. It is also known as the "controlled-controlled-not" gate, which describes its action. It has 3-bit inputs and outputs; if the first two bits are both set to 1, it inverts the third bit, otherwise all bits stay the same.

The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It is also a deterministic algorithm, meaning that it always produces an answer, and that answer is always correct.

Bloch sphere geometrical representation of the pure state space of a two-level quantum mechanical system

In quantum mechanics, the Bloch sphere is a geometrical representation of the pure state space of a two-level quantum mechanical system (qubit), named after the physicist Felix Bloch.

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal not only with noise on stored quantum information, but also with faulty quantum gates, faulty quantum preparation, and faulty measurements.

The Bell states, a concept in quantum information science, are specific quantum states of two qubits that represent the simplest examples of quantum entanglement. The Bell states are a form of entangled and normalized basis vectors. This normalization implies that the overall probability of the particle being in one of the mentioned states is 1: <Φ|Φ> = 1. Entanglement is a basis-independent result of superposition, a principle in which a particle is in multiple states at once. Due to this superposition, measurement of the qubit will collapse it into one of its basis states with a given probability. Because of the entanglement, measurement of one qubit will assign one of two possible values to the other qubit instantly, where the value assigned depends on which Bell state the two qubits are in. Bell states can be generalized to represent specific quantum states of multi-qubit systems, such as the GHZ state for 3 subsystems.

Superdense coding Two-bit quantum communication protocol

In quantum information theory, superdense coding is a quantum communication protocol to transmit two classical bits of information from a sender to a receiver, by sending only one qubit from Alice to Bob, under the assumption of Alice and Bob pre-sharing an entangled state. This protocol was first proposed by Bennett and Weisner in 1992 and experimentally actualized in 1996 by Mattel, Weinfurter, Kwiat and Zeilinger using entangled photon pairs. By performing one of four quantum gate operations on the (entangled) qubit she possesses, Alice can prearrange the measurement Bob makes. After receiving Alice's qubit, operating on the pair and measuring both, Bob has two classical bits of information. If Alice and Bob do not already share entanglement before the protocol begins, then it is impossible to send two classical bits using 1 qubit, as this would violate Holevo's theorem.

Controlled NOT gate

In computing science, the controlled NOT gate is a quantum gate that is an essential component in the construction of a quantum computer. It can be used to entangle and disentangle EPR states. Any quantum circuit can be simulated to an arbitrary degree of accuracy using a combination of CNOT gates and single qubit rotations.

In quantum information theory, fidelity is a measure of the "closeness" of two quantum states. It expresses the probability that one state will pass a test to identify as the other. The fidelity is not a metric on the space of density matrices, but it can be used to define the Bures metric on this space.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state into some number of approximately pure Bell pairs, using only local operations and classical communication (LOCC).

In quantum mechanics, and especially quantum information theory, the purity of a normalized quantum state is a scalar defined as

The Quantum phase estimation algorithm, is a quantum algorithm to estimate the phase of an eigenvector of a unitary operator. More precisely, given a unitary matrix and a quantum state such that , the algorithm estimates the value of with high probability within additive error , using controlled-U operations.

In quantum computing, the quantum Fourier transform is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem.

Linear Optical Quantum Computing or Linear Optics Quantum Computation (LOQC) is a paradigm of quantum computation, allowing universal quantum computation. LOQC uses photons as information carriers, mainly uses linear optical elements to process quantum information, and uses photon detectors and quantum memories to detect and store quantum information.

The KLM scheme or KLM protocol is an implementation of linear optical quantum computing (LOQC), developed in 2000 by Knill, Laflamme and Milburn. This protocol makes it possible to create universal quantum computers solely with linear optical tools. The KLM protocol uses linear optical elements, single photon sources and photon detectors as resources to construct a quantum computation scheme involving only ancilla resources, quantum teleportations and error corrections.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.