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

quantum algorithms for algebraic problems

Reviews of Modern Physics 2010年第1期82卷 1-1页

作者： Andrew M. Childs Wim van Dam []Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1

quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.

关键词： quantum computers ALGORITHMS INTEGER programming quantum theory ALGEBRA

来源：评论

学校读者我要写书评

暂无评论

Robustness of ethnocentrism to changes in interpersonal interactions

Robustness of ethnocentrism to changes in interpersonal inte...

引用

2010 AAAI Fall Symposium

作者： Kaznatcheev, Artem School of Computer Science Department of Psychology McGill University 3600 University Street Montreal QC H3A 2T8 Canada Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Avenue West Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9781577354857

We use the methods of evolutionary game theory and computational modelling to examine the evolution of ethnocentrism. We show that ethnocentrism evolves in a spatially structured population not only under prisoner's dilemma interactions, but also hawk-dove, assurance, harmony, and leader games. In the case of harmony, ethnocentrism evolves even when defection is irrational. This suggests that the pressure of competing for a common resource (in our model: free space) can produce irrational hostility between groups. The minimal cognitive assumptions in our model also suggest that the ethnocentrism observed in humans and elsewhere in nature has an evolutionary basis that is robust over changes in interaction types. Copyright © 2010, Association for the Advancement of Artificial Intelligence. All rights reserved.

关键词： Game theory

来源：评论

学校读者我要写书评

暂无评论

Interacting Boson Problems Can Be QMA Hard

引用

Physical Review Letters 2010年第4期104卷 040501-040501页

作者： Tzu-Chieh Wei Michele Mosca Ashwin Nayak Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada Department of Physics and Astronomy University of British Columbia Vancouver British Columbia Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada Perimeter Institute for Theoretical Physics Waterloo Ontario Canada

computing the ground-state energy of interacting electron problems has recently been shown to be hard for quantum Merlin Arthur (QMA), a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we demonstrate that the complexity of interacting boson problems is also QMA hard. Moreover, the bosonic version of N-representability problem is QMA complete. Consequently, these problems are unlikely to have efficient quantum algorithms.

关键词： Ground state

来源：评论

学校读者我要写书评

暂无评论

Tensor product representation of a topological ordered phase: Necessary symmetry conditions

引用

Physical Review B 2010年第16期82卷 165119-165119页

作者： Xie Chen Bei Zeng Zheng-Cheng Gu Isaac L. Chuang Xiao-Gang Wen Department of Physics Massachusetts Institute of Technology Cambridge Massachusetts 02139 USA Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada Department of Mathematics and Statistics University of Guelph Guelph Ontario Canada Kavli Institute for Theoretical Physics University of California Santa Barbara California 93106 USA

The tensor product representation of quantum states leads to a promising variational approach to study quantum phase and quantum phase transitions, especially topological ordered phases which are impossible to handle with conventional methods due to their long-range entanglement. However, an important issue arises when we use tensor product states (TPSs) as variational states to find the ground state of a Hamiltonian: can arbitrary variations in the tensors that represent ground state of a Hamiltonian be induced by local perturbations to the Hamiltonian? Starting from a tensor product state which is the exact ground state of a Hamiltonian with Z2 topological order, we show that, surprisingly, not all variations in the tensors correspond to the variation in the ground state caused by local perturbations of the Hamiltonian. Even in the absence of any symmetry requirement of the perturbed Hamiltonian, one necessary condition for the variations in the tensors to be physical is that they respect certain Z2 symmetry. We support this claim by calculating explicitly the change in topological entanglement entropy with different variations in the tensors. This finding will provide important guidance to numerical variational study of topological phase and phase transitions. It is also a crucial step in using TPS to study universal properties of a quantum phase and its topological order.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Entanglement and area law with a fractal boundary in a topologically ordered phase

引用

Physical Review A 2010年第1期81卷 010102(R)-010102(R)页

作者： Alioscia Hamma Daniel A. Lidar Simone Severini Perimeter Institute for Theoretical Physics 31 Caroline St. N N2L 2Y5 Waterloo Ontario Canada Departments of Chemistry Electrical Engineering and Physics and Center for Quantum Information Science and Technology University of Southern California Los Angeles California 90089 USA Institute for Quantum Computing and Department of Combinatorics & Optimization University of Waterloo 200 University Ave. W N2L 3G1 Waterloo Ontario Canada

quantum systems with short-range interactions are known to respect an area law for the entanglement entropy: The von Neumann entropy S associated to a bipartition scales with the boundary p between the two parts. Here we study the case in which the boundary is a fractal. We consider the topologically ordered phase of the toric code with a magnetic field. When the field vanishes it is possible to analytically compute the entanglement entropy for both regular and fractal bipartitions (A,B) of the system and this yields an upper bound for the entire topological phase. When the A−B boundary is regular we have S/p=1 for large p. When the boundary is a fractal of the Hausdorff dimension D, we show that the entanglement between the two parts scales as S/p=γ⩽1/D, and γ depends on the fractal considered.

关键词： Entropy

来源：评论

学校读者我要写书评

暂无评论

quantum State Reduction for Universal Measurement Based Computation

引用

Physical Review Letters 2010年第2期105卷 020502-020502页

作者： Xie Chen Runyao Duan Zhengfeng Ji Bei Zeng 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 NSW Australia Department of Computer Science and Technology Tsinghua National Laboratory for Information Science and Technology Tsinghua University Beijing China 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 University of Waterloo Waterloo Ontario Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada

Measurement based quantum computation, which requires only single particle measurements on a universal resource state to achieve the full power of quantum computing, has been recognized as one of the most promising models for the physical realization of quantum computers. Despite considerable progress in the past decade, it remains a great challenge to search for new universal resource states with naturally occurring Hamiltonians and to better understand the entanglement structure of these kinds of states. Here we show that most of the resource states currently known can be reduced to the cluster state, the first known universal resource state, via adaptive local measurements at a constant cost. This new quantum state reduction scheme provides simpler proofs of universality of resource states and opens up plenty of space to the search of new resource states.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

quantum-capacity-approaching codes for the detected-jump channel

引用

Physical Review A 2010年第6期82卷 062324-062324页

作者： Markus Grassl Zhengfeng Ji Zhaohui Wei Bei Zeng Centre for Quantum Technologies National University of Singapore Singapore 117543 Singapore Perimeter Institute for Theoretical Physics Waterloo Ontario N2L 2Y5 Canada State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing 100190 China Department of Mathematics and Statistics University of Guelph Guelph Ontario N1G 2W1 Canada Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada

The quantum-channel capacity gives the ultimate limit for the rate at which quantum data can be reliably transmitted through a noisy quantum channel. Degradable quantum channels are among the few channels whose quantum capacities are known. Given the quantum capacity of a degradable channel, it remains challenging to find a practical coding scheme which approaches capacity. Here we discuss code designs for the detected-jump channel, a degradable channel with practical relevance describing the physics of spontaneous decay of atoms with detected photon emission. We show that this channel can be used to simulate a binary classical channel with both erasures and bit flips. The capacity of the simulated classical channel gives a lower bound on the quantum capacity of the detected-jump channel. When the jump probability is small, it almost equals the quantum capacity. Hence using a classical capacity-approaching code for the simulated classical channel yields a quantum code which approaches the quantum capacity of the detected-jump channel.

关键词： quantum capacity approaching jump spontaneous decay quanta labeling scheme Codes quantum dense coding ultimate limits

来源：评论

学校读者我要写书评

暂无评论

Multi-error-correcting amplitude damping codes

Multi-error-correcting amplitude damping codes

引用

IEEE International Symposium on Information Theory

作者： Runyao Duan Markus Grassl Zhengfeng Ji Bei Zeng State Key Laboratory of Intelligent Technology and Systems Tsinghua National Laboratory for Information Science and Technology Department of Computer Science and Technology Tsinghua University Beijing China Centre for Quantum Computation and Intelligent Systems (QCIS) Faculty of Engineering and Information Technology University of Technology Sydney NSW Australia Centre for Quantum Technologies National University of Singapore Singapore Perimeter Institute of Theoretical Physics Waterloo ONT Canada State Key Laboratory of Computer Science Institute of Software Chinese Academy and Sciences Beijing China Institute for Quantum Computing and the Department of Combinatorics and Optimization University of Waterloo Waterloo ONT Canada

ISBN: (纸本)9781424478903

We construct new families of multi-error-correcting quantum codes for the amplitude damping channel. Our key observation is that, with proper encoding, two uses of the amplitude damping channel simulate a quantum erasure channel. This allows us to use concatenated codes with quantum erasure-correcting codes as outer codes for correcting multiple amplitude damping errors. Our new codes are degenerate stabilizer codes and have parameters which are better than the amplitude damping codes obtained by any previously known construction.

关键词： Damping quantum mechanics quantum computing Error correction codes Noise level Laboratories Phase noise Physics computing Intelligent systems Computer science

来源：评论

学校读者我要写书评

暂无评论

A note on observables for counting trails and paths in graphs

引用

Journal of Mathematical Modelling and Algorithms 2009年第3期8卷 335-342页

作者： Markopoulou, Fotini Severini, Simone Perimeter Institute for Theoretical Physics Waterloo N2L 2Y5 ON Canada Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo N2L 3G1 ON 200 University Avenue West Canada

We point out that the total number of trails and the total number of paths of given length, between two vertices of a simple undirected graph, are obtained as expectation values of specifically engineered quantum mechanical observables. Such observables are contextual with some background independent theories of gravity and emergent geometry. Thus, we point out yet another situation in which the mathematical formalism of a physical theory has some computational aspects involving intractable problems. © Springer Science + Business Media B.V. 2009.

关键词： Cycles Enumeration Graphity models Grassman variables Observables Paths

来源：评论

学校读者我要写书评

暂无评论

Universal Computation by quantum Walk

引用

Physical Review Letters 2009年第18期102卷 180501-180501页

作者： Andrew M. Childs Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo 200 University Avenue West Waterloo Ontario Canada N2L 3G1

In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：