TECHNICAL NOTE
Will the NISQ era really arrive?
PROBLEMS
What are the "difficult" problems that quantum computers should solve?
In today's society, there are problems that are considered intractable for classical computers but might be solvable by quantum computers. Can we investigate these problems and distinguish the key to solving them? This is where the concept of complexity classes comes into play. Complexity classes are a mathematical field that classifies problems based on the difficulty they pose for classical computers to solve. The term "difficulty" here refers to the degree of increase in computational time as problems scale up in size. A complexity class of interest is NP-hardness, which encompasses a variety of optimization problems known to be challenging for classical computers, such as the Maximum Cut (MAX CUT) problem, Traveling Salesman Problem, and Knapsack Problem.
To illustrate, let's consider the MAX CUT problem as an example. Given a graph composed of five vertices (white circles) and six edges as depicted in Figure 2, the problem is to find the partition of the vertex set into two subsets using a single path (meaning each edge is traversed zero or one times) that maximizes the number of cut edges. Figure 2 provides examples of ways to cut the graph. Upon examination, it's clear that it's not possible to partition it in a way that yields a cut size of 6. Thus, the maximum cut size for this graph is 5. While this graph is small enough to enumerate all possible cuts, the number of possible partitions of the vertex set grows rapidly as the number of vertices in the graph increases. For instance, with 10 vertices, there are 2^10 = 1024 possibilities; with 20 vertices, there are 2^20 = 1048576 possibilities; and with 30 vertices, there are 2^30 = 1073741824 possibilities, and so on.
NP-hard problems can be described as problems that exhibit exponential growth in computational time as their scale increases. Currently, these problems are typically approached on classical computers using heuristic methods (methods based on experience that might yield the correct answer if fortunate). Classifying problems that are difficult for classical computers and, interestingly, remain difficult even for quantum computers, alongside problems that quantum computers can efficiently solve, presents a fascinating challenge.
Figure Figure 2: The dashed lines in the left diagram represent a cut achieved through a single path, resulting in a cut size of 2. As shown in the middle and right diagrams, the cut size is 5 when partitioned in that manner.
HYBRID
Quantum-Classical Hybrid Algorithms for the NISQ Era
AAs mentioned at the beginning of this paper, quantum computers in the NISQ era have a limited number of qubits and are heavily affected by noise, making it challenging to handle large-scale problems. To leverage quantum computers in this context, the development of quantum-classical hybrid algorithms is being pursued. These algorithms divide tasks between the quantum and classical components of a computer system. Quantum-classical hybrid algorithms, including the widely used Variational Quantum Algorithms (VQA), allocate quantum tasks to quantum computers and classical tasks to classical computers. As depicted in Figure 3, a typical VQA generates quantum superposition states based on variational parameters within the quantum computer, and classical computers are utilized for updating these parameters. By iteratively performing this process, the optimal quantum state is obtained. While various VQAs have been proposed, they all essentially follow the procedure illustrated in Figure 3.
Figure 3: Schematic diagram of computation using VQA. Reprinted from Bittel and Kliesch.
EXAMPLE
Example of a Variational Quantum Algorithm: Quantum Approximate Optimization Algorithm (QAOA)
Many optimization problems of practical interest can be formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems, and the Quantum Approximate Optimization Algorithm (QAOA) is used to solve them using quantum computers [Blekos et al., arXiv:2306.09198].
Figure 4: Steps of the QAOA method. Reprinted from Blekos et al
Example of a Variational Quantum Algorithm: ADAPT-VQE
For quantum chemistry calculations, a Variational Quantum Eigensolver (VQE) is used as a Variational Quantum Algorithm. Among its improved versions, one that holds particular promise is ADAPT-VQE [Grimsley et al., Nature Communications 10, 3007 (2019)]. As illustrated in Figure 5, ADAPT-VQE defines a pool of candidate operators (operator pool) to generate the variational circuit. From this pool, candidates are selected to incrementally expand the variational circuit in a way that minimizes the correlated energy of the molecular system. The determination of operators for expansion is followed by parameter optimization, which is similar to the standard VQE approach.
Figure 5 provides a comparison between ADAPT-VQE and other methods for calculating the total energy of a BeH2 molecule. As evident from Figure 6, ADAPT-VQE achieves smaller errors with fewer circuit parameters compared to other methods. In the NISQ era of quantum computing, where the depth of quantum circuits significantly impacts reliability, the feature of ADAPT-VQE showcased in this comparison becomes a substantial strength.
Figure 5: Procedure of the ADAPT-VQE method. Reprinted from Grimsley et al.
Figure 6: Difference between the total energy of the BeH2 molecule calculated using ADAPT-VQE and other methods compared to the exact solution. Reprinted from Grimsley et al.
PROSPECTS
Various Variational Quantum Algorithms (VQAs) have been proposed, and they have achieved success in demonstrating concepts for simple problems. However, it is important to note that even if the quantum part of a problem's solution using VQA were to have a calculation time of 0, the problem could still become NP-hard due to the classical part, as mathematically proven [Bittel and Kliesch, Phys. Rev. Lett. 127, 120502 (2021)]. Complexity classes are based on the worst-case scenario for computation time, so while VQA is not impractical due to NP-hardness, there's a possibility that the classical part could hinder the algorithm's effectiveness, regardless of how superior the quantum part is.
One strategy to avoid the NP-hardness associated with VQA is the use of non-variational algorithms. However, it's important to distinguish between problems that a given non-variational algorithm can solve efficiently after bypassing the NP-hardness arising from VQA. Recently, we proposed a general non-variational algorithm called Probabilistic Imaginary-Time Evolution (PITE®️) that doesn't require the incorporation of classical computers [Kosugi et al., Phys. Rev. Research 4, 033121 (2022)]. Unlike VQA, which can only optimize quantum states within a certain scope defined by variational circuits, PITE®️ is distinguished by its ability to execute genuine quantum optimization. With the advancement of hardware technology, it's expected that the utility of PITE®️ will be demonstrated in the era following NISQ, where quantum computers consist of more qubits and incorporate error correction.
NP-Hardness of Variational Quantum Algorithms and Prospects for the Post-NISQ Era
The development of quantum computers requires cutting-edge hardware technology
Since Google's announcement of achieving quantum supremacy in 2019, research and development in the field of quantum computing have been increasingly active. The Japan Science and Technology Agency (JST) Research Strategy Center, as shown in Figure 1, has projected the evolution of the number of quantum bits (qubits). For quantum computers to surpass the performance of classical computers that we currently use in our daily lives, it is believed that the number of qubits must exceed 10,000, and these qubits must be error resistant.
A reasonable estimate suggests that reaching that point will likely occur around 2050, and the approximately 30 years between now and then are being referred to as the era of Noisy Intermediate-Scale Quantum (NISQ) devices. During this era, the focus is on developing useful algorithms assuming the future use of error-resistant quantum computers and adapting these algorithms for the NISQ era or applying them to intermediate-scale problems.
As of July 2023, a quantum computer consisting of 433 qubits has been developed by IBM, indicating that progress is being made toward large-scale quantum systems.
INTRODUCTION
Figure 1: Evolution of the number of qubits in gate-model quantum computers. Reprinted from 'Everyone's Quantum Computer' by Japan Science and Technology Agency (JST) Research Strategy Center (2018).
