Quantum bounds for 2D-grid and Dyck language

DOI10.1007/s11128-023-03910-9MaRDI QIDQ6101583

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

Publication date: 1 June 2023

Published in: Quantum Information Processing (Search for Journal in Brave)

zbMATH Keywords

quantum algorithmsquantum query complexityDyck languagegrid path

Mathematics Subject Classification ID

Quantum computation (81P68)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum algorithm for Dyck language with multiple types of brackets
• Quantum Adversary (Upper) Bound
• Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Quantum Computation and Quantum Information
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• Span Programs are Equivalent to Quantum Query Algorithms
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Strengths and Weaknesses of Quantum Computing
• The String-to-String Correction Problem
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
• Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
• Quantum lower bounds by quantum arguments

This page was built for publication: Quantum bounds for 2D-grid and Dyck language