## Author

### Rajendra K. Bera

Chief Mentor, Acadinnet

## Part II – Algorithms

In Part I we laid the foundation on which quantum algorithms are built. In this part we harness such exotic aspects as superposition, entanglement and collapse of quantum states of that foundation to show how powerful quantum algorithms can be constructed for efficient computation. Appendixes A and B are provided to jog the memory of those who are recently out of touch with linear algebra and Fourier series.

**NOTE:** Readers desirous of getting some hands-on experience with a few of the algorithms presented in Part II can visit https://acc.digital/Quantum_Algorithms. This material is provided by Vikram Menon and Ayan Chatterjee using the IBM Q Experience for Researchers. (see https://quantumexperience.ng.bluemix.net/qx/experience” ).

## 9. The quantum path to algorithms

Developers of quantum algorithms must always bear in mind an intriguing aspect of Nature. It keeps track of all the continuous parameters describing the state of a quantum system, like *a* and *b* that describe, say, the state *|Ψ〉 = a|0〉 + b|1〉* of a qubit, but keeps most of that information hidden from observers. Nature hides information or more likely we are not smart enough to discover it.

In quantum computation, the state of the quantum computer is described by a state vector *|Ψ〉*, which in its general form is a complex linear superposition of all binary states of the qubits. The temporal evolution of *|Ψ〉* is described by a unitary operator *U* on this vector space.

The unique ability of qubits to stay in superposed and entangled states and the ability of unitary operators to act in parallel on all the superposed states of one or more qubits, permits some unusual computational tricks. For example, it is possible to calculate the value of a function * f(x)* for multiple values of

*x*in parallel without parallel replication of computing hardware. Indeed, quantum parallelism comes for free. Further, the Hadamard gate generates genuine random numbers. The essence of designing quantum algorithms lies in the clever use of quantum superposition of states, entanglement of quantum states, wave interference, and collapse of quantum states.

### 9.1 Some basic quantum algorithms

The design of quantum algorithms lies in the clever choice of computational and measurement bases, initial states, sequence of unitary gates and measurement points. Certain things, *e.g.*, determination of global information about a function, is more efficiently done than on classical computers.

**Random number generation**

When we think of random numbers we think of tossing a fair coin. Quantum particles can be made the fairest coins of all. Random numbers can be generated perfectly by preparing a qubit in state *|0〉 or |1〉* and applying the Hadamard gate to change its state to *(|0〉 + |1〉)/√2 or (|0〉 -|1〉)/√2*, respectively, and then measuring the state. The result will be either* |0〉 or |1〉* with equal probability.

**n-qubit Hadamard gate**

When the Hadamard gate is applied to *n* qubits individually, we get

where the sum is over all possible *2 ^{n}* mutually orthogonal states of

*n*qubits or values of

*x*. Thus, the Hadamard transform produces an equal superposition of all

*2*possible computational basis states, i.e.,

^{n}*x*can be viewed as the binary representation of the numbers from 0 to

*2*. The n-qubit Hadamard gate is sometimes known as the Walsh-Hadamard gate.

^{n }-1Consider a single qubit in state* |x〉* where *x ∈ {0, 1}*. Then

For an n-qubit system *|x〉 = |x _{1}〉…|x_{n}〉 = |x_{1} … x_{n}〉*, we have

*x·y* is the bitwise inner product of *x* and* y* modulo 2 and *|y〉 = |y _{1}〉 …|y_{n}〉 = |y_{1} … y_{n}〉*. The reader should instinctively spot the above formula (last line) as it will appear frequently in later Sections.

### 9.2 Computing x∧y

Take 3 qubits, each prepared in state *|0〉*. The first qubit is the placeholder for *x*, the second for* y*, and the third for the result of x∧y. To create the 4 possible inputs of x and y, *{|00〉, |01〉, |10〉, |11〉}*, apply the Hadamard gate to the first two qubits to get

An application of the Toffoli gate, T, then produces

Notice that the 3-qubit system is put into equal superposition of the four possible results of x∧y. The result of ANDing the first two qubits appears in the third qubit.

### 9.3 Computing *x+y*

By applying the* C _{not }* gate to the first two qubits of

*T|Ψ1〉*above we get

where the second qubit is the sum and the third qubit is the carry bit. Note that the carry bit in the adder is the result of an AND operation. The carry and AND are really the same thing. The sum bit comes from an XOR gate (that is, the *C _{not }* operation).