检索结果-内蒙古大学图书馆

randomized decision tree complexity of Deutsch-Jozsa problem and a generalization

QUANTUM INFORMATION PROCESSING 2024年第3期23卷 79-79页

作者： Xu, Guoliang Qiu, Daowen Zhang, Binbin Wang, Tianyin Zhang, Yongxin Luoyang Normal Univ Coll Informat Technol Luoyang 471934 Peoples R China Sun Yat sen Univ Inst Quantum Comp & Comp Theory Sch Comp Sci & Engn Guangzhou 510006 Peoples R China Luoyang Normal Univ Fac Math Sci Luoyang 471934 Peoples R China

Deutsch-Jozsa problem (DJn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$DJ_{n}$$\end{document}) showed for the first time that quantum computation can achieve exponential advantages over classical computers, which encouraged and laid the foundation for further research on quantum algorithms. A generalization of Deutsch-Jozsa problem (DJnk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$DJ<^>{k}_{n}$$\end{document}, proposed by Phys Rev A 97:062331, 2018) maintains the exponential advantage when the parameter k is a constant. However, these achieved exponential advantages are just in the case that all outputs are required to be accurate. In contrast, this paper studies classical randomized decision tree complexities of DJn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$DJ_{n}$$\end{document} and DJnk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$DJ<^>{k}_{n}$$\end{document}. It is proved that the first complexity R2(DJn)<= 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_complexity(DJ_{n})\le 3$$\end{document} in all cases and the second complexity R2(DJnk)\documentclass[12pt]{

关键词： Quantum computation Quantum algorithm and complexity randomized decision tree complexity Boolean function

来源：评论

学校读者我要写书评

暂无评论

TIGHT BOUNDS FOR randomized AND QUANTUM LOCAL SEARCH

引用

SIAM JOURNAL ON COMPUTING 2009年第3期39卷 948-977页

作者： Zhang, Shengyu Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in theoretical computer science. In this paper, we study the problem in both the randomized and the quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0, 1}(n) and the constant-dimensional grids [n](d), two particular product graphs that recently drew much attention, we get the following tight results: RLS({0, 1}(n)) = Theta(2(n)/(2)n(1/2)), QLS({0, 1}(n)) = Theta(2(n/3)n(1/6)), RLS([n](d)) = Theta(n(d/2)) for d >= 4, QLS([n](d)) = Theta(n(d/3)) for d >= 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465-474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494-501]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n](2), a new quantum algorithm using O(root n(log log n)(1.5)) queries is given. This improves the previously best known upper bound of O(n(2/3)) (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465-474]), and implies that Local Search on grids exhibits different properties in low dimensions.

关键词： optimization local search quantum algorithm quantum query complexity randomized algorithm randomized decision tree complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：