



01051nas a2200145   4500008004100000245007400041210006900115260001400184490000700198520060100205100002400806700001800830700002000848856003700868       2010                        eng d00aQMA-complete problems for stoquastic Hamiltonians and Markov matrices0 aQMAcomplete problems for stoquastic Hamiltonians and Markov matr  c2010/3/290 v813 a  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.
1 aJordan, Stephen, P.1 aGosset, David1 aLove, Peter, J.  uhttp://arxiv.org/abs/0905.4755v201766nas a2200181   4500008004100000245008100041210006900122260001500191300001800206490000800224520121000232100001701442700002401459700002001483700002001503700002401523856003701547       2008                        eng d00aPolynomial-time quantum algorithm for the simulation of chemical  dynamics
0 aPolynomialtime quantum algorithm for the simulation of chemical   c2008/11/24  a18681 - 186860 v1053 a  The computational cost of exact methods for quantum simulation using
classical computers grows exponentially with system size. As a consequence,
these techniques can only be applied to small systems. By contrast, we
demonstrate that quantum computers could exactly simulate chemical reactions in
polynomial time. Our algorithm uses the split-operator approach and explicitly
simulates all electron-nuclear and inter-electronic interactions in quadratic
time. Surprisingly, this treatment is not only more accurate than the
Born-Oppenheimer approximation, but faster and more efficient as well, for all
reactions with more than about four atoms. This is the case even though the
entire electronic wavefunction is propagated on a grid with appropriately short
timesteps. Although the preparation and measurement of arbitrary states on a
quantum computer is inefficient, here we demonstrate how to prepare states of
chemical interest efficiently. We also show how to efficiently obtain
chemically relevant observables, such as state-to-state transition
probabilities and thermal reaction rates. Quantum computers using these
techniques could outperform current classical computers with one hundred
qubits.
1 aKassal, Ivan1 aJordan, Stephen, P.1 aLove, Peter, J.1 aMohseni, Masoud1 aAspuru-Guzik, Alán  uhttp://arxiv.org/abs/0801.2986v3