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

On the Limitations of Graph Invariants Inspired by quantum Walks

Electronic Notes in Discrete Mathematics 2011年 38卷 795-801页

作者： Smith, Jamie Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Waterloo N2L 3G1 Canada

We consider two graph invariants inspired by quantum walks-one in continuous time [John King Gamble, Mark Friesen, Dong Zhou, Robert Joynt, and S. N. Coppersmith. Two-particle quantum walks applied to the graph isomorphism problem. Phys. Rev. A, (81), May 2010] and one in discrete time [David Emms, Edwin R Hancock, Simone Severini, and Richard C Wilson. A matrix representation of graphs and its spectrum as a graph invariant. arXiv:quant-ph/0505026v2, May 2005, Chris Godsil and Krystal Guo. quantum walks on regular graphs and eigenvalues. arXiv:***/1011.5460v1, Nov 2010]. We will associate a matrix algebra called a cellular algebra with every graph. We show that, if the cellular algebras of two graphs have a similar structure, then they are not distinguished by either of the proposed invariants. This has implications for the strength of these proposed invariants in relation to other known invariants, and gives rise to several interesting open problems. © 2011 Elsevier B.V.

关键词： Cellular algebras Graph isomorphism problem quantum walks

来源：评论

学校读者我要写书评

暂无评论

quantum property testing for bounded-degree graphs 1

引用

Lecture Notes in Computer Science

作者： Ambainis, Andris Childs, Andrew M. Liu, Yi-Kai Faculty of Computing University of Latvia Latvia Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Department of Computer Science University of California Berkeley CA United States

ISBN: (数字)9783642229350

ISBN: (纸本)9783642229343

We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time Õ(N1/3), beating the Ω(√N) classical lower bound. For testing expansion, we also prove an Ω(N1/4) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure. © 2011 Springer-Verlag.

关键词： Testing

来源：评论

学校读者我要写书评

暂无评论

Authentication of quantum messages

Authentication of quantum messages

引用

Applications of Lasers for Sensing and Free Space Communications, LSC 2011

作者： Hayden, Patrick Leung, Debbie Mayers, Dominic School of Computer Science McGill University Montreal QC Canada Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Waterloo ON Canada Institute for Quantum Information Caltech Pasadena CA United States

ISBN: (纸本)9781557529145

Message authentication is a cryptographic task that allows the receiver to reject a message that is forged or has been tampered with. A protocol to authenticate quantum messages was proposed by Barnum, Crépeau, Gottesman, Tapp, and Smith [1] and stand-alone security was proved. Here, we are concerned with universal composable security (which requires a protocol to be essentially indistinguishable from the ideal functionality and ensures overall security when the protocol is part of any larger scheme). We show that the protocol in [1] is universal composably secure, and that most of the required key can be reused with universal composable security. © 2011 Optical Society of America.

关键词： Authentication

来源：评论

学校读者我要写书评

暂无评论

Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs

引用

Physical Review A 2012年第5期86卷 052334-052334页

作者： Edward Farhi David Gosset Itay Hen A. W. Sandvik Peter Shor A. P. Young Francesco Zamponi Center for Theoretical Physics Massachusetts Institute of Technology 77 Massachusetts Avenue 6-304 Cambridge Massachusetts 02139 USA Department of Combinatorics & Optimization and Institute for Quantum Computing University of Waterloo 200 University Avenue West Waterloo Ontario Canada N2L 3G1 Department of Physics University of California Santa Cruz California 95064 USA Department of Physics Boston University Boston Massachusetts 02215 USA Department of Mathematics Center for Theoretical Physics and CSAIL Massachusetts Institute of Technology Cambridge Massachusetts 02139 USA Laboratoire de Physique Théorique UMR 8549 CNRS and Ecole Normale Supérieure 24 Rue Lhomond FR-75231 Paris Cedex 05 France

In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular max-cut. The cost functions associated with these two clause-based optimization problems are similar as they are both defined on 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular max-cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons.

关键词： Cost functions Random quanta Adiabatic

来源：评论

学校读者我要写书评

暂无评论

Parallelizing the Weil and Tate pairings

Parallelizing the Weil and Tate pairings

引用

13th IMA International Conference on Cryptography and Coding, IMACC 2011

作者： Aranha, Diego F. Knapp, Edward Menezes, Alfred Rodríguez-Henríquez, Francisco Institute of Computing University of Campinas Brazil Department of Combinatorics and Optimization University of Waterloo Canada CINVESTAV-IPN Computer Science Department Mexico

ISBN: (纸本)9783642255151

In the past year, the speed record for pairing implementations on desktop-class machines has been broken several times. The speed records for asymmetric pairings were set on a single processor. In this paper, we describe our parallel implementation of the optimal ate pairing over Barreto-Naehrig (BN) curves that is about 1.23 times faster using two cores of an Intel Core i5 or Core i7 machine, and 1.45 times faster using 4 cores of the Core i7 than the state-of-the-art implementation on a single core. We instantiate Hess's general Weil pairing construction and introduce a new optimal Weil pairing tailored for parallel execution. Our experimental results suggest that the new Weil pairing is 1.25 times faster than the optimal ate pairing on 8-core extensions of the aforementioned machines. Finally, we combine previous techniques for parallelizing the eta pairing on a supersingular elliptic curve with embedding degree 4, and achieve an estimated 1.24-fold speedup on an 8-core extension of an Intel Core i7 over the previous best technique. © 2011 Springer-Verlag.

关键词： Computers

来源：评论

学校读者我要写书评

暂无评论

No-go theorem for one-way quantum computing on naturally occurring two-level systems

引用

Physical Review A 2011年第5期83卷 050301(R)-050301(R)页

作者： Jianxin Chen Xie Chen Runyao Duan Zhengfeng Ji Bei Zeng Department of Computer Science and Technology Tsinghua National Laboratory for Information Science and Technology Tsinghua University Beijing China Department of Physics Massachusetts Institute of Technology Cambridge Massachusetts USA Centre for Quantum Computation and Intelligent Systems (QCIS) Faculty of Engineering and Information Technology University of Technology Sydney New South Wales Australia Perimeter Institute for Theoretical Physics Waterloo Ontario Canada State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada

The ground states of some many-body quantum systems can serve as resource states for the one-way quantum computing model, achieving the full power of quantum computation. Such resource states are found, for example, in spin-52 and spin-32 systems. It is, of course, desirable to have a natural resource state in a spin-12, that is, qubit system. Here, we give a negative answer to this question for frustration-free systems with two-body interactions. In fact, it is shown to be impossible for any genuinely entangled qubit state to be a nondegenerate ground state of any two-body frustration-free Hamiltonian. What is more, we also prove that every spin-12 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states. In other words, there cannot be any interesting entanglement features in the ground state of such a qubit Hamiltonian.

关键词： quantum computers quantum theory HAMILTONIAN operator HAMILTONIAN systems PHYSICS

来源：评论

学校读者我要写书评

暂无评论

Inverting a Permutation is as Hard as Unordered Search

引用

Theory of computing 2011年 7卷 19-25页

作者： Nayak, Ashwin Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics WaterlooON Canada

We show how an algorithm for the problem of inverting a permutation may be used to design one for the problem of unordered search (with a unique solution). Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent. The reduction we present helps us bypass the hybrid argument due to Bennett, Bernstein, Brassard, and Vazirani (1997) and the quantum adversary method due to Ambainis (2002) that were earlier used to derive lower bounds on the quantum query complexity of the problem of inverting permutations. It directly implies that the quantum query complexity of the problem is asymptotically the same as that for unordered search, namely in Θ(√n). © 2011, University of Chicago, department of Computer Science. All rights reserved.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Noise and microresonance of critical current in Josephson junction induced by Kondo trap states

引用

Physical Review B 2011年第23期84卷 235102-235102页

作者： M. H. Ansari F. K. Wilhelm Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo 200 University Ave. W Waterloo ON Canada N2L 3G1 Department of Physics and Astronomy and Institute for Quantum Computing University of Waterloo 200 University Ave. W Waterloo ON Canada N2L 3G1

We analyze the impact of trap states in the oxide layer of a superconducting tunnel junction on the fluctuation of the Josephson critical current, thus on coherence in superconducting qubits. Two mechanisms are usually considered: the current blockage due to repulsion at the occupied trap states and the noise from electrons hopping across a trap. We extend previous studies of noninteracting traps to the case where the traps have onsite electron repulsion inside one ballistic channel. The repulsion not only allows the appropriate temperature dependence of 1/f noise, but also the control of the coupling between the computational qubit and the spurious two-level systems inside the oxide dielectric. We use second-order perturbation theory, which allows to obtain analytical formulas for the interacting bound states and spectral weights, limited to small and intermediate repulsions. Remarkably, it still reproduces the main features of the model as identified from the numerical renormalization group. We present analytical formulations for the subgap bound state energies, the singlet-doublet phase boundary, and the spectral weights. We show that interactions can reverse the supercurrent across the trap. We finally work out the spectrum of junction resonators for qubits in the presence of onsite repulsive electrons and analyze its dependence on microscopic parameters that may be controlled by fabrication.

关键词： OXIDES ELECTRONS NOISE JOSEPHSON junctions JOSEPHSON effect SUPERCONDUCTORS

来源：评论

学校读者我要写书评

暂无评论

Perturbation theory in a pure-exchange nonequilibrium economy

引用

Physical Review E 2010年第3期81卷 036102-036102页

作者： Samuel E. Vázquez Simone Severini Institute for Quantum Computing and Department of Combinatorics & Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1

We develop a formalism to study linearized perturbations around the equilibria of a pure-exchange economy. With the use of mean-field theory techniques, we derive equations for the flow of products in an economy driven by heterogeneous preferences and probabilistic interaction between agents. We are able to show that if the economic agents have static preferences, which are also homogeneous in any of the steady states, the final wealth distribution is independent of the dynamics of the nonequilibrium theory. In particular, it is completely determined in terms of the initial conditions and it is independent of the probability, and the network of interaction between agents. We show that the main effect of the network is to determine the relaxation time via the usual eigenvalue gap as in random walks on graphs.

关键词： Mean field theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：