Fetching the paper…
Reading the bibliography…
We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem, which we call 'Guidable Local Hamiltonian' problems.
Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui and Wenyuan Liu · 1952
Earlier work this paper cites.
“The double dixie cup problem”
Donald Newman · 1960
Earlier work this paper cites.
“The complexity of theorem-proving procedures”
Stephen. Cook · 1971
Earlier work this paper cites.
“Universal sequential search problems”
Leonid. Levin · 1973
Earlier work this paper cites.
“The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines”
Paul Benioff · 1980
Earlier work this paper cites.
“Simulating Physics with Computers”
Richard Feynman · 1982
Earlier work this paper cites.
“NP is as easy as detecting unique solutions”
L Valiant and V Vazirani · 1985
Earlier work this paper cites.
“Probabilistic quantifiers and games”
Stathis Zachos · 1988
Earlier work this paper cites.
“The role of relativization in complexity theory”
Lance Fortnow · 1994
Earlier work this paper cites.
“Mixed-state entanglement and quantum error correction” arXiv:quant-ph/9604024
Charles. Bennett, David. DiVincenzo, John. Smolin and William. Wootters · 1996
Earlier work this paper cites.
“Proof Verification and the Hardness of Approximation Problems”
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy · 1998
Earlier work this paper cites.
“Probabilistic checking of proofs: a new characterization of NP”
Sanjeev Arora and Shmuel Safra · 1998
Earlier work this paper cites.
“The Heisenberg representation of quantum computers” arXiv:quant-ph/9807006
Daniel Gottesman · 1998
Earlier work this paper cites.
“Some Optimal Inapproximability Results”
Johan Håstad · 2001
Earlier work this paper cites.
“Creating superpositions that correspond to efficiently integrable probability distributions” arXiv:quant-ph/0208112
Lov Grover and Terry Rudolph · 2002
Earlier work this paper cites.
“Classical and quantum computation”
Alexei. Kitaev, Alexander Shen and Mikhail. Vyalyi · 2002
Earlier work this paper cites.
“3-local Hamitonian is QMA-complete” arXiv:0302079
Julia Kempe and Oded Regev · 2003
Earlier work this paper cites.
“Quantum Computing and Error Correction” arXiv:quant-ph/0304016 , 2003
A.. Steane · 2003
Earlier work this paper cites.
“Two QCMA-complete problems” arXiv:quant-ph/0305090
Pawel Wocjan, Dominik Janzing and Thomas Beth · 2003
Earlier work this paper cites.
“Improved simulation of stabilizer circuits” arXiv:quant-ph/0406196
Scott Aaronson and Daniel Gottesman · 2004
Earlier work this paper cites.
“Quantum Arthur-Merlin Games” arXiv:cs/0506068
Chris Marriott and John Watrous · 2004
Earlier work this paper cites.
“Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games” arXiv:quant-ph/0205133
Barbara. Terhal and David. DiVincenzo · 2004
Earlier work this paper cites.
“Sequential generation of entangled multiqubit states” arXiv:quant-ph/0501096
Christian Schön, Enrique Solano, Frank Verstraete, J. Cirac and Michael. Wolf · 2005
Earlier work this paper cites.
“Efficient algorithm for a quantum analogue of 2-SAT” arXiv:quant-ph/0602108 , 2006
Sergey Bravyi · 2006
Earlier work this paper cites.
“Merlin-Arthur games and stoquastic complexity” arXiv:quant-ph/0611021 , 2006
Sergey Bravyi, Arvid Bessen and Barbara Terhal · 2006
Earlier work this paper cites.
“The complexity of stoquastic local Hamiltonian problems” arXiv:quant-ph/0606140
Sergey Bravyi, David. DiVincenzo, Roberto. Oliveira and Barbara. Terhal · 2006
Earlier work this paper cites.
“On promise problems: A survey”
Oded Goldreich · 2006
Earlier work this paper cites.
“Consistency of Local Density Matrices is QMA-complete” arXiv:quant-ph/0604166 , 2006
Yi-Kai Liu · 2006
Earlier work this paper cites.
“The PCP theorem by gap amplification”
Irit Dinur · 2007
Earlier work this paper cites.
“Computational Complexity of Projected Entangled Pair States” arXiv:0611050
Norbert Schuch, Michael. Wolf, Frank Verstraete and J. Cirac · 2007
Cited alongside, same era.
Sergey Bravyi, David. DiVincenzo, Daniel Loss and Barbara. Terhal · 2008
Cited alongside, same era.
“Randomized benchmarking of quantum gates” arXiv:0707.0963
E. Knill, D. Leibfried, R. Reichle, J. Britton, R.. Blakestad, J.. Jost, C. Langer, R. Ozeri, S. Seidelin and D.. Wineland · 2008
Cited alongside, same era.
Frank Verstraete, Valentin Murg and J Cirac · 2008
Cited alongside, same era.
“Computational complexity: Why quantum chemistry is hard”
Sevag Gharibian and Ojas Parekh · 2019
Later among the works it cites.
“The complexity of simulating local measurements on quantum systems” arXiv:1606.05626
Sevag Gharibian and Justin Yirka · 2019
Later among the works it cites.
András Gilyén, Yuan Su, Guang Low and Nathan Wiebe · 2019
Later among the works it cites.
“Oracle separation of BQP and PH”
Ran Raz and Avishay Tal · 2019
Later among the works it cites.
“A quantum-inspired classical algorithm for recommendation systems” arXiv:1807.04271
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Scott Aaronson · 2009
Cited alongside, same era.
“The detectability lemma and quantum gap amplification” arXiv:0811.3412
Dorit Aharonov, Itai Arad, Zeph Landau and Umesh Vazirani · 2009
Cited alongside, same era.
“BQP and the polynomial hierarchy” arXiv:0910.4698
Scott Aaronson · 2010
Cited alongside, same era.
“Complexity of stoquastic frustration-free Hamiltonians” arXiv:0806.1746
Sergey Bravyi and Barbara Terhal · 2010
Cited alongside, same era.
Michael Bremner, Richard Jozsa and Dan Shepherd · 2010
Cited alongside, same era.
“A note about a partial no-go theorem for quantum PCP” arXiv:1012.3319
Itai Arad · 2011
Cited alongside, same era.
“A PCP Characterization of AM” arXiv:1002.3664
Andrew Drucker · 2011
Cited alongside, same era.
“Markov Entropy Decomposition: A Variational Dual for Quantum Belief Propagation” arXiv:1012.2050
David Poulin and Matthew. Hastings · 2011
Cited alongside, same era.
Ewin Tang · 2019
Later among the works it cites.
“Quantum Algorithms for Quantum Chemistry and Quantum Materials Science” arXiv:2001.03685
Bela Bauer, Sergey Bravyi, Mario Motta and Garnet. Chan · 2020
Later among the works it cites.
“A short note on learning discrete distributions” arXiv:2002.11457 , 2020
Clément Canonne · 2020
Later among the works it cites.
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang and Chunhao Wang · 2020
Later among the works it cites.
“Quantum-Inspired Classical Algorithms for Singular Value Transformation” arXiv:1910.05699
Dhawal Jethwani, François Le and Sanjay. Singh · 2020
Later among the works it cites.
“Near-optimal ground state preparation” arXiv:2002.12508
Lin Lin and Yu Tong · 2020
Later among the works it cites.
“Reducing SAT to Max2SAT”
Carlos Ansótegui and Jordi Levy · 2021
Later among the works it cites.
“Quantum computing enhanced computational catalysis” arXiv:2007.14460
Vera Burg, Guang Low, Thomas Häner, Damian. Steiger, Markus Reiher, Martin Roetteler and Matthias Troyer · 2021
Later among the works it cites.
“Revisiting dequantization and quantum advantage in learning tasks” arXiv:2112.00811 , 2021
Jordan Cotler, Hsin-Yuan Huang and Jarrod. McClean · 2021
Later among the works it cites.
“StoqMA Meets Distribution Testing” arXiv:2011.05733
Yupan Liu · 2021
Later among the works it cites.
“Universal qudit hamiltonians” arXiv:1802.07130
Stephen Piddock and Ashley Montanaro · 2021
Later among the works it cites.
“The Acrobatics of BQP” arXiv:2111.10409
Scott Aaronson, DeVon Ingram and William Kretschmer · 2022
Later among the works it cites.
Dorit Aharonov, Michael Ben-Or, Fernando.S.L. Brandão and Or Sattath · 2022
Later among the works it cites.
“NLTS Hamiltonians from good quantum codes” arXiv:2206.13228
Anurag Anshu, Nikolas. Breuckmann and Chinmay Nirkhe · 2022
Later among the works it cites.
Anne Broadbent and Alex Grilo · 2022
Later among the works it cites.
Chris Cade, Marten Folkertsma and Jordi Weggemans · 2022
Later among the works it cites.
“Importance of the Spectral gap in Estimating Ground-State Energies” arXiv:2007.11582
Abhinav Deshpande, Alexey. Gorshkov and Bill Fefferman · 2022
Later among the works it cites.
Sevag Gharibian and François Le · 2022
Later among the works it cites.
“Prospects of quantum computing for molecular sciences” arXiv:2102.10081
Hongbin Liu, Guang Low, Damian. Steiger, Thomas Häner, Markus Reiher and Matthias Troyer · 2022
Later among the works it cites.
“Intractability of Electronic Structure in a Fixed Basis” arXiv:2103.08215
Bryan O’Gorman, Sandy Irani, James Whitfield and Bill Fefferman · 2022
Later among the works it cites.
“The variational quantum eigensolver: a review of methods and best practices” arXiv:2111.05176
Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger and George. Booth · 2022
Later among the works it cites.
“The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate” arXiv:2211.12519
Lennart Bittel, Sevag Gharibian and Martin Kliesch · 2023
Closest in time.
“Improved Hardness Results for the Guided Local Hamiltonian Problem” arXiv:2207.10250
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le, Tomoyuki Morimae and Jordi Weggemans · 2023
Closest in time.
“Local Hamiltonians with no low-energy stabilizer states” arXiv:2302.14755
Nolan Coble, Matthew Coudron, Jon Nelson and Seyed Nezhadi · 2023
Closest in time.
“Local Hamiltonian Problem with succinct ground state is MA-Complete” arXiv:2309.10155 , 2023
Jiaqing Jiang · 2023
Closest in time.