Fetching the paper…
Reading the bibliography…
We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete.
Two theorems on random polynomial time
L. Adleman · 1978
Earlier work this paper cites.
On the computational complexity of ising spin glass models
F. Barahona · 1982
Earlier work this paper cites.
Trading group theory for randomness
L. Babai · 1985
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh Vazirani · 1997
Earlier work this paper cites.
Introduction to the Theory of Computation
Michael Sipser · 1997
Earlier work this paper cites.
Succinct quantum proofs for properties of finite groups
J. Watrous · 2000
Earlier work this paper cites.
Robustness of adiabatic quantum computation
Andrew M. Childs, Edward Farhi, and John Preskill · 2001
Earlier work this paper cites.
Quantum NP - A Survey
Dorit Aharonov and Tomer Naveh · 2002
Earlier work this paper cites.
Classical and Quantum Computation
A. Yu Kitaev, A. H. Shen, and M. N. Vyalyi · 2002
Earlier work this paper cites.
3-local Hamiltonian is QMA-complete
Julia Kempe and Oded Regev · 2003
Cited alongside, same era.
Both Toffoli and Controlled-NOT need little help to do universal quantum computation
Yaoyun Shi · 2003
Cited alongside, same era.
The complexity of the local Hamiltonian problem
Julia Kempe, Alexei Kitaev, and Oded Regev · 2004
Cited alongside, same era.
Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
Cited alongside, same era.
Efficient algorithm for a quantum analogue of 2-sat
Sergey Bravyi · 2006
Cited alongside, same era.
Merlin-Arthur games and stoquastic complexity
Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal · 2006
Cited alongside, same era.
The local consistency problem for stoquastic and 1-D quantum systems
Yi-Kai Liu · 2007
Later among the works it cites.
Realizable Hamiltonians for universal adiabatic quantum computers
Jacob D. Biamonte and Peter J. Love · 2008
Later among the works it cites.
The complexity of stoquastic local Hamiltonian problems
Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal · 2008
Later among the works it cites.
Quantum computation beyond the circuit model
Stephen P. Jordan · 2008
Later among the works it cites.
The complexity of quantum spin systems in a two-dimensional square lattice
Roberto Oliveira and Barbara M. Terhal · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Dominik Janzing and Pawel Wocjan · 2006
Cited alongside, same era.
Adiabatic quantum computation is equivalent to standard quantum computation
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev · 2007
Cited alongside, same era.
Quantum computational complexity of the N-representability problem: QMA complete
Y. Liu, M. Christandl, and F. Verstraete · 2007
Cited alongside, same era.
Computational Complexity: A Modern Approach
S. Arora and B. Barak · 2009
Closest in time.
Complexity of stoquastic frustration-free Hamiltonians
Sergey Bravyi and Barbara Terhal · 2009
Closest in time.
Daniel Nagaj, Pawel Wocjan, and Yong Zhang · 2009
Closest in time.
Computational complexity of interacting electrons and fundamental limitations of density functional theory
Norbert Schuch and Frank Verstraete · 2009
Closest in time.