%0 Journal Article
%J Quantum Information and Computation
%D 2016
%T Complexity of the XY antiferromagnet at fixed magnetization
%A Andrew M. Childs
%A David Gosset
%A Zak Webb
%X We prove that approximating the ground energy of the antiferromagnetic XY model on a simple graph at fixed magnetization (given as part of the instance specification) is QMA-complete. To show this, we strengthen a previous result by establishing QMA-completeness for approximating the ground energy of the Bose-Hubbard model on simple graphs. Using a connection between the XY and Bose-Hubbard models that we exploited in previous work, this establishes QMA-completeness of the XY model.
%B Quantum Information and Computation
%V 16
%P 1-18
%8 2016/01/01
%G eng
%U http://arxiv.org/abs/1503.07083v1
%N 1-2
%0 Journal Article
%J Quantum Information and Computation
%D 2015
%T Momentum switches
%A Andrew M. Childs
%A David Gosset
%A Daniel Nagaj
%A Mouktik Raha
%A Zak Webb
%X Certain continuous-time quantum walks can be viewed as scattering processes. These processes can perform quantum computations, but it is challenging to design graphs with desired scattering behavior. In this paper, we study and construct momentum switches, graphs that route particles depending on their momenta. We also give an example where there is no exact momentum switch, although we construct an arbitrarily good approximation.
%B Quantum Information and Computation
%V 15
%P 601-621
%8 2015/05/01
%G eng
%U http://arxiv.org/abs/1406.4510v1
%N 7-8
%! Quantum Information and Computation 15
%0 Journal Article
%J Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)
%D 2014
%T The Bose-Hubbard model is QMA-complete
%A Andrew M. Childs
%A David Gosset
%A Zak Webb
%X The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients.
%B Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)
%V 8572
%P 308-319
%8 2014/07/08
%G eng
%U http://arxiv.org/abs/1311.3297v1
%! Proceedings of the 41st International Colloquium on Automata
%R 10.1007/978-3-662-43948-7_26
%0 Journal Article
%J Science
%D 2013
%T Universal computation by multi-particle quantum walk
%A Andrew M. Childs
%A David Gosset
%A Zak Webb
%X A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. Here we consider a generalization of quantum walk to systems with more than one walker. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. Multi-particle quantum walk includes a broad class of interacting many-body systems such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions. We show that multi-particle quantum walk is capable of universal quantum computation. Since it is also possible to efficiently simulate a multi-particle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation. In principle our construction could be used as an architecture for building a scalable quantum computer with no need for time-dependent control.
%B Science
%V 339
%P 791 - 794
%8 2013/02/14
%G eng
%U http://arxiv.org/abs/1205.3782v2
%N 6121
%! Science
%R 10.1126/science.1229957
%0 Journal Article
%J Journal of Mathematical Physics
%D 2012
%T Levinson's theorem for graphs II
%A Andrew M. Childs
%A David Gosset
%X We prove Levinson's theorem for scattering on an (m+n)-vertex graph with n semi-infinite paths each attached to a different vertex, generalizing a previous result for the case n=1. This theorem counts the number of bound states in terms of the winding of the determinant of the S-matrix. We also provide a proof that the bound states and incoming scattering states of the Hamiltonian together form a complete basis for the Hilbert space, generalizing another result for the case n=1.
%B Journal of Mathematical Physics
%V 53
%P 102207
%8 2012/11/21
%G eng
%U http://arxiv.org/abs/1203.6557v2
%N 10
%! J. Math. Phys.
%R 10.1063/1.4757665
%0 Journal Article
%J Physical Review A
%D 2010
%T QMA-complete problems for stoquastic Hamiltonians and Markov matrices
%A Stephen P. Jordan
%A David Gosset
%A Peter J. Love
%X We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration free Hamiltonian is universal. Our results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems.
%B Physical Review A
%V 81
%8 2010/3/29
%G eng
%U http://arxiv.org/abs/0905.4755v2
%N 3
%! Phys. Rev. A
%R 10.1103/PhysRevA.81.032331