Quantum algorithm proposed to solve Dyck language problems

September 04, 2020

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.

Kazan Federal University

Related Quantum Computer Articles from Brightsurf:

UCLA computer scientists set benchmarks to optimize quantum computer performance
Two UCLA computer scientists have shown that existing compilers, which tell quantum computers how to use their circuits to execute quantum programs, inhibit the computers' ability to achieve optimal performance.

Simulating quantum 'time travel' disproves butterfly effect in quantum realm
Using a quantum computer to simulate time travel, researchers have demonstrated that, in the quantum realm, there is no 'butterfly effect.' In the research, information--qubits, or quantum bits--'time travel' into the simulated past.

Solving materials problems with a quantum computer
Scientists at Argonne and the University of Chicago have developed a method paving the way to using quantum computers to simulate realistic molecules and complex materials.

Orbital engineering of quantum confinement in high-Al-content AlGaN quantum well
Recently, professor Kang's group focus on the limitation of quantum confine band offset model, the hole states delocalization in high-Al-content AlGaN quantum well are understood in terms of orbital intercoupling.

Quantum leap: Photon discovery is a major step toward at-scale quantum technologies
A team of physicists at the University of Bristol has developed the first integrated photon source with the potential to deliver large-scale quantum photonics.

Wiring the quantum computer of the future: A novel simple build with existing technology
Efficient quantum computing is expected to enable advancements that are impossible with classical computers.

To tune up your quantum computer, better call an AI mechanic
A paper in the journal Physical Review Applied outlines a way to teach an AI to make an interconnected set of adjustments to the quantum dots that could form the qubits in a quantum computer's processor.

USTC realizes the first quantum-entangling-measurements-enhanced quantum orienteering
Researchers enhanced the performance of quantum orienteering with entangling measurements via photonic quantum walks.

Computer-based weather forecast: New algorithm outperforms mainframe computer systems
The exponential growth in computer processing power seen over the past 60 years may soon come to a halt.

What a pair! Coupled quantum dots may offer a new way to store quantum information
Researchers at the National Institute of Standards and Technology (NIST) and their colleagues have for the first time created and imaged a novel pair of quantum dots -- tiny islands of confined electric charge that act like interacting artificial atoms.

Read More: Quantum Computer News and Quantum Computer Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.