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

Conference on quantum Information and Computation V

作者： Dubrovska, Alina Univ Latvia Dept Comp Sci LV-1459 Riga Latvia

ISBN: (纸本)9780819466952

quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box, but the aim is to compute function value for arbitrary input using as few queries as possible. In this paper we concentrate on quantum query algorithm designing tasks. The main aim of research was to find new efficient algorithms and develop general algorithm designing techniques. We present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next we introduce algorithm transformation methods that allow significant enlarging of sets of exactly computable functions. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries.

关键词： quantum computing quantum query algorithms complexity theory Boolean functions algorithm design

来源：评论

学校读者我要写书评

暂无评论

The Power of Adaptivity in quantum query algorithms 2024

The Power of Adaptivity in Quantum Query Algorithms

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Girish, Uma Sinha, Makrand Tal, Avishay Wu, Kewen Princeton Univ Princeton NJ 08544 USA Univ Illinois Champaign IL USA Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9798400703836

Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with r versus r-1 rounds of adaptivity. We do so by using the k-fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP18). For k=2r, this problem can be solved using an r round quantum algorithm with only one query per round, yet we show that any r-1 round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round. Our results are proven following the Fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the Fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.

关键词： quantum query algorithms query Adaptivity Forrelation quantum Advantages Fourier Analysis of Boolean Functions

来源：评论

学校读者我要写书评

暂无评论

Properties and application of nondeterministic quantum query algorithms - art. no. 657310

Properties and application of nondeterministic quantum query...

引用

Conference on quantum Information and Computation V

作者： Dubrovska, Alina Univ Latvia Dept Comp Sci LV-1459 Riga Latvia

ISBN: (纸本)9780819466952

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require 0(n) queries.

关键词： quantum computing quantum query algorithms complexity theory Boolean functions nondeterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

quantum query algorithms for Automorphisms of Galois Groups

Quantum Query Algorithms for Automorphisms of Galois Groups

引用

2013 2nd International Symposium on Computer,Communication,Control and Automation(3CA 2013)

作者： Agnis ?ku?kovniks Rūsi?? Freivalds Faculty of Computing University of Latvia Institute of Mathematics and Computer Science University of Latvia

In this paper we study quantum query complexity of exactly(with probability 1) deciding the parity of npermutations of numbers(from 0 to n-1). We show that for this non-Boolean problem use of quantum complexity techniques gives quite strong results as it does for other, but Boolean problems. We use Galois Theory to find new problems where quantum query algorithms are more efficient than deterministic ones.

关键词： quantum computin quantum query algorithms galois groups permutations

来源：评论

学校读者我要写书评

暂无评论

Exact quantum 1-query algorithms and Complexity

引用

SPIN 2021年第3期11卷

作者： Qiu, Daowen Xu, Guoliang Sun Yat Sen Univ Sch Comp Sci & Engn Inst Quantum Comp & Comp Theory Guangzhou 510006 Peoples R China

Deutsch-Jozsa problem (D-J) has exact quantum 1-query complexity ("exact" means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D-J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D-J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D-J algorithm. Further problems are pointed out for future study.

关键词： quantum computation quantum query algorithms quantum query complexity Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Improved bounds on quantum learning algorithms

引用

quantum INFORMATION PROCESSING 2005年第5期4卷 355-386页

作者： Atici, Alp Servedio, Rocco A. Columbia Univ Dept Math New York NY 10027 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. [quantum Information Processing, to appear] conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is O (log vertical bar C vertical bar/root gamma C), where gamma(C) is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function front C using O(log vertical bar C vertical bar log log vertical bar C vertical bar/root gamma(C)) quantum black box queries. We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). We give positive and negative results on when the quantum and classical query complexities of these intermediate problems are polynomially related to each other. Finally, we improve the known lower bounds on the number of quantum examples (as opposed to quantum black-box queries) required for (epsilon, delta)-PAC learning any concept class of Vapnik-Chervonenkis dimension d over the domain {0, 1}(n) front Omega (d/n) to Omega(1/epsilon log 1/delta +d+ root d/epsilon). This new lower bound comes closer to matching known upper bounds for classical PAC learning.

关键词： quantum query algorithms quantum computation computational learning theory PAC learning

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for learning and testing juntas

引用

quantum INFORMATION PROCESSING 2007年第5期6卷 323-348页

作者： Atici, Alp Servedio, Rocco A. Citadel Investment Group Chicago USA Department of Computer Science Columbia University New York USA

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop efficient algorithms: (1) whose sample complexity has no dependence on n, the dimension of the domain the Boolean functions are defined over;(2) with no access to any classical or quantum membership ("black-box") queries. Instead, our algorithms use only classical examples generated uniformly at random and fixed quantum superpositions of such classical examples;(3) which require only a few quantum examples but possibly many classical random examples (which are considered quite "cheap" relative to quantum examples). Our quantum algorithms are based on a subroutine FS which enables sampling according to the Fourier spectrum of f;the FS subroutine was used in earlier work of Bshouty and Jackson on quantum learning. Our results are as follows: (1) We give an algorithm for testing k-juntas to accuracy epsilon that uses O(k/is an element of) quantum examples. This improves on the number of examples used by the best known classical algorithm. ( 2) We establish the following lower bound: any FS-based k-junta testing algorithm requires Omega (root k) queries. (3) We give an algorithm for learning k-juntas to accuracy is an element of that uses O(is an element of(-1)k log k) quantum examples and O(2(k) log(1/is an element of)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound.

关键词： Juntas quantum query algorithms quantum property testing computational learning theory quantum computation lower bounds

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for Learning Symmetric Juntas via the Adversary Bound

引用

COMPUTATIONAL COMPLEXITY 2015年第2期24卷 255-293页

作者： Belovs, Aleksandrs MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends *** h is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively. We analyze the general case using the adversary bound and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is ) or the exact-half function (complexity is ). The first algorithm resolves an open problem from Ambainis & Montanaro (quantum Inf Comput 14(5&6): 439-453, 2014). For the case when h is the majority function, we prove an upper bound of . All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomized complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

关键词： quantum query algorithms computational learning theory combinatorial group testing representation theory of the symmetric group semi-definite optimization

来源：评论

学校读者我要写书评

暂无评论

quantum lower bounds by quantum arguments

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2002年第4期64卷 750-767页

作者： Ambainis, A Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA

We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new Omega(rootN) lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via a variety of different techniques. (C) 2002 Elsevier Science (USA).

关键词： quantum computing quantum lower bounds quantum query algorithms

来源：评论

学校读者我要写书评

暂无评论

quantum walk algorithm for element distinctness

引用

SIAM JOURNAL ON COMPUTING 2007年第1期37卷 210-239页

作者： Ambainis, Andris Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 2T2 Canada

We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness ( the problem of finding two equal items among N given items), we get an O(N-2/3) query quantum algorithm. This improves the previous O(N-3/4) quantum algorithm of Buhrman et al. [SIAM J. Comput., 34 ( 2005), pp. 1324-1330] and matches the lower bound of Aaronson and Shi [J. ACM, 51 ( 2004), pp. 595-605]. We also give an O(Nk/(k+1)) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

关键词： quantum computing quantum query algorithms element distinctness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：