Introduction
This article is Part 3 of a series on quantum computing.
In Part 1, we covered an overview of the history, principles, types, and quantum computing applications. In Part 2, we explored its computational mechanism, including quantum mechanics experiments and principles, quantum gates, mathematical representations of qubits, and quantum measurement. We also dived into how this computational mechanism makes particular calculations (such as chemistry simulations, optimization problems, and simultaneous linear equations) more efficient than classical computers.
In Part 3, we will now delve into specific algorithms, seeing how quantum computers make computations faster than their classical counterpart.
Algorithms
When we make computations on a computer, we want the run time to be as little as possible. The time it takes for a particular computation is given by the product of the time taken for one calculation and the number of calculations needed. As we have discussed in previous parts, it is estimated that the completion of a fully functioning quantum gate computer (a quantum computer with functionality close to a classical computer) will still take decades. Therefore, we are yet to know the time it takes for a quantum computer to carry out one calculation. So, when we compare the computation time for classical and quantum computers, we only focus on the number of calculations needed to complete the desired computation.
In computer science, we often describe the number of calculations needed with a mathematical notation called the Big O notation. This notation describes the growth of a particular algorithm’s run time as the number of inputs approaches infinity. This concept is similar to the order of a certain function. For example, for a quadratic function, as the input approaches infinity, we can ignore the terms with a lower order. We can approximate the function’s growth to be dependent only on the term with the highest order, which for a quadratic function is 2. From this, we can say that an algorithm with a lower order runs faster. In Big O notation, we express linear growth as O(n) and quadratic growth as O(n^2). When n is the base, we call the algorithm running in polynomial time. When n is the exponent, we call the algorithm running in superpolynomial time.
We already know that quantum computers can speed up some algorithms. Let us now explore two famous algorithms, Shor’s algorithm and Grover’s algorithm, and also discuss some hybrid algorithms, which use the capabilities of both classical and quantum computers.
Shor's Algorithm
Shor’s algorithm is an algorithm invented by mathematician Peter Shor in 1994. The algorithm solves integer factorization problems in polynomial time. A classical algorithm that solves the same problem runs on superpolynomial time, so Shor’s algorithm is a significant speedup. In Big O notation, a classical algorithm is larger than O(e^(n^3)), whereas Shor’s algorithm runs in O(n^3). A primary application of this algorithm is prime factorization. Standard encryption used today, called RSA encryption, uses prime factors as the key for decryption. RSA encryption was realistically unable to solve for a classical algorithm. However, with Shor’s algorithm running in polynomial time, this encryption is expected to be broken.
Shor’s algorithm is a type of quantum Fourier transform, one of few quantum algorithm categories. A quantum Fourier transform is a type of linear transformation on qubits. To transform 2^n amplitudes, it takes O(n2^n) gates for a classical computer, but only O(n^2) gates for a quantum computer, which we can see is a superpolynomial speedup. Therefore, algorithms that involve Fourier transforms can be efficiently implemented on a quantum computer in polynomial time, and Shor’s algorithm is one example of this.
Grover's Algorithm
Grover’s algorithm is an algorithm invented by computer scientist Lov Grover in 1996. The algorithm searches through an unstructured database with N number of entries. In other words, given the output of a certain function that is unknown, the algorithm finds the input. So, for y = f(x), given y, we can figure out the x-values. Therefore, Grover’s algorithm can find the x-values for f(x) = 0. We can also use this algorithm to find security codes, search through databases, and estimate the mean and median of a set of numbers. A classical algorithm with the same functionality would take O(n) time, whereas Grover’s algorithm only takes O(sqrt(n)) time, which is a quadratic speedup.
Grover’s algorithm is a type of amplitude amplification, which is another category of quantum algorithms. In amplitude amplification, we amplify the wave function of a particular combination of the quantum state for each calculation (query) based on how close it is to the desired value. We eventually get a large amplitude for the likely-to-be-correct combination by repeating this, thus probabilistically reaching the answer.
Hybrid Algorithms
Some algorithms use the capabilities of both classical and quantum computers for practical industrial applications. Two popular algorithms are QAOA (quantum approximate optimization algorithm) and VQE (variational quantum eigensolver), which combine the use of quantum states and measurement with classical optimization.
QAOA is a model of quantum annealing and therefore is an algorithm used for optimization (maximizing an objective function), and this is used in fields such as finance.
VQE is an algorithm that minimizes the energy expectation of the quantum state. We can find the ground state energy of molecules and therefore use it for quantum chemistry calculations.
This brings us to an end to Part 3! In a future part (Part 4), we will explore the development of quantum computer hardware.
English 
Japanese