2024.05.09 Thursday
Developed Compiler Acceleration Technology for Quantum Computers
- Probabilistic method reduces optimal gate sequence search time by orders of magnitude -
National Institute of Information and Communications Technology
Tokyo University of Science
School of Science, The University of Tokyo
【Highlights】
- Developed a new compilation method to generate optimal sequences to be executed on quantum computers
- The new method is based on a probabilistic approach and reduces the time to search for the optimal sequence by several orders of magnitude.
- Expected to contribute to quantum information processing at quantum nodes that support the quantum internet
【Abstract】
The National Institute of Information and Communications Technology (NICT, President: TOKUDA Hideyuki, Ph.D.), RIKEN (President: GONOKAMI Makoto, Ph.D.), Tokyo University of Science (President: Dr.ISHIKAWA Masatoshi), and the University of Tokyo (President: FUJII Teruo, Ph.D.) succeeded in developing a technique to quickly search for the optimal quantum gate sequence*1 for a quantum computer using a probabilistic method*2.
To make a quantum computer perform a task, it must use a compiler to convert instructions written in a programming language into a sequence of gate*3 operations on quantum bits, or qubits for short. We previously applied optimal control theory (GRAPE*4 algorithm) to an exhaustive search to develop a method to identify the theoretically optimal gate sequence*5, but as the number of qubits increases, the number of possible combinations increases. As the number increases explosively, an exhaustive search becomes impossible. For example, if we were to perform an exhaustive search to find the optimal gate sequence for the task of generating an arbitrary quantum state of 6 qubits, it would take longer than the age of the universe using the fastest classical computer currently available.
Therefore, we attempted to develop a method to search for the optimal quantum gate sequence using a probabilistic approach and succeeded. Using the supercomputer Fugaku, it was confirmed and demonstrated that using a new probabilistic random search method, it is possible to search for the optimal quantum gate sequence for the above problem in a few hours.
This new method is expected to speed up quantum computer compilers, become a useful tool for practical quantum computers, and lead to improved performance of quantum computer devices. It can also be applied to optimize quantum information processing at quantum relay nodes, so it is expected to contribute to the realization of the quantum Internet and the reduction of environmental impact.
This result was published in the American scientific journal "Physical Review A" on May 6, 2024.
【Background】
Quantum computers, which are currently under development, are expected to have a major impact on society. Their benefits include reducing the environmental burden by reducing energy consumption, finding new chemical substances for medical use, accelerating the search for materials for a cleaner environment, etc. One of the big problems for quantum computers is that the quantum state is very sensitive to noise, so it is difficult to maintain it stably for a long time (maintaining a coherent quantum state).
For best performance, operations must proceed within a time that allows the quantum state to remain coherent. However, apart from the special case where the number of qubits is very small, no good method has been known to find the optimal quantum gate sequence. A solution that avoids the difficulty of the explosive increase in the number of possible gate sequences even in large-scale quantum computations and allows efficient searches within the time and computational resources that can be performed on classical computers has been awaited.
【Achievements】
The research team introduced a probabilistic method to develop a systematic method that can efficiently search for the optimal quantum gate sequence within the execution time and computational resources.
When a computer stores and processes information, all information is converted to a string of bits with values of 0 or 1. A quantum gate sequence is a computer program written in a human-readable language after it has been converted so that it can be processed by a quantum computer (see Figure 4 in the Glossary). The quantum gate sequence consists of 1-qubit gates and 2-qubit gates. The best sequence is the one with the fewest gates and shows the best performance (the number of red squares and green vertical lines is the smallest in Figure 4 in the Glossary).
Figure 1 shows the estimated calculation time when a search is performed to optimize the fidelity*6 F on the fastest classical computer for every gate arrangement using the optimal control theory algorithm GRAPE for preparing n qubit states. The solid blue line is the so-called age of the universe (13.7 billion years). As the number of qubits increases, the number of possible combinations increases explosively, so at n=6, the total calculation time exceeds the age of the universe.
Analysis of all possible sequences for small qubit numbers reveals that there are many optimal quantum gate sequences (shown in Figure 5 in the Appendix). This suggests the possibility of expanding to large quantum tasks and finding the optimal quantum gate sequence using a probabilistic search method rather than an exhaustive search.
Figure 2 shows the appearance rate (p) of sequences with fidelity F=1 for the preparation of a state consisting of n=8 qubits, which was investigated using the supercomputer Fugaku. The rate p is expressed as a function of the number of 2-qubit CNOT gates (N) in the sequence. It is clear that the probabilistic method is very efficient because the F=1 occurrence rate increases rapidly when the lower limit of N (N=124) is exceeded. For example, the appearance rate of F=1 at N=129, which is a little over N=124, is over 50%, so if you search for a gate arrangement twice, you will find a quantum sequence that has F=1 at least once on average (see Table 1 in the Appendix). In this way, it has been found that by using a probabilistic method, it is possible to search for optimal quantum gate sequences several orders of magnitude faster than when searching using an exhaustive search method.
【Future prospects】
The developed systematic and probabilistic method to provide optimal quantum gate sequences for quantum computers is expected to become a useful tool for practical quantum computers and speed up quantum computer compilers. It is expected to improve the performance of quantum computing devices (see Figure 3) and contribute to the development of quantum nodes in the quantum internet and the reduction of environmental burden.
In the future, the research team will integrate the results obtained in this study with machine learning approaches and apply them to optimize the performance of quantum computers, aiming to further speed up quantum compilers and create a database of optimal quantum gate sequences.
＜Role of each organization＞
- National Institute of Information and Communications Technology:
Research concept, analysis using GRAPE algorithm including probabilistic approach, Discussion on analysis of results and interpretation, paper writing
- RIKEN: Creation and analysis of program code for implementation of the supercomputer Fugaku, Discussion on analysis of results and interpretation, paper refinement
- Tokyo University of Science: Concept and discussion of research, paper refinement
- The University of Tokyo: Research concept, Discussion on analysis of results and interpretation, paper refinement
＜Article information＞
Journal: Physical Review A
DOI: 10.1103/PhysRevA.109.052605
Title: Quantum circuit synthesis via a random combinatorial search
Authors: Sahel Ashhab, Fumiki Yoshihara, Miwako Tsuji, Mitsuhisa Sato, and Kouichi Semba
Part of this research is supported by the Ministry of Education, Culture, Sports, Science and Technology Optical and Quantum Leap Flagship Program (Q-LEAP) "Quantum Software Research and Development and Application by Intelligent Quantum Design" (JPMXS0120319794) and by the Center of Innovations for Sustainable Quantum AI (SQAI) (JST Grant Number JPMJPF2221). The research used computational resources of the supercomputer Fugaku provided by the RIKEN Center for Computational Science.
＜Glossary＞
*1 Quantum gate sequence
A set of instructions that specify the steps for gate *3 operations to be performed on multiple qubits. In Figure 4, the six horizontal blue lines represent six qubits, with the input on the left and the output on the right. Operations are executed from left to right. Each red square represents a 1-qubit gate, and each green vertical line connecting two blue lines represents a 2-qubit gate. A quantum gate sequence consists of a sequence of 1-qubit gates and 2-qubit gates, but the optimal sequence is the one that achieves high performance with the smallest number of gates.
*2 Probabilistic approach
A computational method that randomly tries possible solutions and may succeed or fail. If there are many solutions, probabilistic methods may perform better than methods that analyze all possible solutions.
*3 Gate
A simple operation performed on one or two bits of information. Several recent studies have proposed improved methods (recipes) for constructing sequences of quantum gates that perform various quantum tasks. However, these recipes do not necessarily yield the shortest sequence of quantum gates.
*4 GRAPE
The abbreviation of GRadient Ascent Pulse Engineering. A numerical algorithm that uses the principles of optimal control theory to find the optimal pulse to control a quantum system.
*5 Developed a method of applying optimal control theory (GRAPE*4 algorithm) to an exhaustive search to identify the theoretically optimal gate sequence.
Press Release dated September 2, 2022,
"New Method to Systematically Find Optimal Quantum Operation Sequences for Quantum Computers Developed"
*6 Fidelity
A measure of the "closeness" of two quantum states. It represents the probability that one quantum state passes the test of being identified as another quantum state. If two quantum states are identical, the fidelity between them is equal to 1 (F=1). The fidelity has also been generalized for use as a measure of "closeness" between two unitary operators.
*7 Theoretical lower bound that gives F=1
The minimum number of CNOT gates required in a quantum gate sequence to obtain fidelity F=1. In the case of n-qubit state preparation, as the number of qubits (n) increases, the number of representable state parameters also increases, as shown in the "Number of CNOT gates (NCNOT)" column in Table 1 of the Appendix.
The CNOT gate is a type of two-qubit gate. It serves to flip the state of the second qubit (target qubit) if and only if the first qubit (control qubit) is |1>.
*8 Quantum coherence
A number between 0 and 1 that represents how much the quantum information has been degraded by device noise or other imperfections. The quantum coherence index equals 1 when the information is first input into the quantum processor and is still intact. If the quantum coherence index is equal to zero, it means that the original information is completely lost.
One of the biggest issues that need to be addressed in the further development of quantum computers is how to cope with the gradual loss of information (the inability to maintain a coherent quantum state) caused by the noise inside the computer.
About The Tokyo University of Science
Tokyo University of Science (TUS) is a well-known and respected university, and the largest science-specialized private research university in Japan, with four campuses in central Tokyo and its suburbs and in Hokkaido. Established in 1881, the university has continually contributed to Japan's development in science through inculcating the love for science in researchers, technicians, and educators.
With a mission of "Creating science and technology for the harmonious development of nature, human beings, and society," TUS has undertaken a wide range of research from basic to applied science. TUS has embraced a multidisciplinary research approach and undertaken intensive study in some of today's most vital fields. TUS is a meritocracy where the best in science is recognized and nurtured. It is the only private university in Japan that has produced a Nobel Prize winner and the only private university in Asia to produce Nobel Prize winners within the natural sciences field.
■
Tokyo University of Science(About TUS)