June 18, 2019 Quantum Computing: Programming Model and Algorithms

Quantum Computing – Programming Model and Algorithms

To use Quantum computers, it is important to understand multiple things such as: their programming model, the quantum- mechanical effects like superposition, entanglement and tunneling that make them superior; how QCs exploit these quantum-mechanical effects to effectively improve computation in terms of time and energy consumption; and why it is imminent that quantum computers perform an operation that is intractable on a classical computer.  What are quantum algorithms, what classes of problems do they solve, and how are they different from classical algorithms?

Companies like IBM, DWave and Rigetti are offering cloud service to access this pricey hardware. It is about time we understand the programming model and try to implement some basic algorithms. The mathematical basis of QC was published decades ago (starting in the 1990s) and with the advent of these cloud services, it is now possible to finally create an application that can solve real world problems.

QC Programming Model

Define Qubit

Computation as we define it is basically the mapping of the states from input to output. A qubit is a two-dimensional system that is in a state of 0 or 1 or both.

If the qubit gets measured, it will return the classical bit value 0 with probability or bit value of 1 with probability of A qubit, or system of qubits, changes its state by going through a series of unitary transformations . The matrix U is unitary if the product of matrix and its transpose is identity matrix.

A qubit state evolves under the action of 2 x 2 matrix U according to :

The joint state of a system of qubits is described by a tensor product . A three qubit system with qubit being

As in classical computers, the basic operation is called Gates e.g. AND, OR , NOT gate. Similarly, QC has these basic operations as unitary transformation that is reversible. It means the number of input qubits will always be equal to number of output qubits. For example :

X gate  : quantum version of NOT gate

CNOT gate  : “controlled NOT” negates a target bit if and only if control bit is “1” .

Toffoli gate  : “controlled controlled NOT” is quantum (reversible) version of AND gate. It negates a target bit if and only if both control bits are “1”

A set of gates that together can execute all possible quantum computations is called universal gate set. The set of all unary, binary and CNOT gates form a universal gate set.i.e. {H, T, CNOT} .

Commonly Used Quantum Gates

By using these gates, a quantum algorithm can be thought of in three steps:

1. Encoding the data into the state of set of input qubits.
2. A sequence of quantum gates is applied to input qubits.
3. Measurement of one or more qubits to obtain classically interpretable results.

The two quantum effects that quantum algorithms exploit to outperform classical computers are :

1. Superposition : Before measurement, each qubit is both basis state simultaneously with probability proportional to the amplitude of prefactor.
2. Entanglement : a type of correlation that has no classical analog. When two particles are entangled their spin matches in all direction.

The main challenge in quantum algorithms is to leverage these two quantum effects. The fact that most known quantum algorithms are based on few paradigms is remarkable and perhaps surprising. These paradigms are :

1. Quantum Fourier Transform (QFT)
2. The Grover Operator (GO)
3. The Harrow/Hassidim/Lloyd (HHL) method for linear systems
4. Variational quantum eigenvalue solver (VQE)
5. Direct Hamiltonian simulation (SIM)

We can find the following quantum algorithm details and their implementation in this arxiv article:

Quantum algorithms are often divided into three categories. Details can be found at Quantum Algorithm Zoo

There are some limitations of current Quantum computers. These limitations must be well understood to effectively design an algorithm.

Decoherence : Quantum computers lose their “quantumness” gradually and become more like a classical object. After decoherence has completely occurred a QC can no longer take advantage of these quantum effects of superposition and entanglement. This increases the noise in the system as quantum algorithms proceed in time. This limits the depth of the algorithm that can be applied.

Other important questions to consider are: What are available gate sets with which the user can state their algorithm? What physical gates are implemented? Which pair of qubits can two-qubit gates apply to? What are the sources of noise? Have thoughts on these? Let’s chat in the forums.