Fetching the paper…
Reading the bibliography…
Recently it was shown that the so-called guided local Hamiltonian problem -- estimating the smallest eigenvalue of a $k$-local Hamiltonian when provided with a description of a quantum state ('guiding state') that is guaranteed to have substantial overlap with the true groundstate -- is BQP-complete for $k \geq 6$ when the required precision is inverse polynomial in the system size $n$, and remains hard even when the overlap of the guiding state with the groundstate is close to a constant $\left(\frac12 - \Omega\left(\frac{1}{\mathop{poly}(n)}\right)\right)$.
Dorit Aharonov and Alex B. Grilo · 1901
Earlier work this paper cites.
Classical and quantum computation
Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi · 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.
Computational complexity: Why quantum chemistry is hard
Scott Aaronson · 2009
Earlier work this paper cites.
Quantum-merlin-arthur–complete problems for stoquastic hamiltonians and markov matrices
Stephen P. Jordan, David Gosset, and Peter J. Love · 2010
Earlier work this paper cites.
Schrieffer-Wolff transformation for quantum many-body systems
Sergey Bravyi, David P. DiVincenzo, and Daniel Loss · 2011
Cited alongside, same era.
Qma with subset state witnesses
Alex Bredariol Grilo, Iordanis Kerenidis, and Jamie Sikora · 2015
Cited alongside, same era.
The quantum complexity of computing schatten p-norms
Chris Cade and Ashley Montanaro · 2018
Cited alongside, same era.
Quantum algorithms for quantum chemistry and quantum materials science
Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan · 2020
Cited alongside, same era.
Electronic structure in a fixed basis is qma-complete
Bryan O’Gorman, Sandy Irani, James Whitfield, and Bill Fefferman · 2021
Cited alongside, same era.
Improved hardness results for the guided local hamiltonian problem
Sevag Gharibian, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae · 2022
Closest in time.
Sevag Gharibian and François Le Gall · 2022
Closest in time.
Maarten Stroeks, Jonas Helsen, and Barbara Terhal · 2022
Closest in time.
Jordi Weggemans, Marten Folkertsma, and Chris Cade · 2023
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…