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

On the complexity of quantum partition functions

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bravyi, Sergey Chowdhury, Anirban Gosset, David Wocjan, Pawel IBM Quantum IBM T.J. Watson Research Center United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

The partition function and free energy of a quantum many-body system determine its physical properties in thermal equilibrium. Here we study the computational complexity of approximating these quantities for n-qubit local Hamiltonians. First, we report a classical algorithm with poly(n) runtime which approximates the free energy of a given 2-local Hamiltonian provided that it satisfies a certain denseness condition. Our algorithm combines the variational characterization of the free energy and convex relaxation methods. It contributes to a body of work on efficient approximation algorithms for dense instances of optimization problems which are hard in the general case, and can be viewed as simultaneously extending existing algorithms for (a) the ground energy of dense 2-local Hamiltonians, and (b) the free energy of dense classical Ising models. Secondly, we establish polynomial-time equivalence between the problem of approximating the free energy of local Hamiltonians and three other natural quantum approximate counting problems, including the problem of approximating the number of witness states accepted by a QMA verifier. These results suggest that simulation of quantum many-body systems in thermal equilibrium may precisely capture the complexity of a broad family of computational problems that has yet to be defined or characterized in terms of known complexity classes. Finally, we summarize state-of-the-art classical and quantum algorithms for approximating the free energy and show how to improve their runtime and memory footprint. Copyright © 2021, The Authors. All rights reserved.

关键词： Free energy

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

Beyond product state approximations for a quantum analogue of Max Cut

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Anshu, Anurag Gosset, David Morenz, Karen Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada Department of Chemistry University of Toronto Canada

We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem’s approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation). Copyright © 2020, The Authors. All rights reserved.

关键词： Approximation algorithms

On the circuit diameter of some combinatorial polytopes

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Kafer, Sean Pashkovich, Kanstantsin Sanità, Laura Department of Combinatorics and Optimization University of Waterloo Canada Simons Institute for the Theory of Computing UC Berkeley United States

The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, where the path uses potential edge directions of P i.e., all edge directions that can arise by translating some of the facets of P. In this paper, we study the circuit diameter of polytopes corresponding to classical combinatorial optimization problems, such as the Matching polytope, the Traveling Salesman polytope and the Fractional Stable Set polytope. Copyright © 2017, The Authors. All rights reserved.

关键词： Timing circuits

A survey on locking of bipartite correlations

学校读者我要写书评

暂无评论

Journal of Physics: Conference Series 2009年第1期143卷

作者： Leung, Debbie Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Waterloo ON N2L3G1 Canada

Unlocking of a correlation refers to the unexpected phenomenon that a small amount of communication increases that correlation (as a function of the state of the distributed system) by a disproportionate amount. Locking refers to the suppression of the correlation prior to the communication. The notion was subsequently extended to abrupt changes in a correlation due to the manipulation (in particular, the addition or removal) of a small subsystem. In this proceeding, we review the basic ideas and summarize the results known so far. © 2009 IOP Publishing Ltd.

关键词：

Universal Adiabatic quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction

学校读者我要写书评

暂无评论

Physical Review Letters 2015年第14期114卷 140501-140501页

作者： David Gosset Barbara M. Terhal Anna Vershynina Institute for Quantum Computing and Dept. of Combinatorics and Optimization University of Waterloo Ontario N2L 3G1 Canada JARA Institute for Quantum Information RWTH Aachen University 52056 Aachen North Rhine-Westphalia Germany

We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young’s lattice.

关键词： HAMILTONIAN systems FERROMAGNETIC materials DYNAMICAL systems MAGNETIC materials quantum theory

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

Sample-efficient learning of quantum many-body systems

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Anshu, Anurag Arunachalam, Srinivasan Kuwahara, Tomotaka Soleimanifar, Mehdi Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada IBM Research. RIKEN Japan Center for Theoretical Physics MIT

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems. Copyright © 2020, The Authors. All rights reserved.

关键词： quantum optics

Capacity of quantum Erasure Channel Assisted by Backwards Classical Communication

学校读者我要写书评

暂无评论

Physical Review Letters 2009年第24期103卷 240505-240505页

作者： Debbie Leung Joungkeun Lim Peter Shor Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo 200 University Avenue West Waterloo Ontario Canada N2L 3G1 Department of Mathematics Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge Massachusetts 02139 USA

We present a communication protocol for the erasure channel assisted by backward classical communication, which achieves a significantly better rate than the best prior result. In addition, we prove an upper bound for the capacity of the channel. The upper bound is smaller than the capacity of the erasure channel when it is assisted by two-way classical communication. Thus, we prove the separation between quantum capacities assisted by backward classical communication and two-way classical communication.

关键词：