Quantum bounds for 2D-grid and Dyck language
Quantum bounds for 2D-grid and Dyck language
复制标题
二维网格和 Dyck 语言的量子界限
DOI：
10.1007/s11128-023-03910-9
复制
发表时间：
2023
影响因子：
2.5
通讯作者：
Ambainis A
中科院分区：
文献类型：
--
作者：
Ambainis A
We study the quantum query complexity of two problems. First, we consider the problem of determining whether a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at mostk. We call this the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\textsc {Dyck}}\,}}_{k,n}$$\end{document} problem. We prove a lower bound of, showing that the complexity of this problem increases exponentially ink. Herenis the length of the word. Whenkis a constant, this is interesting as a representative example of star-free languages for which a surprisingquery quantum algorithm was recently constructed by Aaronson et al. (Electron Colloquium Comput Complex (ECCC) 26:61, 2018). Their proof does not give rise to a general algorithm. Whenkis not a constant, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\textsc {Dyck}}\,}}_{k,n}$$\end{document} is not context-free. We give an algorithm with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( \sqrt{n}(\log {n})^{0.5k}\right) $$\end{document} quantum queries for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\textsc {Dyck}}\,}}_{k,n}$$\end{document} for allk. This is better than the trivial upper boundnfor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=o\left( \frac{\log (n)}{\log \log n}\right) $$\end{document}. Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the “balanced parentheses” problem into the grid, we show a lower bound offor the directed 2D grid andfor the undirected 2D grid. We present two algorithms for particular cases of the problem. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions
We study the quantum query complexity of two problems. First, we consider the problem of determining whether a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at mostk. We call this the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\textsc {Dyck}}\,}}_{k,n}$$\end{document} problem. We prove a lower bound of, showing that the complexity of this problem increases exponentially ink. Herenis the length of the word. Whenkis a constant, this is interesting as a representative example of star-free languages for which a surprisingquery quantum algorithm was recently constructed by Aaronson et al. (Electron Colloquium Comput Complex (ECCC) 26:61, 2018). Their proof does not give rise to a general algorithm. Whenkis not a constant, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\textsc {Dyck}}\,}}_{k,n}$$\end{document} is not context-free. We give an algorithm with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( \sqrt{n}(\log {n})^{0.5k}\right) $$\end{document} quantum queries for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\textsc {Dyck}}\,}}_{k,n}$$\end{document} for allk. This is better than the trivial upper boundnfor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=o\left( \frac{\log (n)}{\log \log n}\right) $$\end{document}. Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the “balanced parentheses” problem into the grid, we show a lower bound offor the directed 2D grid andfor the undirected 2D grid. We present two algorithms for particular cases of the problem. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions
登录
查看更多内容
任何大小为 N 的 AND-OR 公式都可以在量子计算机上在 N^{1/2 o(1)} 时间内计算
DOI：
10.1137/080712167
发表时间：
2010
期刊：
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
影响因子：
--
作者：
A. Ambainis;Andrew M. Childs;B. Reichardt;R. Spalek;Shengyu Zhang
通讯作者：
Shengyu Zhang
在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce
影响因子：
2.5
作者：
Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
通讯作者：
Seddighin, Saeed
可计算性、复杂性和语言 - 理论计算机科学基础
DOI：
--
发表时间：
2014
期刊：
Computer science and applied mathematics
影响因子：
--
作者：
Martin D. Davis;E. Weyuker
通讯作者：
E. Weyuker
具有多种类型括号的 Dyck 语言的量子算法
DOI：
--
发表时间：
2021
期刊：
International Conference on Unconventional Computation and Natural Computation
影响因子：
--
作者：
K. Khadiev;Dmitry Kravchenko
通讯作者：
Dmitry Kravchenko
2D 网格和 Dyck 语言的量子下界和上限
DOI：
--
发表时间：
2020
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
A. Ambainis;K. Balodis;Janis Iraids;K. Khadiev;Vladislavs Klevickis;Krisjanis Prusis;Yixin Shen;Juris Smotrovs;J. Vihrovs
通讯作者：
J. Vihrovs