An algorithm is a step-by-step procedure to perform a calculation, or a sequence of instructions to solve a problem, where each step can be performed on a computer. Therefore, an algorithm is a quantum algorithm when it can be performed on a quantum computer. In principle it is possible to run all classical algorithms on a quantum computer. However, the term quantum algorithm is applied to algorithms [1] of which at least one of the steps is distinctly ‘quantum’, using superposition or entanglement.

Problems that are fundamentally unsolvable by classical algorithms (so called undecidable problems) cannot be solved by quantum algorithms either. The added value of quantum algorithms is that they can solve some problems significantly faster than classical algorithms. The best-known examples are Shor’s algorithm and Grover’s algorithm. Shor’s algorithm is a quantum algorithm for integer factorization. Simply put, when given an integer N, it will find its prime factors. It can solve this problem exponentially faster than the best-known classical algorithm can. Grover’s algorithm figure1 shows below can search an unstructured database or unordered list quadratically faster than the best classical algorithm with this purpose.

Figure1: Quantum Computer Algorithms

Quantum algorithms are most commonly described by a quantum circuit, of which a simple example is shown in the figure below. A quantum circuit is a model for quantum computation, where the steps to solve the problem are quantum gates performed on one or more qubits. A quantum gate is an operation applied to a qubit that changes the quantum state of the qubit. Quantum gates can be divided into single-qubit gates and two-qubit gates, depending on the number of qubits on which they are applied at the same time. Three-qubit gates and other multi-qubit gates can also be defined. A quantum circuit is concluded with a measurement on one or more qubits.

The power of quantum algorithms ultimately derives from the exponential complexity of quantum systems—the state of a system of n entangled qubits is described by (and can thus encode) N = 2n complex coefficients, as discussed in the previous chapter. Moreover, the application of each elementary gate on, say, two qubits update the 2n complex numbers describing the state, thereby seeming [2] to perform 2n computations in a single step. On the other hand, at the end of the computation, when the n qubits are measured, the result is just n classical bits. The challenge of designing useful and advantageous quantum algorithms derives from the tension between these two phenomena—one must find tasks whose operational solutions both make use of this parallelism and yield a final quantum state that has a high probability of returning valuable information upon measurement. Successful approaches take advantage of the phenomenon of quantum interference for generating useful results.

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims to explain the principles of quantum programming, which are quite [3] different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM's quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

References:

1. https://www.quantum-inspire.com/kbase/what-is-a-quantum-algorithm/#:~:text=What%20is%20a%20quantum%20algorithm%3F%201%20Quantum%20Algorithms%204%20The%20power%20of%20quantum%20algorithms.%20
2. https://www.nap.edu/read/25196/chapter/5
3. https://arxiv.org/abs/1804.03719

Cite this article:

S. Nandhinidwaraka (2021) Scope of Quantum Computer Algorithms, AnaTechmaz, pp.10