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 -
TY - JOUR
T1 - Polynomial-time quantum algorithm for the simulation of chemical dynamics
JF - Proceedings of the National Academy of Sciences
Y1 - 2008
A1 - Ivan Kassal
A1 - Stephen P. Jordan
A1 - Peter J. Love
A1 - Masoud Mohseni
A1 - Alán Aspuru-Guzik
AB - 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.
VL - 105
U4 - 18681 - 18686
UR - http://arxiv.org/abs/0801.2986v3
CP - 48
J1 - Proceedings of the National Academy of Sciences
U5 - 10.1073/pnas.0808245105
ER -