Quantum Algorithm Implementations

QUANTUM ALGORITHM IMPLEMENTATIONS

 

INTRODUCTION

Quantum computing exploits quantum-mechanical effects—in particular, superposition, entanglement, and quantum tunneling—to more efficiently execute a computation. Compared to traditional, digital computing, quantum computing offers the potential to dramatically reduce both execution time and energy consumption. These potential advantages, steady advances in nano-manufacturing, and the slow-down of traditional hardware scaling laws (such as Moore’s Law) have led to a substantial commercial and national-security interest and investment in quantum computing technology in the 2010s. Recently, Google announced that it has reached a major milestone known as quantum supremacy—the demonstration that a quantum computer can perform a calculation that is intractable on a classical supercomputer [9]. The problem tackled here by the quantum computer is not one with any direct real-world application. Nonetheless, this is a watershed moment for quantum computing and is widely seen as an important step on the road toward building quantum computers that will offer practical speedups when solving real-world problems [100]. (See [3] for a precise technical definition of quantum supremacy.)

While the mathematical basis of quantum computing, the programming model, and most quantum algorithms have been published decades ago (starting in the 1990s), they have been of interest only to a small dedicated community. We believe the time has come to make quantum algorithms and their implementations accessible to a broad swath of researchers and developers across computer science, software engineering, and other fields. The quantum programming model is fundamentally different from traditional computer programming. It is also dominated by physics and algebraic notations that at times present unnecessary entry barriers for mainstream computer scientists and other more mathematically trained scientists.

In this review, we provide a self-contained, succinct description of quantum computing, and of the basic quantum algorithms with a focus on implementation. Since real quantum computers, such as IBM Q [69], are now available as a cloud service, we present results from simulator and actual hardware experiments for smaller input datasets. Other surveys of quantum algorithms with a different target audience and also without actual implementations include [1130729091106]. Other cloud service-based quantum computers are also available from Rigetti and IonQ, but in this review, we will focus solely on IBM’s quantum computing ecosystem. The code and implementations accompanying the article can be found at https://github.com/lanl/quantum_algorithms.

1.1 The Quantum Computing Programming Model

Here, we provide a self-contained description of the quantum computing programming model. We will define the common terms and concepts used in quantum algorithms literature. We will not discuss how the constructs explained here are related to the foundations of quantum mechanics. Interested readers are encouraged to take a look at Reference [92] for a more detailed account along those lines. Readers with a computer science background are referred to References [82103136], for a more comprehensive introduction to quantum computing from a computer science perspective.

Quantum computing basically deals with the manipulation of quantum systems. The physical details of this is dependent on the quantum computer’s hardware design. Here, we will only talk about the higher level abstractions used in quantum computing: A typical programmer will only be exposed to these abstractions. The state of any quantum system is always represented by a vector in a complex vector space (usually called a Hilbert space). Quantum algorithms are always expressible as transformations acting on this vector space. These basic facts follow from the axioms of quantum mechanics. Now, we will explain some of the basic concepts and terminology used in quantum computing.

1.1.1 The Qubit.

The qubit (short for ‘quantum bit’) is the fundamental information carrying unit used in quantum computers. It can be seen as the quantum mechanical generalization of a bit used in classical computers. More precisely, a qubit is a two dimensional quantum system. The state of a qubit can be expressed as (1)

|ϕ=α|0+β|1.|ϕ⟩=α|0⟩+β|1⟩.Here, αα and ββ are complex numbers such

that, |α|2+|β|2=1.|α|2+|β|2=1. In the ket-notation or the Dirac

notation|0=(10)|0⟩=(10) and |1=(01)|1⟩=(01) are shorthands for the vectors

encoding the two basis states of a two dimensional vector space. So according to this notation, Equation (1) expresses the fact that the state of the qubit is the two dimensional complex vector (αβ)(αβ). Unlike a classical bit, the state of a qubit cannot be measured without changing it. Measuring a qubit, whose state given by Equation (1), will yield the classical value of either zero (|0|0⟩) with probability |α|2|α|2 or one (|1|1⟩) with probability |β|2.|β|2. Qubit implementations and technologies are a very active area of research that is not the focus of our review, an interested reader is referred to [80] for a survey.

1.1.2 System of Qubits.

The mathematical structure of a qubit generalizes to higher dimensional quantum systems as well. The state of any quantum system is a normalized vector (a vector of norm one) in a complex vector space. The normalization is necessary to ensure that the total probability of all the outcomes of a measurement sum to one.

A quantum computer contains many number of qubits. So it is necessary to know how to construct the combined state of a system of qubits given the states of the individual qubits. The joint state of a system of qubits is described using an operation known as the tensor product. Mathematically, taking the tensor product of two states is the same as taking the Kronecker product of their corresponding vectors. Say we have two single qubit states

|ϕ|ϕ⟩ = (αβ)(αβ) and |ϕ|ϕ′⟩ = (αβ)(α′β′).

Then, the full state of a system composed of two independent qubits is given by

(2)

|ϕ|ϕ= (αβ)(αβ)=⎛⎝⎜⎜⎜αααββαββ⎞⎠⎟⎟⎟.|ϕ⟩⊗|ϕ′⟩= (αβ)⊗(α′β′)=(αα′αβ′βα′ββ′).

Sometimes the  symbol is dropped all together while denoting the tensor

product to reduce clutter. Instead the states are written inside a single ket. For example,

|ϕ|ϕ|ϕ⟩⊗|ϕ′⟩ is shortened to |ϕϕ|ϕϕ′⟩, and |0|0|0|0⟩⊗|0⟩⊗|0⟩  is shortened to |000.|000⟩. For larger

systems, the Dirac notation gives a more succinct way to compute the tensor

product using the distributive property of the Kronecker product.

For a system of, say, three qubits with each qubit in the state

|γj=αj|0+βj|1|γj⟩=αj|0⟩+βj|1⟩, for j=1,2,3j=1,2,3, the joint state is

(3)

|γ1γ2γ3=|γ1|γ2|γ3|γ1γ2γ3⟩=|γ1⟩⊗|γ2⟩⊗|γ3⟩ 

(4)

=α1α2α3|000+α1α2β3|001+α1β2α3|010+α1β2β3|011+β1α2α3|100+β1α2β 3|101+β1β2α3|110+β1β2β3|111.

=α1α2α3|000⟩+α1α2β3|001⟩+α1β2α3|010⟩+α1β2β3|011⟩+β1α2α3|100⟩+β1α2β3|101⟩+β1β2α3|110⟩+β1β2β3|111⟩.

A measurement of all three qubits could result in any of the eight (2323) possible bit-strings associated with the eight basis vectors. One can see from these examples that the dimension of the state space grows exponentially in the number of qubits n and that the number of basis vectors is 2n2n.

1.1.3 Superposition and Entanglement.

Superposition refers to the fact that any linear combination of two quantum states, once normalized, will also be a valid quantum state. The upshot to this is that any quantum state can be expressed as a linear combination of a few basis states. For example, we saw in Equation (1) that any state of a qubit can be expressed as a linear combination of |0|0⟩ and |1|1⟩. Similarly, the state of any n qubit system can be written as a normalized linear combination of the 2n2n bit-string states (states formed by the tensor products of |0|0⟩’s and |1|1⟩’s). The orthonormal basis formed by the 2n2n bit-string states is called the computational basis.

Notice that Equation (3) described a system of three qubits whose complete state was the tensor product of three different single qubit states. But it is possible for three qubits to be in a state that cannot be written as the tensor product of three single qubit states. An example of such a state is(5)

|ψ=12(|000 + |111).|ψ⟩=12(|000⟩ + |111⟩).

States of a system of which cannot be expressed as a tensor product of states of its individual subsystems are called entangled states. For a system of n qubits, this means that an entalged state cannot be written a tensor product of n single qubit states. The existence of entangled states is a physical fact that has important consequences for quantum computing, and quantum information processing in general. In fact, without the existence of such states quantum computers would be no more powerful than their classical counterparts [128]. Entanglement makes it possible to create a complete 2n2n dimensional complex vector space to do our computations in, using just n physical qubits.

1.1.4 Inner and Outer Products.

We will now discuss some linear algebraic notions necessary for understanding quantum algorithms. First of these is the inner product or overlap between two quantum states. As we have seen before, quantum states are vectors in complex vectors spaces. The overlap between two states is just the inner product between these complex vectors. For example, take two single qubit states,

|ϕ=α|0+β|1|ϕ⟩=α|0⟩+β|1⟩ and |ψ=γ|0+δ|1.|ψ⟩=γ|0⟩+δ|1⟩.

The overlap between these states is denoted in the ket notation as ψ|ϕ⟨ψ|ϕ⟩. And this is given by(6)

ψ|ϕ=γα+δβ,⟨ψ|ϕ⟩=γ∗α+δ∗β,where  denotes the complex conjugate. Notice that,ψ|ϕ=ϕ|ψ⟨ψ|ϕ⟩=⟨ϕ|ψ⟩∗.

The overlap of two states is in general a complex number. The overlap of a state with a bit-string state will produce the corresponding coefficient. For instance from Equation (1),

0|ϕ=α⟨0|ϕ⟩=α and 1|ϕ=β⟨1|ϕ⟩=β. And from Equation

(3), 001|γ1γ2γ3=α1α2β3⟨001|γ1γ2γ3⟩=α1α2β3.

Another way to look at overlaps between quantum states is by defining what is called a bra state. The states we have seen so far are ket states, like |ϕ|ϕ⟩, which represented column vectors. A bra state corresponding to this ket state, written

as ϕ|⟨ϕ|, represents a row vector with complex conjugated entries.

For instance, |ϕ|ϕ⟩ = (αβ)(αβ) implies that ϕ|⟨ϕ| = (αβ).(α∗β∗).

The overlap of two states is then the matrix product of a row vector with a column vector, yielding a single number. The reader must have already noticed the wordplay here. The overlap, with its closing angled parenthesis, form a “bra-ket”!

The outer product of two states is an important operation that outputs a matrix given two states. The outer product of the two states we defined above will be denoted by, |ψ|ψ⟩ϕ|⟨ϕ|. Mathematically the outer product of two states is a matrix obtained by multiplying the column vector of the first state with the complex conjugated row vector of the second state (notice how the ket is written before the bra to signify this). For example,(7)

|ψϕ|=(αβ)(γδ)=(αγβγαδβδ).|ψ⟩⟨ϕ|=(αβ)(γ∗δ∗)=(αγ∗αδ∗βγ∗βδ∗).

In this notation, any matrix can be written as a linear combination of outer products between bit-string states.

For a 2×22×2 matrix (8)

A=(A00A10A01A11)=A00|00|+ A01|01|+ A10|10|+ A11|11|.A

=(A00A01A10A11)=A00|0⟩⟨0|+ A01|0⟩⟨1|+ A10|1⟩⟨0|+ A11|1⟩⟨1|.

Acting on a state with a matrix then becomes just an exercise in computing overlaps between states. Let us demonstrate this process:(9)

A|ϕ=A00|00|ϕ+ A01|01|ϕ+ A10|10|ϕ+ A11|11|ϕ

=(A00α+A01β)|0+(A10α + A11β)|1 = (A00α+A01βA10α+A11β).A|ϕ⟩

=A00|0⟩⟨0|ϕ⟩+ A01|0⟩⟨1|ϕ⟩+ A10|1⟩⟨0|ϕ⟩+ A11|1⟩⟨1|ϕ⟩=(A00α+A01β)|0⟩+(A10α + A11β)|1⟩ = (A00α+A01βA10α+A11β).

This notation might look tedious at first glance but it makes algebraic manipulations of quantum states easily understandable. This is especially true when we are dealing with large number of qubits as otherwise we would have to explicitly write down exponentially large matrices.

The outer product notation for matrices also gives an intuitive input-output relation for them. For instance, the matrix

|01|+|10||0⟩⟨1|+|1⟩⟨0|

can be read as “output 0 when given a 1 and output 1 when given a 0”. Likewise,the matrix,

|0000|+|0101|+|1011|+|1110||00⟩⟨00|+|01⟩⟨01|+|10⟩⟨11|+|11⟩⟨10|

can be interpreted as the mapping

{“00” –> “00”, “01” –> “01”, “11” –> “10”, “10” –> “11” }.

But notice that this picture becomes a bit tedious when the input is in a superposition. In that case, the correct output can be computed like in Equation (9).

1.1.5 Measurements.

Measurement corresponds to transforming the quantum information (stored in a quantum system) into classical information. For example, measuring a qubit typically corresponds to reading out a classical bit, i.e., whether the qubit is 0 or 1. A central principle of quantum mechanics is that measurement outcomes are probabilistic.Using the aforementioned notation for inner products, for the single qubit state in Equation (1), the probability of obtaining |0|0⟩ after measurement is|0|ϕ|2|⟨0|ϕ⟩|2  and the probability of obtaining |1|1⟩ after measurement is|1|ϕ|2|⟨1|ϕ⟩|2. So measurement probabilities can be represented as the squared absolute values of overlaps. Generalizing this, the probability of getting the bit string

|x1xn|x1…xn⟩ after measuring an n qubit state, |ϕ|ϕ⟩, is then

|x1xn|ϕ|2|⟨x1…xn|ϕ⟩|2.

Now, consider a slightly more complex case of measurement. Suppose, we have a three qubit state, |ψ|ψ⟩ but we only measure the first qubit and leave the other two qubits undisturbed. What is the probability of observing a |0|0⟩ in the first qubit? This probability will be given by(10)

(x2x3){0,1}2|0x2x3|ϕ|2.∑(x2x3)∈{0,1}2|⟨0x2x3|ϕ⟩|2.

The state of the system after this measurement will be obtained by normalizing the state(11)

(x2x3){0,1}20x2x3|ϕ|0x2x3.∑(x2x3)∈{0,1}2⟨0x2x3|ϕ⟩|0x2x3⟩.

Applying this paradigm to the state in Equation (5), we see that the probability of getting |0|0⟩ in the first qubit will be 0.5, and if this result is obtained, the final state of the system would change to |000.|000⟩. On the other hand, if we were to measure |1|1⟩ in the first qubit, we would end up with a state |111.|111⟩. Similarly we can compute the effect of subsystem measurements on any n qubit state.

In some cases, we will need to do measurements on a basis different from the computational basis. This can be achieved by doing an appropriate transformation on the qubit register before measurement. Details of how to do this is given in a subsequent section discussing observables and expectation values.

The formalism discussed so far is sufficient to understand all measurement scenarios in this paper. We refer the reader to Reference [92] for a more detailed and more general treatment of measurement.

1.1.6 Unitary Transformations and Gates.

A qubit or a system of qubits changes its state by going through a series of unitary transformations. A unitary transformation is described by a matrix U with complex entries. The matrix U is called unitary if(12)

UU=UU=I,UU†=U†U=I,where UU† is the transposed, complex conjugate of U (called its Hermitian conjugate) and I is the identity matrix. A qubit state

|ϕ=α|0+β|1|ϕ⟩=α|0⟩+β|1⟩ evolves under the action of the 2×22×2 matrix U according to(13)

|ϕU|ϕ=(U00U10U01U11)(αβ)=(U00α+U01βU10α+U11β).|ϕ⟩→U|ϕ⟩=(U00U01U10U11)(αβ)=(U00α+U01βU10α+U11β).

Operators acting on different qubits can be combined using the Kronecker product. For example, if U1U1 and U2U2 are operators acting on two different qubits then the full operator acting on the combined two qubit system will be given by U1U2U1⊗U2.

For an n qubit system the set of physically allowed transformations, excluding measurements, consists of all 2n×2n2n×2n unitary matrices. Notice that the size of a general transformation increases exponentially with the number of qubits. In practice, a transformation on n qubits is effected by using a combination of unitary transformations that act only on one or two qubits at a time. By analogy to classical logic gates like NOT and AND, such basic unitary transformations, which are used to build up more complicated n qubit transformations, are called gates. Gates are unitary transformations themselves and from Equation (12) it is clear that unitarity can only be satisfied if the number of input qubits is equal to the number of output qubits. Also, for every gate U it is always possible to have another gate UU† that undoes the transformation. So unlike classical gates quantum gates have to be reversible. Reversible means that the gate’s inputs can always be reconstructed from the gate’s outputs. For instance, a classical NOT gate, which maps 0 to 1 and 1 to 0 is reversible because an output of 1 implies the input was 0 and vice versa. However, a classical AND gate, which returns 1 if and only if both of its inputs are 1, is not reversible. An output of 1 implies that both inputs were 1, but an output of 0 provides insufficient information to determine if the inputs were 00, 01, or 10.

But this extra restriction of reversibility does not mean that quantum gates are “less powerful” than classical gates. Even classical gates can be made reversible with minimal overhead. Reversibility does not restrict their expressive power [105]. Quantum gates can then be seen as a generalization of classical reversible gates.

The most common gates are described in Table 1. The X gate is the quantum version of the NOT gate. The CNOT or “controlled NOT” negates a target bit if and only if the control bit is 1. We will use the notation CNOTijCNOTij for a CNOT gate controlled by qubit i acting on qubit j. The CNOT gate can be expressed using the outer product notation as(14)

CNOT=|00|I+|11|X=|0000|+|0101|+|1011|+|1110|.

Table 1.

  •  
  •  
One-qubit gatesMulti-qubit gates
  
Hadamard=H=12(1111)Hadamard=H=12(111−1)CNOT=CX=⎛⎝⎜⎜⎜1000010000010010⎞⎠⎟⎟⎟CNOT=CX=(1000010000010010)
  
  
I=(1001)I=(1001)S=(100i)S=(100i)CZ=⎛⎝⎜⎜⎜1000010000100001⎞⎠⎟⎟⎟CZ=(100001000010000−1)
  
  
T=(100eiπ/4)T=(100eiπ/4)

Controlled-U=CU=⎛⎝⎜⎜⎜1000010000U00U1000U01U11⎞⎠⎟⎟⎟Controlled-U

=CU=(1000010000U00U0100U10U11)

  
  
NOT=X=(0110)NOT=X=(0110)SWAP=⎛⎝⎜⎜⎜1000001001000001⎞⎠⎟⎟⎟SWAP=(1000001001000001)
  
  
Y=(0ii0)Y=(0−ii0)Z=(1001)Z=(100−1)

Toffoli(CCNOT)=⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜100000000100000000100000000100000000

1000000001000000000100000010⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟Toffoli(CCNOT)

=(1000000001000000001000000001000000001000000001000000000100000010)

  
  
R(θ)=P(θ)=(100eiθ)R(θ)=P(θ)=(100eiθ) 
  

Table 1. Commonly used Quantum Gates

 

The Toffoli gate or “controlled-controlled NOT” or CCNOT, is a three qubit gate that is essentially the quantum (reversible) version of the AND gate. It negates a target bit if and only if both control bits are 1. In the outer product notation,

GROVER’S ALGORITHM

2.1 Problem Definition and Background

BERNSTEIN–VAZIRANI ALGORITHM

3.1 Problem Definition and Background

Accordion Content
Accordion Content
Accordion Content
Accordion Content
Accordion Content
Accordion Content
Translate »