Quantum circuit

Last updated
Circuit that performs teleportation of a qubit. This circuit consists of both quantum gates and measurements. Measurement is a quantum phenomenon that does not occur in classical circuits. Quantum teleportation circuit.svg
Circuit that performs teleportation of a qubit. This circuit consists of both quantum gates and measurements. Measurement is a quantum phenomenon that does not occur in classical circuits.

In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits 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.

Contents

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 bits. 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. [2] [3] [4]

The graphical depiction of quantum circuit elements is described using a variant of the Penrose graphical notation.[ citation needed ] Richard Feynman used an early version of the quantum circuit notation in 1986. [5]

Reversible classical logic gates

Most elementary logic gates of a classical computer 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 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 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.

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

The quantum logic gates are reversible unitary transformations on at least one qubit. Multiple qubits taken together are referred to as quantum registers. 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

This is by definition the space of complex-valued functions on {0,1}n and is naturally an inner product space. means the function is a square-integrable function. This space can also be regarded as consisting of linear combinations, or superpositions, of classical bit strings. Note that HQB(n) is a vector space over the complex numbers of dimension 2n. The elements of this vector space are the possible state-vectors of n-qubit quantum registers.

Using Dirac ket notation, if x1,x2, ...,xn is a classical bit string, then

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 2n 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 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-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 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 phase shift operator:

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

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. [6]

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

Now

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.

See also

Related Research Articles

<span class="mw-page-title-main">BQP</span> Computational complexity class of problems

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

<span class="mw-page-title-main">Qubit</span> Basic unit of quantum information

In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic 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 spin states can also be measured as horizontal and vertical linear 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 simultaneously, a property that is fundamental to quantum mechanics and quantum computing.

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search 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.

The Deutsch–Jozsa algorithm is a deterministic 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.

<span class="mw-page-title-main">Bloch sphere</span> Geometrical representation of the pure state space of a two-level quantum mechanical system

In quantum mechanics and computing, 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 theorised as essential to achieve fault tolerant quantum computing that can reduce the effects of noise on stored quantum information, faulty quantum gates, faulty quantum preparation, and faulty measurements. This would allow algorithms of greater circuit depth.

In quantum information science, the Bell's states or EPR pairs are specific quantum states of two qubits that represent the simplest examples of quantum entanglement. The Bell's 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: . Entanglement is a basis-independent result of superposition. 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 "collapse" the other qubit to a state whose measurement will yield one of two possible values, where the value depends on which Bell's state the two qubits are in initially. Bell's states can be generalized to certain quantum states of multi-qubit systems, such as the GHZ state for 3 or more subsystems.

<span class="mw-page-title-main">Superdense coding</span> Two-bit quantum communication protocol

In quantum information theory, superdense coding is a quantum communication protocol to communicate a number of classical bits of information by only transmitting a smaller number of qubits, under the assumption of sender and receiver pre-sharing an entangled resource. In its simplest form, the protocol involves two parties, often referred to as Alice and Bob in this context, which share a pair of maximally entangled qubits, and allows Alice to transmit two bits to Bob by sending only one qubit. This protocol was first proposed by Charles H. Bennett and Stephen Wiesner in 1970 and experimentally actualized in 1996 by Klaus Mattle, Harald Weinfurter, Paul G. Kwiat and Anton Zeilinger using entangled photon pairs. Superdense coding can be thought of as the opposite of quantum teleportation, in which one transfers one qubit from Alice to Bob by communicating two classical bits, as long as Alice and Bob have a pre-shared Bell pair.

<span class="mw-page-title-main">Controlled NOT gate</span> Quantum logic gate

In computer science, the controlled NOT gate, controlled-X gate, controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-based quantum computer. It can be used to entangle and disentangle Bell states. Any quantum circuit can be simulated to an arbitrary degree of accuracy using a combination of CNOT gates and single qubit rotations. The gate is sometimes named after Richard Feynman who developed an early notation for quantum gate diagrams in 1986.

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error.

In quantum mechanics, notably 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.

<span class="mw-page-title-main">One-way quantum computer</span> Method of quantum computing

The one-way or measurement-based quantum computer (MBQC) is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. The algorithm was initially introduced by Alexei Kitaev in 1995.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

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.

<span class="mw-page-title-main">Bernstein–Vazirani algorithm</span> Quantum algorithm

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.

The One Clean Qubit model of computation is performed an qubit system with one pure state and maximally mixed states. This model was motivated by highly mixed states that are prevalent in Nuclear magnetic resonance quantum computers. It's described by the density matrix , where I is the identity matrix. In computational complexity theory, DQC1; also known as the Deterministic quantum computation with one clean qubit is the class of decision problems solvable by a one clean qubit machine in polynomial time, upon measuring the first qubit, with an error probability of at most 1/poly(n) for all instances.

References

  1. Nielsen, Michael A.; Chuang, Isaac (2010). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. pp. 26–28. ISBN   978-1-10700-217-3. OCLC   43641333.
  2. Colin P. Williams (2011). Explorations in Quantum Computing. Springer. pp. 123–200. ISBN   978-1-84628-887-6.
  3. Nielsen, Michael A.; Chuang, Isaac (2010). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. pp. 171–215. ISBN   978-1-10700-217-3. OCLC   43641333.
  4. Ömer, Bernhard (2000-01-20). Quantum Programming in QCL (PDF) (Thesis). Institute for Theoretical Physics, Vienna University of Technology. pp. 37–38. Retrieved 2021-10-12.
  5. Feynman, Richard P. (1986). "Quantum mechanical computers". Foundations of Physics. Springer Science and Business Media LLC. 16 (6): 507–531. Bibcode:1986FoPh...16..507F. doi:10.1007/bf01886518. ISSN   0015-9018. S2CID   122076550.
  6. "Introduction to the Quantum Circuit Model" (PDF).