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

DOI10.4230/LIPICS.MFCS.2020.8MaRDI QIDQ5089167zbMATH OpenOpenAlexFDO

Authors Kaspars Balodis, Jānis Iraids, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, J. Smotrovs, Jevgēnijs Vihrovs, Andris Ambainis, Kamil Khadiev

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/2007.03402

zbMATH Keywords

Dyck languagegrid pathquantum algorithmsquantum query complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(7)

• Quantum algorithms for string processing
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Quantum bounds for 2D-grid and Dyck language
• Quantum complexity for vector domination problem
• Near-optimal quantum algorithms for string problems
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• A framework of quantum strong exponential-time hypotheses

This page was built for publication: Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089167)