Fetching the paper…
Reading the bibliography…
We prove that estimating the ground state energy of a translationally-invariant, nearest-neighbour Hamiltonian on a 1D spin chain is QMAEXP-complete, even for systems of low local dimension (roughly 40).
“Logical reversibility of computation”
Charles. Bennett · 1973
Earlier work this paper cites.
“Algebraic connectivity of graphs”
Miroslav Fiedler · 1973
Earlier work this paper cites.
“Introduction to automata theory, languages, and computation”
John E. and Jeffrey D · 1979
Earlier work this paper cites.
“Quantum mechanical computers”
Richard. Feynman · 1986
Earlier work this paper cites.
“Quantum complexity theory”
Ethan Bernstein and Umesh Vazirani · 1997
Earlier work this paper cites.
“Algebraic Graph Theory” 207
Chris Godsil and Gordon Royle · 2001
Earlier work this paper cites.
“Classical and quantum computing”
Alexei. Kitaev, Alexander Shen and Mikhail. Vyalyi · 2002
Earlier work this paper cites.
“Classical and quantum computing” 47
Alexei Yu., Alexander Shen and Mikhail N · 2002
Earlier work this paper cites.
“The complexity of the local Hamiltonian problem”
Julia Kempe, Alexei. Kitaev and Oded Regev · 2006
Earlier work this paper cites.
“An area law for one-dimensional quantum systems”
Matthew. Hastings · 2007
Earlier work this paper cites.
“The complexity of quantum systems on a one-dimensional chain”, 2007
Sandy Irani · 2007
Earlier work this paper cites.
“The complexity of quantum spin systems on a two-dimensional square lattice”
Roberto. Oliveira and Barbara. Terhal · 2008
Earlier work this paper cites.
“Hamiltonian quantum cellular automata in one dimension”
Daniel Nagaj and Pawel Wocjan · 2008
Earlier work this paper cites.
“Reversible computing and cellular automata—A survey”
Kenichi Morita · 2008
Earlier work this paper cites.
“The power of quantum systems on a line”
Dorit Aharonov, Daniel Gottesman, Sandy Irani and Julia Kempe · 2009
Earlier work this paper cites.
““When nobody else dreamed of these things” – Axel Thue und die Termersetzung”
Wolfgang Thomas · 2010
Cited alongside, same era.
“Quantum computation and quantum information”
Michael. Nielsen and Isaac. Chuang · 2010
Cited alongside, same era.
“No-go theorem for one-way quantum computing on naturally occurring two-level systems”
Jianxin Chen, Xie Chen, Runyao Duan, Zhengfeng Ji and Bei Zeng · 2011
Cited alongside, same era.
“Efficient algorithm for a quantum analogue of 2-SAT”
Sergey Bravyi · 2011
Cited alongside, same era.
“Criticality without frustration for quantum spin-1 chains”
Sergey Bravyi, Libor Caha, Ramis Movassagh, Daniel Nagaj and Peter. Shor · 2012
Cited alongside, same era.
“Solving condensed-matter ground-state problems by semidefinite relaxations”
Thomas Barthel and Robert Hübener · 2012
“Gapped and gapless phases of frustration-free spin- 1 / 2 1/2 chains”
Sergey Bravyi and David Gosset · 2015
Later among the works it cites.
“The complexity of antiferromagnetic interactions and 2D lattices”, 2015, pp. 35
Stephen Piddock and Ashley Montanaro · 2015
Later among the works it cites.
“Hamiltonian quantum computer in one dimension”
Tzu-Chieh Wei and John. Liang · 2015
Later among the works it cites.
“A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians”
Zeph Landau, Umesh Vazirani and Thomas Vidick · 2015
Later among the works it cites.
“Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction”
David Gosset, Barbara. Terhal and Anna Vershynina · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
“Universal two-body-Hamiltonian quantum computing”
Daniel Nagaj · 2012
Cited alongside, same era.
“Quantum computational complexity”
John Watrous · 2012
Cited alongside, same era.
“The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems”
Daniel Gottesman and Sandy Irani · 2013
Cited alongside, same era.
“The local Hamiltonian problem on a line with eight states is QMA-complete”
Sean Hallgren, Daniel Nagaj and Sandeep Narayanaswami · 2013
Cited alongside, same era.
“Introduction to reversible computing”, Chapman & Hall/CRC Computational Science Series
Kalyan S · 2013
Cited alongside, same era.
“Introduction to graph theory”, Dover Books on Mathematics
Richard. Trudeau · 2013
Cited alongside, same era.
“Supercritical entanglement in local systems: Counterexample to the area law for quantum matter”
Ramis Movassagh and Peter. Shor · 2016
Closest in time.
“Size-Driven Quantum Phase Transitions”
Johannes Bausch, Toby Cubitt, Angelo Lucia, David Perez-Garcia and Michael. Wolf · 2016
Closest in time.
“Complexity classification of local Hamiltonian problems”
Toby Cubitt and Ashley Montanaro · 2016
Closest in time.
“Linear time algorithm for quantum 2SAT”
Itai Arad, Miklos Santha, Aarthi Sundaram and Shengyu Zhang · 2016
Closest in time.
“A linear time algorithm for quantum 2-SAT”
Niel de Beaudrap and Sevag Gharibian · 2016
Closest in time.
“Quantum 3-SAT is QMA1-complete”
David Gosset and Daniel Nagaj · 2016
Closest in time.
“Quantum proofs”
Thomas Vidick and John Watrous · 2016
Closest in time.
“Increasing the quantum UNSAT penalty of the circuit-to-Hamiltonian construction”, 2016
Johannes Bausch and Elizabeth Crosson · 2016
Closest in time.
“Graph theory” 173
Reinhard Diestel · 2016
Closest in time.