Quantum algorithm proposed to solve Dyck language problems

A joint French-Russian-Latvian research saw light in Leibniz International Proceedings in Informatics.

Co-author, Senior Research Associate of the KFU Quantum Informatics Lab Kamil Khadiev, explains, "The Dyck problem is designed to check the program code and allows you to find out whether it satisfies the rules or not. The problem, on the one hand, is an important subtask of parsers and compilers, and on the other hand, it is interesting from a theoretical point of view. The classical solution to the problem has been known for a long time, but no one thought about a quantum algorithm for the problem until 2018. Particular attention to the construction of a quantum algorithm for the Dyck problem appeared after a publication by Scott Aaronson and his co-authors two years ago. Aaronson showed, in particular, that a program for an ordinary computer would solve the problem for a year, but on a quantum computer it can be solved in a few seconds."

In the paper, Khadiev and his colleagues demonstrated an algorithm that can solve the problem in 40 seconds and also proved that it cannot be solved in less than 10 second on a quantum computer.

"Scientists are developing quantum algorithms in parallel with the creation of the quantum computer itself. The emergence of another effective algorithm spurs physicists to create quantum computers as soon as possible and makes the prospect of a quantum computer more and more enticing," adds Khadiev.

More information:
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

drops.dagstuhl.de/opus/volltexte/2020/12677/

Provided by Kazan Federal University