Source: School of Physics
Written by: School of Physics
Edited by: Wang Dongmei

Automaton is a fundamental computing model that has wide applications in computer science. Similar to quantum computer — by changing the basic elements of a computer from bits and logic gates to quantum bits and quantum logic gates, quantum automaton is the quantum version of classical automaton. It has been theoretically predicted that quantum finite automaton (QFA) can solve certain problems more efficiently than its classical counterpart. However, by now, no experiment has been performed to prove the quantum benefits of QFA yet.

Recently, Professor Xiaoqi Zhou’s group from the School of Physics, Sun Yat-sen University has made important progress in the experimental research of quantum automaton. They experimentally realized a quantum finite automaton based on linear optical system. The quantum automaton is used to solve the promise problems of determining whether the length of an input string can be divided by a prime number P with no remainder or with a remainder of R utilizing a state space with only three orthonormal states, whereas the classical automaton needs no less than P states. They experimentally demonstrate the space complexity advantage of a quantum automaton over its classical counterpart for the first time and paves the way for implementing quantum automaton for more complicated and practical applications.


The above work entitled "Experimental demonstration of quantum finite automaton" was published in npj Quantum Information (IF: 9.206) in June 2019. The first authors are Yuling Tian and Tianfeng Feng who contributed equally. The corresponding authors are Professor Xiaoqi Zhou and Associate Professor Shenggen Zheng of Pengcheng Laboratory. This work was supported by the National Key Research and Development Program, the Key Research and Development Program of Guangdong Province of China, the Natural Science Foundation of Guangdong Province of China and the State Key Laboratory of Optoelectronic Materials and Technologies of Sun Yat-sen University.

Link to the paper: https://www.nature.com/articles/s41534-019-0163-x