00953nas a2200157 4500008004100000245006400041210006400105260001500169300000900184490000700193520050200200100002300702700001800725700001400743856003800757 2016 eng d00aComplexity of the XY antiferromagnet at fixed magnetization0 aComplexity of the XY antiferromagnet at fixed magnetization c2016/01/01 a1-180 v163 a 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.
1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1503.07083v100877nas a2200181 4500008004100000245002200041210002200063260001500085300001200100490000700112520044800119100002300567700001800590700001800608700001800626700001400644856003700658 2015 eng d00aMomentum switches0 aMomentum switches c2015/05/01 a601-6210 v153 a 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.
1 aChilds, Andrew, M.1 aGosset, David1 aNagaj, Daniel1 aRaha, Mouktik1 aWebb, Zak uhttp://arxiv.org/abs/1406.4510v101367nas a2200157 4500008004100000245004300041210003700084260001500121300001200136490000900148520096000157100002301117700001801140700001401158856003701172 2014 eng d00aThe Bose-Hubbard model is QMA-complete0 aBoseHubbard model is QMAcomplete c2014/07/08 a308-3190 v85723 a 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.
1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1311.3297v101608nas a2200157 4500008004100000245005700041210005600098260001500154300001400169490000800183520116700191100002301358700001801381700001401399856003701413 2013 eng d00aUniversal computation by multi-particle quantum walk0 aUniversal computation by multiparticle quantum walk c2013/02/14 a791 - 7940 v3393 a 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.
1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1205.3782v2