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

quantum query complexity for Searching Multiple Marked States from an Unsorted Database

Communications in Theoretical Physics 2007年第2X期48卷 264-266页

作者： SHANG Bin School of Computer Science & Technology Beijing Institute of Technology Beijing 100081 China

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.

关键词： quantum algorithm unsorted database search problem quantum query complexity

来源：评论

学校读者我要写书评

暂无评论

quantum query complexity of Almost All Functions with Fixed On-set Size

引用

COMPUTATIONAL complexity 2016年第4期25卷 723-735页

作者： Ambainis, Andris Iwama, Kazuo Nakanishi, Masaki Nishimura, Harumichi Raymond, Rudy Tani, Seiichiro Yamashita, Shigeru Univ Latvia Inst Math & Comp Sci Riga Latvia Kyoto Univ Sch Informat Kyoto Japan Yamagata Univ Fac Educ Art & Sci Yamagata Japan Nagoya Univ Grad Sch Informat Sci Nagoya Aichi Japan IBM Japan Ltd IBM Res Tokyo Tokyo Japan NTT Corp NTT Commun Sci Labs Atsugi Kanagawa Japan Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu Japan

This paper considers the quantum query complexity of almost all functions in the set of -variable Boolean functions with on-set size , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in except its polynomially small fraction, the quantum query complexity is Theta (logM/c+log N- log log M + root N) for a constant . This is quite different from the quantum query complexity of the hardest function in F-N,F-M : Theta (root N logM/c+log N- log log M + root N) . In contrast, almost all functions in have the same randomized query complexity as the hardest one, up to a constant factor.

关键词： quantum query complexity Boolean functions On-set size

来源：评论

学校读者我要写书评

暂无评论

quantum query complexity OF MINOR-CLOSED GRAPH PROPERTIES

引用

SIAM JOURNAL ON COMPUTING 2012年第6期41卷 1426-1450页

作者： Childs, Andrew M. Kothari, Robin Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an n-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties-those that cannot be characterized by a finite set of forbidden subgraphs-have quantum query complexity Theta(n(3/2)). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n(3/2)) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

关键词： quantum query complexity quantum algorithms lower bounds graph minors graph properties

来源：评论

学校读者我要写书评

暂无评论

quantum query complexity of Subgraph Isomorphism and Homomorphism 33

Quantum Query Complexity of Subgraph Isomorphism and Homomor...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kulkarni, Raghav Podder, Supartha Ctr Quantum Technol Singapore Singapore Nanyang Technol Univ Singapore Singapore

ISBN: (纸本)9783959770019

Let H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f( H) (G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha(H )denote the cardinality of a maximum independent set of H. In this paper we show: Q(f(H)) = Omega(root alpha(H) . n), where Q(f (H)) denotes the quantum query complexity of f (H). As a consequence we obtain lower bounds for Q(f (H)) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that Q(f (H)) = Omega(n(3/4)) for any H, improving on the previously best known bound of Omega(n(2/3)) [16]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n(3/4)) bound for Q(f (H)) matches the square root of the current best known bound for the randomized query complexity of f (H), which is Omega(n(3/2)) due to Groger. Interestingly, the randomized bound of Omega(alpha(H) . n) for f( H) still remains open. We also study the Subgraph Homomorphism Problem, denoted by f ([H]), and show that Q(f([H])) = Omega(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n(4/5)) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n(3/4)) bound. For the Subgraph Homomorphism, we obtain an Omega(n(3/2)) bound for the same.

关键词： quantum query complexity subgraph isomorphism monotone graph properties

来源：评论

学校读者我要写书评

暂无评论

quantum query complexity of state conversion

Quantum query complexity of state conversion

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Lee, Troy Mittal, Rajat Reichardt, Ben W. Spalek, Robert Szegedy, Mario Centre for Quantum Technologies United States University of Waterloo Canada Google Inc. United States Rutgers University United States

ISBN: (纸本)9780769545714

State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.

关键词： quantum query complexity adversary bound span program semi-definite program quantum walk Schur product operator norm

来源：评论

学校读者我要写书评

暂无评论

Upper Bounds on quantum query complexity Inspired by the Elitzur-Vaidman Bomb Tester

引用

THEORY OF COMPUTING 2016年 12卷

作者： Lin, Cedric Yen-Yu Lin, Han-Hsuan Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Natl Univ Singapore Ctr Quantum Technol Singapore Singapore

Inspired by the Elitzur-Vaidman bomb testing problem (1993), we introduce a new query complexity model, which we call bomb query complexity, B(f). We investigate its relationship with the usual quantum query complexity Q(f), and show that B(f) = Theta(Q(f)(2)). This result gives a new method to derive upper bounds on quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide non-constructive upper bounds on Q(f) = Theta(root B(f)). Subsequently, we were able to give explicit quantum algorithms matching our new bounds. We apply this method to the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with O(n(1.5)) quantum query complexity, improving the best known algorithm of O(n(1.5)logn) (Durr et al. 2006, Furrow 2008). Applying this method to the maximum bipartite matching problem gives an algorithm with O(n(1.75)) quantum query complexity, improving the best known (trivial) O(n(2)) upper bound.

关键词： algorithms query complexity quantum algorithms quantum query complexity graph algorithms Elitzur-Vaidman bomb tester adversary method maximum bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Polynomial degree vs. quantum query complexity

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2006年第2期72卷 220-238页

作者： Ambainis, A Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity Omega(M-1.321...). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a generalized version of the quantum adversary method. (c) 2005 Elsevier Inc. All rights reserved.

关键词： quantum lower bounds quantum query complexity polynomial degree of Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds on quantum query complexity for Read-Once Formulas with XOR and MUX Operators

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2010年第2期E93D卷 280-289页

作者： Fukuhara, Hideaki Takimoto, Eiji Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Kyushu Univ Dept Informat Fukuoka 8190395 Japan

We introduce a complexity measure r for the class F of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class F, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in F, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.

关键词： quantum query complexity read-once formulas decision trees adversary method

来源：评论

学校读者我要写书评

暂无评论

On the quantum query complexity of Local Search in Two and Three Dimensions

引用

ALGORITHMICA 2009年第3期55卷 576-600页

作者： Sun, Xiaoming Yao, Andrew Chi-Chih Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed da parts per thousand yen5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n](2) is Omega(n (1/2-delta) ), and that for the 3-dimensional grid [n](3) is Omega(n (1-delta) ), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (based on Ambainis' adversary method for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemer,di, Bose and Chowla, and Halasz from combinatorial number theory, as well as less familiar probability tools like Esseen's Inequality.

关键词： Local search quantum query complexity

来源：评论

学校读者我要写书评

暂无评论

The quantum query complexity of elliptic PDE

引用

JOURNAL OF complexity 2006年第5期22卷 691-725页

作者： Heinrich, Stefan Univ Kaiserslautern Dept Comp Sci D-67653 Kaiserslautern Germany

The query complexity of the following numerical problem is studied in the quantum model of computation: consider a general elliptic partial differential equation of order 2m in a smooth, bounded domain Q subset of R(d) with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold M subset of Q of dimension 0 <= d(1) <= d. With the right-hand side belonging to C(r)(Q), and the error being measured in the Loo (M) norm, we prove that the nth minimal quantum error is (up to logarithmic factors) of order n(-min((r+2m)/d1.r/d+ 1)). For comparison, in the classical deterministic setting the nth minimal error is known to be of order n(-r/d), for all d(1), while in the classical randomized setting it is (up to logarithmic factors) n(-min((r+2m)/dt,r/d+ 1/2)). (C) 2006 Elsevier Inc. All rights reserved.

关键词： elliptic partial differential equation weakly singular operator quantum algorithm quantum query complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：