Quantum bounds for 2D-grid and Dyck language

DOI10.1007/S11128-023-03910-9MaRDI QIDQ6101583zbMATH OpenFDO

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

Publication date 1 June 2023

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

Full work available at URL https://doi.org/10.1007/S11128-023-03910-9

zbMATH Keywords

Dyck languagegrid pathquantum algorithmsquantum query complexity

Mathematics Subject Classification ID

Quantum computation (81P68)

Recommendations

• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
• Quantum algorithm for Dyck language with multiple types of brackets
• Quantum, stochastic, and pseudo stochastic languages with few states
• Upper bounds on quantum dynamics in arbitrary dimension
• scientific article; zbMATH DE number 2221158
• Lower bounds on the size of quantum automata accepting unary languages.
• Quantum Probabilistic Dyadic Second-Order Logic
• scientific article; zbMATH DE number 1405684
• QUANTUM DILOGARITHM
• Size lower bounds for quantum automata

Cites work

• An optimal quantum algorithm for the oracle identification problem
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• scientific article; zbMATH DE number 6667586 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum adversary (upper) bound
• Quantum algorithm for Dyck language with multiple types of brackets
• Quantum computation and quantum information. 10th anniversary edition
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
• Quantum lower bounds by quantum arguments
• Quantum speedups for exponential-time dynamic programming algorithms
• Reflections for quantum query algorithms
• Span programs and quantum algorithms for st-connectivity and claw detection
• Span programs are equivalent to quantum query algorithms
• Strengths and Weaknesses of Quantum Computing
• The String-to-String Correction Problem

Cited in

(1)

• Quantum property testing algorithm for the concatenation of two palindromes language

This page was built for publication: Quantum 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 Q6101583)