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

Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 46-62页

作者： Laplante, Sophie Magniez, Frederic Univ Paris 11 CNRS LRI F-91405 Orsay France

We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted and unweighted methods of Ambainis and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for Boolean functions f in O(min(root nC(0)(f), root nC(1)(f))), where C-0, C-1 is the certificate complexity and n is the size of the input.

关键词： quantum computing lower bounds query complexity adversary method Kolmogorov complexity

来源：评论

学校读者我要写书评

暂无评论

Quantum query complexity of Entropy Estimation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第5期65卷 2899-2921页

作者： Li, Tongyang Wu, Xiaodi Univ Maryland Inst Adv Comp Studies Dept Comp Sci College Pk MD 20742 USA Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA

Estimation of Shannon and Renyi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating alpha-Renyi entropies (Shannon entropy being 1-Renyi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for alpha-Renyi entropy estimation for all alpha >= 0 values, including tight bounds for the Shannon entropy, the Hartley entropy (alpha = 0), and the collision entropy (alpha = 2). We also provide quantum upper bounds for estimating min-entropy (alpha = +infinity) as well as the Kullback-Leibler divergence. We complement our results with quantum lower bounds on alpha-Renyi entropy estimation for all alpha >= 0 values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH);however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro's approach to estimating the expected output of quantum subroutines for alpha = 0, 1;2) we develop a procedure, similar to cooling schedules in simulated annealing, for general alpha >= 0, and 3) in the cases of integer alpha >= 2 and alpha = + infinity, we reduce the entropy estimation problem to the alpha-distinctness and inverted left perpendicular log n inverted right perpendicular-distinctness problems, respectively.

关键词： Statistical property testing sampling entropy estimation quantum information query complexity

来源：评论

学校读者我要写书评

暂无评论

The quantum query complexity of the abelian hidden subgroup problem

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-2期380卷 115-126页

作者： Koiran, Pascal Nesme, Vincent Portier, Natacha Ecole Normale Super Lyon Lab Informat Parallelisme F-69364 Lyon 07 France

Simon, in his FOCS'94 paper, was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon's problem from the point of view of quantum query complexity and give here a first non-trivial lower bound on the query complexity of a hidden subgroup problem, namely Simon's problem. More generally, we give a lower bound which is optimal up to a constant factor for any abelian group. (C) 2007 Elsevier B.V. All rights reserved.

关键词： quantum computing query complexity lower bounds polynomial method hidden subgroup problems Simon's problem

来源：评论

学校读者我要写书评

暂无评论

On the query complexity of selecting minimal sets for monotone predicates

引用

ARTIFICIAL INTELLIGENCE 2016年 233卷 73-83页

作者： Janota, Mikolas Marques-Silva, Joao IST INESC ID Lisbon Portugal

Propositional Satisfiability (SAT) solvers are routinely used for solving many function problems. A natural question that has seldom been addressed is: what is the number of calls to a SAT solver for solving some target function problem? This article improves upper bounds on the query complexity of solving several function problems defined on propositional formulas. These include computing the backbone of a formula and computing the set of independent variables of a formula. For the general case of monotone predicates, the article improves upper bounds on the query complexity of computing a minimal set when the number of minimal sets is constant. This applies for example to the computation of a minimal unsatisfiable subset (MUS) for CNF formulas, but also to the computation of prime implicants and implicates, with immediate application in a number of AI settings. (C) 2016 Elsevier B.V. All rights reserved.

关键词： query complexity Monotone predicates Minimal set SAT Backbone Minimal unsatisfiable set Minimal correction set Independent variables

来源：评论

学校读者我要写书评

暂无评论

query complexity of correlated equilibrium

Query complexity of correlated equilibrium

引用

作者： Babichenko, Yakov Barman, Siddharth Center for the Mathematics of Information California Institute of Technology United States

We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box that returns players' utilities at pure action profiles. In this model, we establish that in order to compute a correlated equilibrium, any deterministic algorithm must query the black box an exponential (in n) number of times. © 2015 ACM 2167-8375/2015/07-ART22 $15.00.

关键词： Computation of equilibrium Correlated equilibrium query complexity

来源：评论

学校读者我要写书评

暂无评论

Improving Quantum query complexity of Boolean Matrix Multiplication Using Graph Collision

引用

ALGORITHMICA 2016年第1期76卷 1-16页

作者： Jeffery, Stacey Kothari, Robin Le Gall, Francois Magniez, Frederic Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada Univ Waterloo Inst Quantum Comp Waterloo ON Canada Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan Univ Paris Diderot Sorbonne Paris Cite Paris France

The quantum query complexity of Boolean matrix multiplication is typically studied as a function of the matrix dimension, , as well as the number of s in the output, . We prove an upper bound of for all values of . This is an improvement over previous algorithms for all values of . On the other hand, we show that for any and any , there is an lower bound for this problem, showing that our algorithm is essentially tight. We first reduce Boolean matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently. Using similar ideas, we also show that the time complexity of Boolean matrix multiplication is .

关键词： Quantum algorithms Boolean matrix multiplication query complexity

来源：评论

学校读者我要写书评

暂无评论

A large lower bound on the query complexity of a simple boolean function

引用

INFORMATION PROCESSING LETTERS 2005年第4期95卷 423-428页

作者： Bollig, B JWG Univ Frankfurt D-60054 Frankfurt Germany

Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron (1998) and inspired by Rubinfeld and Sudan (1996), deals with the relaxation of decision problems. Given a property P the aim is to decide whether a given input satisfies the property P or is far from having the property. For a family of boolean functions f = (f(n)) the associated property is the set of 1-inputs of f. Here, the known lower bounds on the query complexity of properties identified by boolean functions representable by (very) restricted branching programs of small size is improved up to Omega(n(1/2)), where n is the input length. (c) 2005 Elsevier B.V. All rights reserved.

关键词： computational complexity branching programs property testing query complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards effective genomic information retrieval: The impact of query complexity and expansion strategies

引用

JOURNAL OF INFORMATION SCIENCE 2010年第2期36卷 194-208页

作者： Mu, Xiangming Lu, Kun Univ Wisconsin Sch Informat Studies Milwaukee WI 53211 USA

The goal of this study is to examine the influence of query complexity and different query expansion strategies on the effectiveness of genomic information retrieval. query complexity is defined as the average number of terms in a query. The query expansion strategies are based on the Unified Medical Language System (UMLS) Metathesaurus. The combination of string/word indexing on concept/term level provides four different automatic UMLS expansion strategies. The test collection for the study is the TREC Genomic Track 2006 data set (24 topics). We use the Mean Average Precision (MAP), 11-point precision/recall, and average precision/recall at maximum recall point for the retrieval performance evaluation. In general, we found that applying query expansion did not improve the retrieval effectiveness as compared to the baseline. Our results also indicated that string index expansions are more effective than word index expansions. Queries with a smaller number of terms outperform queries with a larger number of terms and the difference is statistically significant. String index on term level is the best automatic UMLS expansion strategy for queries with a smaller number of terms. The worst case scenario is applying word index expansions on queries with a larger number of terms. Based on these findings, we recommend that genomic information retrieval systems should support flexible query expansion strategies to best accommodate queries with different levels of complexity.

关键词： health information retrieval query complexity query expansion Unified Medical Language System Metathesaurus

来源：评论

学校读者我要写书评

暂无评论

Quantum query complexity of Unitary Operator Discrimination

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2019年第3期E102D卷 483-491页

作者： Kawachi, Akinori Kawano, Kenichi Le Gall, Francois Tamaki, Suguru Osaka Univ Dept Informat & Commun Technol Suita Osaka 5650871 Japan Tokushima Univ Tokushima Tokushima 7708506 Japan Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Kyoto Univ Informat Kyoto 6068501 Japan

Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U is an element of S := {U-1, U-2} under some probability distribution over S, the goal is to decide whether U = U-1 or U = U-2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using inverted right perpendicular root 6 theta(-1)(cover) inverted left perpendicular queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter theta(cover), which is determined by the eigenvalues of U dagger U-1(2), represents the "closeness" between U-1 and U-2. We also show that this upper bound is essentially tight: we prove that for every theta(cover) > 0 there exist operators U-1 and U-2 such that any quantum algorithm solving this problem with bounded error probability requires at least inverted right perpendicular 2/3 theta cover inverted left perpendicular queries under uniform distribution over S.

关键词： quantum algorithms quantum information theory query complexity

来源：评论

学校读者我要写书评

暂无评论

HARDNESS OF CONTINUOUS LOCAL SEARCH: query complexity AND CRYPTOGRAPHIC LOWER BOUNDS

引用

SIAM JOURNAL ON COMPUTING 2020年第6期49卷 1128-1172页

作者： Hubacek, Pavel Yogev, Eylon Charles Univ Prague Prague Czech Republic Boston Univ Boston MA 02215 USA Tel Aviv Univ IL-6997801 Tel Aviv Israel

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g., via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts, the optimization problem is defined by a continuous function which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class CLS [C. Daskalakis and C. H. Papadimitriou, Proceedings of SODA'11, 2011], which is contained in the intersection of PLS and PPAD, two important subclasses of TFNP (the class of NP search problems with a guaranteed solution). In this work, we show the first hardness results for CLS (the smallest nontrivial class among the currently defined subclasses of TFNP). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions. Our results demonstrate a strong conceptual barrier precluding design of efficient algorithms for solving local search problems even over continuous domains. As our main technical contribution we introduce a new total search problem which we call END-OF-METERED-LINE. The special structure of END-OF-METERED-LINE enables us to (1) show that it is contained in CLS, (2) prove hardness for it in both the black-box and the white-box setting, and (3) extend to CLS a variety of results previously known only for PPAD.

关键词： CLS continuous local search cryptographic hardness PLS PPAD query complexity TFNP

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：