TY - JOUR
T1 - Complexity of the XY antiferromagnet at fixed magnetization
JF - Quantum Information and Computation
Y1 - 2016
A1 - Andrew M. Childs
A1 - David Gosset
A1 - Zak Webb
AB - 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.
VL - 16
U4 - 1-18
UR - http://arxiv.org/abs/1503.07083v1
CP - 1-2
ER -
TY - JOUR
T1 - Momentum switches
JF - Quantum Information and Computation
Y1 - 2015
A1 - Andrew M. Childs
A1 - David Gosset
A1 - Daniel Nagaj
A1 - Mouktik Raha
A1 - Zak Webb
AB - 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.
VL - 15
U4 - 601-621
UR - http://arxiv.org/abs/1406.4510v1
CP - 7-8
J1 - Quantum Information and Computation 15
ER -
TY - JOUR
T1 - The Bose-Hubbard model is QMA-complete
JF - Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)
Y1 - 2014
A1 - Andrew M. Childs
A1 - David Gosset
A1 - Zak Webb
AB - 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.
VL - 8572
U4 - 308-319
UR - http://arxiv.org/abs/1311.3297v1
J1 - Proceedings of the 41st International Colloquium on Automata
U5 - 10.1007/978-3-662-43948-7_26
ER -
TY - JOUR
T1 - Universal computation by multi-particle quantum walk
JF - Science
Y1 - 2013
A1 - Andrew M. Childs
A1 - David Gosset
A1 - Zak Webb
AB - 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.
VL - 339
U4 - 791 - 794
UR - http://arxiv.org/abs/1205.3782v2
CP - 6121
J1 - Science
U5 - 10.1126/science.1229957
ER -
TY - JOUR
T1 - Levinson's theorem for graphs II
JF - Journal of Mathematical Physics
Y1 - 2012
A1 - Andrew M. Childs
A1 - David Gosset
AB - 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.
VL - 53
U4 - 102207
UR - http://arxiv.org/abs/1203.6557v2
CP - 10
J1 - J. Math. Phys.
U5 - 10.1063/1.4757665
ER -
TY - JOUR
T1 - QMA-complete problems for stoquastic Hamiltonians and Markov matrices
JF - Physical Review A
Y1 - 2010
A1 - Stephen P. Jordan
A1 - David Gosset
A1 - Peter J. Love
AB - 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.
VL - 81
UR - http://arxiv.org/abs/0905.4755v2
CP - 3
J1 - Phys. Rev. A
U5 - 10.1103/PhysRevA.81.032331
ER -