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

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete Algorithms

作者： Ben W. Reichardt School of Computer Science and Institute for Quantum Computing University of Waterloo

ISBN: (纸本)9780898719932

We show that any boolean function can be evaluated optimally by a quantum query algorithm that alternates a certain fixed, input-independent reflection with a second reflection that coherently queries the input string. Originally introduced for solving the unstructured search problem, this two-reflections structure is therefore a universal feature of quantum algorithms. Our proof goes via the general adversary bound, a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. By a quantum algorithm for evaluating span programs, this lower bound is known to be tight up to a sub-logarithmic factor. The extra factor comes from converting a continuous-time query algorithm into a discrete-query algorithm. We give a direct and simplified quantum algorithm based on the dual SDP, with a boundederror query complexity that matches the general adversary bound. Therefore, the general adversary lower bound is tight; it is in fact an SDP for quantum query complexity. This implies that the quantum query complexity of the composition f o (g,..., g) of two boolean functions f and g matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. It efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It further shows that span programs are equivalent to quantum query algorithms.

关键词： quanta Boolean functions algorithms Reflection Service Discovery Protocol input string

来源：评论

学校读者我要写书评

暂无评论

Classical Simulation of Entanglement Swapping with Bounded Communication

引用

Physical Review Letters 2012年第10期109卷 100401-100401页

作者： Cyril Branciard Nicolas Brunner Harry Buhrman Richard Cleve Nicolas Gisin Samuel Portmann Denis Rosset Mario Szegedy School of Mathematics and Physics The University of Queensland St Lucia QLD 4072 Australia H. H. Wills Physics Laboratory University of Bristol Bristol BS8 1TL United Kingdom Centrum Wiskunde & Informatica and University of Amsterdam Science Park 123 1098 XG Amsterdam The Netherlands Institute for Quantum Computing and School of Computer Science University of Waterloo 200 University Avenue West Waterloo Ontario Canada N2L 3G1 Perimeter Institute for Theoretical Physics 31 Caroline Street North Waterloo Ontario Canada N2L 2Y5 Group of Applied Physics University of Geneva Chemin de Pinchat 22 CH-1211 Geneva 4 Switzerland Department of Computer Science Rutgers the State University of New Jersey 110 Frelinghuysen Road Piscataway New Jersey 08854-8019 USA

Entanglement appears under two different forms in quantum theory, namely, as a property of states of joint systems and as a property of measurement eigenstates in joint measurements. By combining these two aspects of entanglement, it is possible to generate nonlocality between particles that never interacted, using the protocol of entanglement swapping. We show that even in the more constraining bilocal scenario where distant sources of particles are assumed to be independent, i.e., to share no prior randomness, entanglement swapping can be simulated classically with bounded communication, using only 9 bits in total. Our result thus provides an upper bound on the nonlocality of the entanglement swapping process.

关键词： quantum entanglement computer simulation COMMUNICATION BOUNDS (Mathematics) JOINTS (Engineering) PARTICLES (Nuclear physics)

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for QMA-complete problems

Approximation algorithms for QMA-complete problems

引用

IEEE Annual Conference on Computational Complexity

作者： Gharibian, Sevag Kempe, Julia David R. Cheriton School of Computer Science Institute for Quantum Computing University of Waterloo Waterloo Canada Blavatnik School of Computer Science Tel Aviv University Tel Aviv Israel CNRS LIAFA Université Paris 7 Paris France

ISBN: (纸本)9780769544113

Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p. 193 (1999)] to the quantum setting, and might be of independent interest. © 2011 IEEE.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

QIP = PSPACE

QIP = PSPACE

引用

作者： Jain, Rahul Ji, Zhengfeng Upadhyay, Sarvagya Watrous, John Department of Computer Science National University of Singapore 3 Science Drive 2 Singapore 117543 Singapore Perimeter Institute for Theoritical Physics 31 Caroline Street North Waterloo ON Canada Cheriton School of Computer Science Institute for Quantum Computing University of Waterloo 200 University Avenue West Waterloo ON N2L 3G1 Canada

This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model's natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations. © 2011.

关键词： Turing machines

来源：评论

学校读者我要写书评

暂无评论

quantum snake walk on graphs

引用

Physical Review A 2011年第2期83卷 022304-022304页

作者： Ansis Rosmanis []David R. Cheriton School of Computer Science and Institute for Quantum Computing University of Waterloo West Waterloo Ontario Canada N2L 3G1

I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

关键词： quantum theory PHYSICS quantum computers computer algorithms HAMILTONIAN graph theory COMBINATORIAL analysis

来源：评论

学校读者我要写书评

暂无评论

复合事件相似性检测技术

复合事件相似性检测技术

引用

第29届中国数据库学术会议

作者： Wang Ning 王宁 Gu Yu 谷峪 Li Fangfang 李芳芳 Yu Ge 于戈 Institute of Computer Software and Theory of Information Science and Engineering Institute Northeas 东北大学信息科学与工程学院软件与理论研究所沈阳 110819 Key Laboratory of Medical Image Computing(Northeastern University) Ministry of Education Shenyang 医学影像计算教育部重点实验室(东北大学) 沈阳 110819

复杂事件处理一般都是从大量的简单事件进行查找，整理出有价值的复合事件，在事件的查找过程中，强调的是事件的精确性匹配。本文提出了复合事件相似性查询，并且针对其定义，给出了两种剪枝策略。根据复合事件的特点，减少数据处理数... 详细信息

复杂事件处理一般都是从大量的简单事件进行查找，整理出有价值的复合事件，在事件的查找过程中，强调的是事件的精确性匹配。本文提出了复合事件相似性查询，并且针对其定义，给出了两种剪枝策略。根据复合事件的特点，减少数据处理数量，降低I/O代价。最后，利用实验对提出的两种剪枝策略进行对比分析。

关键词：信息处理复杂事件相似性检测射频识别技术

来源：评论

学校读者我要写书评

暂无评论

quantum Interactive Proofs with Short Messages

引用

theory of computing 2011年 7卷 101-117页

作者： Beigi, Salman Shor, Peter Watrous, John Tehran Iran Department of Mathematics Massachusetts Institute of Technology Cambridge Massachusetts United States Institute for Quantum Computing and School of Computer Science University of Waterloo Waterloo Ontario Canada

This paper considers three variants of quantum interactive proof systems in which short (meaning logarithmic-length) messages are exchanged between the prover and verifier. The first variant is one in which the verifier sends a short message to the prover, and the prover responds with an ordinary, or polynomial-length, message;the second variant is one in which any number of messages can be exchanged, but where the combined length of all the messages is logarithmic;and the third variant is one in which the verifier sends polynomially many random bits to the prover, who responds with a short quantum message. We prove that in all of these cases the short messages can be eliminated without changing the power of the model, so the first variant has the expressive power of QMA and the second and third variants have the expressive power of BQP. These facts are proved through the use of quantum state tomography, along with the finite quantum de Finetti theorem for the first variant. © 2011, University of Chicago, Department of computer science. All rights reserved.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

Ethnocentrism Maintains Cooperation, but Keeping One’s Children Close Fuels It 33

Ethnocentrism Maintains Cooperation, but Keeping One’s Chil...

引用

33rd Annual Meeting of the Cognitive science Society: Expanding the Space of Cognitive science, CogSci 2011

作者： Kaznatcheev, Artem Shultz, Thomas R. Department of Combinatorics & Optimization Institute for Quantum Computing University of Waterloo 200 University Avenue West WaterlooONN2L 3G1 Canada Department of Psychology School of Computer Science McGill University 1205 Penfield Avenue MontrealQCH3A 1B1 Canada

ISBN: (纸本)9780976831877

Ethnocentrism, commonly thought to rely on complex social cognition, can arise through biological evolution in populations with minimal cognitive abilities. In fact, ethnocentrism is considered to be one of the simplest mechanisms for establishing cooperation in the competitive environment of natural selection. Here we study a recent agent-based model. Through our simulations and analysis, we establish that the mechanism responsible for the emergence of cooperation is children residing close to their parents. Our results suggest that group tags maintain cooperation, but do not create it. We formalize this observation as the dual direct hypothesis: ethnocentric agents dominate humanitarian agents by exploiting the unconditional cooperation of humanitarians of different tags to maintain the number of ethnocentric agents after world saturation. We affirm previous observations on the importance of world saturation, finding its drastic effect on dynamics in both spatial tag-based and tag-less models. © CogSci 2011.

关键词： Autonomous agents

来源：评论

学校读者我要写书评

暂无评论

Addendum Entropy and information causality in general probabilistic theories

引用

New Journal of Physics 2012年 14卷

作者： Barnum, Howard Barrett, Jonathan Clark, Lisa Orloff Leifer, Matthew Spekkens, Robert Stepanik, Nicholas Wilce, Alex Wilke, Robin Department of Physics and Astronomy University of New Mexico 1919 Lomas Boulevard NE MSC07 4220 AlbuquerqueNM87131-0001 United States Department of Computer Science University of Oxford Parks Road OxfordOX1 3QD United Kingdom Department of Mathematics and Statistics University of Otago PO Box 56 Dunedin9054 New Zealand Perimeter Institute for Theoretical Physics 31 Caroline St. N WaterlooONN2L 2Y5 Canada Institute for Quantum Computing University of Waterloo 200 University Avenue W WaterlooONN2L 3G1 Canada Department of Mathematics University of Connecticut 198 Auditorium Road Unit 3009 StorrsCT06269 United States Department of Mathematical Sciences Susquehanna University SelinsgrovePA17870 United States Department of Mathematics and Statistics University of Vermont BurlingtonVT05405 United States

In this addendum to our paper (2010 New J. Phys. 12 033024), we point out that an elementary consequence of the strong subadditivity inequality allows us to strengthen one of the main conclusions of that paper. ©...

关键词：

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithms for QMA-Complete Problems

Approximation Algorithms for QMA-Complete Problems

引用

Annual IEEE Conference on Computational Complexity

作者： Sevag Gharibian Julia Kempe David R. Cheriton School of Computer Science and Institute of Quantum Computing University of Waterloo Waterloo Canada Blavatnik School of Computer Science Tel-Aviv University Tel-Aviv Israel CNRS and LIAFA Université Paris 7 Paris France

Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.

关键词： Approximation methods Approximation algorithms Polynomials Optimized production technology NP-hard problem Physics Minimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：