@article {1234,
title = {Complexity of the XY antiferromagnet at fixed magnetization},
journal = {Quantum Information and Computation},
volume = {16},
year = {2016},
month = {2016/01/01},
pages = {1-18},
abstract = { 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.
},
url = {http://arxiv.org/abs/1503.07083v1},
author = {Andrew M. Childs and David Gosset and Zak Webb}
}
@article {1259,
title = {Momentum switches},
journal = {Quantum Information and Computation},
volume = {15},
year = {2015},
month = {2015/05/01},
pages = {601-621},
abstract = { 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.
},
url = {http://arxiv.org/abs/1406.4510v1},
author = {Andrew M. Childs and David Gosset and Daniel Nagaj and Mouktik Raha and Zak Webb}
}
@article {1232,
title = {The Bose-Hubbard model is QMA-complete},
journal = {Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)},
volume = {8572},
year = {2014},
month = {2014/07/08},
pages = {308-319},
abstract = { 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.
},
doi = {10.1007/978-3-662-43948-7_26},
url = {http://arxiv.org/abs/1311.3297v1},
author = {Andrew M. Childs and David Gosset and Zak Webb}
}
@article {1221,
title = {Universal computation by multi-particle quantum walk},
journal = {Science},
volume = {339},
year = {2013},
month = {2013/02/14},
pages = {791 - 794},
abstract = { 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.
},
doi = {10.1126/science.1229957},
url = {http://arxiv.org/abs/1205.3782v2},
author = {Andrew M. Childs and David Gosset and Zak Webb}
}