BLOG
Quantum Advantage of PITE®️
FTQC Quantum Algorithm for Quantum Chemical Computations
The question "In an ideal error-tolerant quantum computer (FTQC), is a quantum computer superior to a classical computer? The correct answer to this question is that quantum computers are superior to classical computers for some problems, and exponentially superior for some of those problems.
How about the question in the field of quantum chemical computation, which is now expected to be applied to a wide range of problems? Let us consider two problems: real-time dynamics (real-time evolution) of Hamiltonians such as atoms and molecules, and ground-state calculations. These problems take exponential time on a classical computer. The real-time evolution is classified in the BQP complexity class (Figure 1) and can be efficiently simulated in polynomial time on a quantum computer. On the other hand, the problem of finding the ground state of the Hamiltonian is classified in the QMA complexity class and takes exponential time even on a quantum computer.
INTRODUCTION
Figure 1. Computational Complexity Class Relationships.
Computational Cost of Quantum Phase Estimation
Some readers may wonder if the ground state calculation can be exponentially faster than the classical Full-CI algorithm by using quantum phase estimation. This is true if certain conditions (good initial conditions can be prepared) are satisfied.
A quantum circuit for quantum phase estimation is shown in Figure 2. In quantum phase estimation, the eigenvalues|Ej> corresponding to the input (Hamiltonian H) eigenstates|ψj> are read into the auxiliary bits. If the input state is a superposition of multiple eigenstates, then the eigenvalues are correspondingly a superposition of multiple eigenvalues. If only the basis energy of interest is extracted from this superposition of multiple superpositions, the measurement needs to be repeated a number of times depending on the ratio of the basis states in the input state. If the input state is considered as a superposition with a uniform ratio for all eigenstates, the computational cost is O(N), which is the same as a brute force hit on a classical computer (N is the total number of eigenstates or the dimension of the Hamiltonian).
PHASE ESTIMATION
Incidentally, the quantum circuit in Figure 2 consists of a sequence of multiple controlled real-time evolution gates, each of which can be implemented in polynomial time. The number of control real-time evolution gates is also scaled depending on the accuracy, but basically, it may be regarded as not requiring exponential time.
Figure 2. Quantum circuits for quantum phase estimation. For details, see e.g. [Nielsen Chang, Quantum Computation and Quantum Information, Ohmsha (2004)].
Computational Cost of PITE®️
In my previous Blog PITE®️-a new era of quantum chemical calculations-, I introduced our method, Probabilistic Imaginary Time Evolution (PITE®️), as a ground state calculation method for quantum chemical calculations. How about the cost? A detailed analysis has been published in Phys. Rev. H. Nishi et al, Phys. Rev. Research 5, 043048 (2023).
The quantum circuit structure of PITE®️ is somewhat similar to that of quantum phase estimation. The structure is such that a controlled real-time evolution gate with the auxiliary bit as the control bit acts on the input state. An approximate imaginary time evolution operator acts when the auxiliary bit is in the desired state (|0> state). The imaginary time evolution operator is not given deterministically but is probabilistic. It can be derived that the probability that the imaginary time evolution operator acts at all steps, i.e., the total success probability, is equal to the probability of obtaining the ground energy in the quantum phase estimation. The total probability of success, P, is expressed in terms of the magnitude of the norm of the wave function of the state in which the imaginary-time evolution operator acts at all steps, since all excited states are attenuated by the imaginary-time evolution operator, leaving only the coefficients of the ground state.
PITE®️
On the other hand, in terms of accuracy, PITE®️has been found to be superior to quantum phase estimation. Figure 3 shows the calculation results. It can be seen that PITE®️ (blue) requires less computational cost than quantum phase estimation (green). Intuitively, this can be understood as follows. Quantum phase estimation requires high-frequency real-time evolution to reproduce the minimum number of digits of eigenvalues to be read out to the auxiliary bits, and the number of trotter steps required in the implementation of the real-time evolution operator is correspondingly larger. On the other hand, PITE®️ only needs real-time evolution to be large enough to distinguish between the minimum energy and the first excitation energy difference, so the number of trotter steps can be reduced accordingly.
Figure 3. The result of quantum phase estimation calculation cost of PITE®️ and QPE. (Left) Relationship between infidelity δ and computational cost.
(Right) The relationship between computational cost and the inverse of the absolute value of the coefficients of the ground state contained in the initial state|c1|-1.
We explained that neither PITE®️ nor quantum phase estimation is exponentially accelerated against the classical computer in the worst case. This is due to the total success probability. However, polynomial time acceleration is expected to be possible using a quantum computer. In fact, polynomial time acceleration can be achieved by combining quantum amplitude amplification (QAA); the combined use of PITE®️ and QAA can accelerate the computational cost by a factor of two, as shown by the orange line in Figure 3.
In addition to the methods introduced here, there are several other ground-state calculation methods using quantum computers. For example, the adiabatic time evolution associated with quantum annealing proposed by Prof. Nishimori of Tokyo Institute of Technology E. Farhi et al. arXiv:0001106 (2000)., Quantum Eigenvalue Transformation of Unitary matrices with real polynomials (QETU) method Y. Dong et al., PRX Quantum 3, 040305 (2022).. It is estimated that the time required for these methods is exponential considering the worst case as well. Comparison and examination of these various ground-state calculation methods may reveal which algorithm is best suited for which problem in the future.
Furthermore, a paper was reported that asked the question, "What kind of quantum chemistry problem is there in which the exponential acceleration hypothesis, the hypothesis that a quantum computer can obtain the ground state in polynomial time while a classical computer requires exponential computation time? The paper reported here addresses this question by numerical experiments S. Lee et al., Nature Comm. 14, 1952 (2023)..
Unfortunately, no evidence for the exponential quantum acceleration hypothesis was found yet. However, future research may find problems for which the exponential quantum acceleration hypothesis is valid. It is also hoped that polynomial time acceleration will further demonstrate the practicality of quantum computers in ground-state calculations in the future.
PROSPECTS
