Our graduate student's research results on quantum algorithms were accepted by the top international academic conference SODA 2024
Recently, the research paper Recovering the Original Simplicity: Succinct and Deterministic Quantum Algorithm for the Welded Tree Problem from the Institute of Quantum Computing and Software, School of Computer Science, Sun Yat-sen University was accepted by the top international academic conference SODA. The School of Computer Science, Sun Yat-sen University is the only signing unit of the paper. The authors of the paper are in alphabetical order: Guanzhong Li, Lvzhou Li, and Jingquan Luo. Guanzhong Li and Jingquan Luo are respectively the doctoral and master students of Professor Li Lvzhou's team. The paper re-examines the welding tree problem, which has attracted much attention in the field of quantum algorithms, and designs a simple deterministic quantum algorithm with exponential acceleration advantages to solve the problem based on the coin quantum walk model. This not only breaks the stereotype that coin quantum walks can only achieve quadratic acceleration over classical algorithms, but also provides new ideas for simplifying existing quantum walk-based algorithms. According to statistics, this is the first paper in the history of SODA that focuses on quantum algorithms with all the signing units from research institutions in mainland China.
Welding Tree Problem
The welding tree problem is one of the few problems based on quantum walks that show the advantage of quantum exponential acceleration. Figuratively speaking, the problem is to find the exit from the entrance of a maze, and each step can only explore the positions connected by paths around. The "maze" here is two complete binary trees of depth n, which are placed horizontally opposite to each other, and the leaves in the middle are randomly "welded" alternately from left to right to form a loop, as shown by the dotted line in the figure below. Assume that the information of the "maze" is stored in an adjacency list. Then, every step in the "maze" requires accessing the adjacency table once to obtain the adjacent information of the current position. The welding tree problem requires accessing the adjacency table as little as possible to find the exit from the entrance, where the number of times the adjacency table is accessed is called the query complexity. It can be proved that the query complexity of any classical algorithm for this problem is exponential in n, that is, Ω(2n)。
指数加速确定性量子算法
Exponentially speeding up deterministic quantum algorithms
For the welding tree problem, the above paper designs a concise and efficient deterministic quantum algorithm based on a simple and intuitive coin quantum walk model. The value of this work is reflected in the following points: (1) Compared with the algorithm of Jeffery and Zur (STOC'2023), the resulting quantum algorithm is quite simple, which not only breaks the stereotype that the coin quantum walk can only achieve quadratic acceleration over the classical algorithm, but also demonstrates the power of the simplest quantum walk model; (2) The resulting quantum algorithm can theoretically be 100% successful, while existing quantum algorithms inevitably have a probability of failure. This may also change people's view that since quantum mechanics is essentially random, it is impossible to have a deterministic quantum algorithm with exponential acceleration to solve the welding tree problem; (3) The concise algorithm ideas presented in the paper are very inspiring. As one reviewer said: "This paper may open up a new research route to simplify existing quantum walk-based algorithms and improve their efficiency."
Introduction to SODA Conference
SODA (ACM-SIAM Symposium of Discrete Algorithms) is a top international conference in the field of algorithms, focusing on the research of efficient algorithms and related data structures for solving discrete problems. Together with STOC and FOCS, it is recognized as the three top academic conferences in theoretical computer science and enjoys a high reputation in the field of computer science.
Source: Party and Government Office of the College
Editors: Li Junyu, Wu Xiaohong
First review: Wang Dongmei
Reviewer: Yan Xiaohui
Review and release: Ma Xiao
