[1]   Scott Aaronson and Daniel Gottesman: Improved simulation of stabilizer circuits. Phys. Rev. A, 70(5):052328, 2004. [doi:10.1103/PhysRevA.70.052328]

[2]   Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani: The detectability lemma and quantum gap amplification. In Proc. 41st STOC, pp. 417–426. ACM Press, 2009. [doi:10.1145/1536414.1536472]

[3]   Dorit Aharonov, Itai Arad, and Thomas Vidick: Guest column: The quantum PCP conjecture. SIGACT News, 44(2):47–79, 2013. [doi:10.1145/2491533.2491549]

[4]   Dorit Aharonov and Lior Eldar: The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP. Quantum Info. Processing, 14(1):83–101, 2015. [doi:10.1007/s11128-014-0877-9]

[5]   Dorit Aharonov and Lior Eldar: Quantum locally testable codes. SIAM J. Comput., 44(5):1230–1262, 2015. [doi:10.1137/140975498]

[6]   Dorit Aharonov and Tomer Naveh: Quantum NP – A survey, 2002. [arXiv:quant-ph/0210077]

[7]   Robert Alicki and Mark Fannes: Continuity of quantum conditional information. J. Phys. A: Math. Gen., 37(5):L55, 2004. [doi:10.1088/0305-4470/37/5/L01]

[8]   Anurag Anshu and Nikolas P. Breuckmann: A construction of combinatorial NLTS. J. Math. Phys., 63(122201):1–12, 2022. [doi:10.1063/5.0113731, arXiv:2206.02741]

[9]   Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe: NLTS Hamiltonians from good quantum codes. In Proc. 55th STOC, pp. 1090–1096. ACM Press, 2023. [doi:10.1145/3564246.3585114, arXiv:2206.13228]

[10]   Anurag Anshu, Aram W. Harrow, and Mehdi Soleimanifar: Entanglement spread area law in gapped ground states. Nature Physics, 18(11):1362–1366, 2022. [doi:10.1038/s41567-022-01740-7, arXiv:2004.15009]

[11]   Anurag Anshu and Chinmay Nirkhe: Circuit lower bounds for low-energy states of quantum code Hamiltonians. In Proc. 13th Innovations in Theoret. Comp. Sci. Conf. (ITCS’22), pp. 6:1–22. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2022. [doi:10.4230/LIPIcs.ITCS.2022.6]

[12]   Bruno Apolloni, Maria C. Carvalho, and Diego de Falco: Quantum stochastic optimization. Stoch. Proc. Appl., 33(2):233–244, 1989. [doi:10.1016/0304-4149(89)90040-9]

[13]   Itai Arad, Alexei Yurievich Kitaev, Zeph Landau, and Umesh Vazirani: An area law and sub-exponential algorithm for 1D systems, 2013. [arXiv:1301.1162]

[14]   Itai Arad, Zeph Landau, and Umesh Vazirani: Improved one-dimensional area law for frustration-free systems. Phys. Rev. B, 85(19):195145, 2012. [doi:10.1103/PhysRevB.85.195145]

[15]   Johannes Bausch and Elizabeth Crosson: Analysis and limitations of modified circuit-to-Hamiltonian constructions. Quantum, 2(94):1–36, 2018. [doi:10.22331/q-2018-09-19-94]

[16]   Chris Beck, Russell Impagliazzo, and Shachar Lovett: Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. In Proc. 53rd FOCS, pp. 101–110. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.82]

[17]   Fernando G. S. L. Brandaõ and Aram W. Harrow: Product-state approximations to quantum states. Comm. Math. Phys., 342:47–80, 2016. Preliminary version in STOC’13. [doi:10.1007/s00220-016-2575-1]

[18]   Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang: Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125(26):260505, 2020. [doi:10.1103/PhysRevLett.125.260505, arXiv:1910.08980]

[19]   Sergey Bravyi, David Poulin, and Barbara Terhal: Tradeoffs for reliable quantum information storage in 2D systems. Phys. Rev. Lett., 104(5):050503, 2010. [doi:10.1103/PhysRevLett.104.050503]

[20]   Sergey Bravyi and Mikhail Vyalyi: Commutative version of the local Hamiltonian problem and common eigenspace problem. Quantum Inf. Comput., 5(3):187–215, 2005. ACM DL.

[21]   Nikolas P. Breuckmann and Jens N. Eberhardt: Balanced product quantum codes. IEEE Trans. Inform. Theory, 67(10):6653–6674, 2021. [doi:10.1109/TIT.2021.3097347, arXiv:2012.09271]

[22]   Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358–368. IEEE Comp. Soc., 1999. [doi:10.1109/SFFCS.1999.814607, arXiv:cs/9904019]

[23]   Libor Caha, Zeph Landau, and Daniel Nagaj: Clocks in Feynman’s computer and Kitaev’s local Hamiltonian: Bias, gaps, idling, and pulse tuning. Phys. Rev. A, 97(6):062306, 2018. [doi:10.1103/PhysRevA.97.062306]

[24]   Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik: Quantum chemistry in the age of quantum computing. Chemical Reviews, 119(19):10856–10915, 2019. [doi:10.1021/acs.chemrev.8b00803]

[25]   Irit Dinur: The PCP Theorem by gap amplification. J. ACM, 54(3):12–55, 2007. [doi:10.1145/1236457.1236459]

[26]   Lior Eldar: Robust quantum entanglement at (nearly) room temperature. In Proc. 12th Innovations in Theoret. Comp. Sci. Conf. (ITCS’21), pp. 49:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.ITCS.2021.49, arXiv:1911.04461]

[27]   Lior Eldar and Aram W. Harrow: Local Hamiltonians whose ground states are hard to approximate. In Proc. 58th FOCS, pp. 427–438. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.46]

[28]   Edward Farhi, Jeffrey Goldstone, and Sam Gutmann: A quantum approximate optimization algorithm, 2014. [arXiv:1411.4028]

[29]   Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland: Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86(3):032324, 2012. [doi:10.1103/PhysRevA.86.032324]

[30]   Michael H. Freedman and Matthew B. Hastings: Quantum systems on non-k-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs. Quantum Inf. Comput., 14(1–2):144–180, 2014. ACM DL. [arXiv:1301.1363]

[31]   Larry Guth and Alexander Lubotzky: Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. J. Math. Phys., 55(8):082202, 2014. [doi:10.1063/1.4891487]

[32]   Matthew B. Hastings: An area law for one-dimensional quantum systems. J. Stat. Mech.: Theory and Experiment, 2007(08):P08024, 2007. [doi:10.1088/1742-5468/2007/08/P08024]

[33]   Matthew B. Hastings: Topological order at nonzero temperature. Phys. Rev. Lett., 107(21):210501, 2011. [doi:10.1103/PhysRevLett.107.210501]

[34]    Matthew B. Hastings: Quantum codes from high-dimensional manifolds. In Proc. 8th Innovations in Theoret. Comp. Sci. Conf. (ITCS’17), volume 67, pp. 25:1–26. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.25]

[35]   Matthew B. Hastings, Jeongwan Haah, and Ryan O’Donnell: Fiber bundle codes: Breaking the N^1∕2polylog(N) barrier for quantum LDPC codes. In Proc. 53rd STOC, pp. 1276–1288. ACM Press, 2021. [doi:10.1145/3406325.3451005, arXiv:2009.03921]

[36]   Tadashi Kadowaki and Hidetoshi Nishimori: Quantum annealing in the transverse ising model. Phys. Rev. E, 58(5):5355–5363, 1998. [doi:10.1103/PhysRevE.58.5355]

[37]   Jeff Kahn, Nathan Linial, and Alex Samorodnitsky: Inclusion-exclusion: Exact and approximate. Combinatorica, 16(4):465–477, 1996. [doi:10.1007/BF01271266]

[38]   Julia Kempe, Alexei Yurievich Kitaev, and Oded Regev: The complexity of the local Hamiltonian problem. SIAM J. Comput., 35(5):1070–1097, 2006. [doi:10.1137/S0097539704445226]

[39]    Alexei Yurievich Kitaev: Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–30, 2003. [doi:10.1016/S0003-4916(02)00018-0]

[40]   Alexei Yurievich Kitaev and John Preskill: Topological entanglement entropy. Phys. Rev. Lett., 96(11):110404, 2006. [doi:10.1103/PhysRevLett.96.110404]

[41]   Alexei Yurievich Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi: Classical and Quantum Computation. Amer. Math. Soc., 2002. ACM DL.

[42]   Emanuel Knill and Raymond Laflamme: Theory of quantum error-correcting codes. Phys. Rev. A, 55(2):900–911, 1997. [doi:10.1103/PhysRevA.55.900]

[43]   Ryan LaRose, Arkin Tikku, Étude O’Neel-Judy, Lukasz Cincio, and Patrick J. Coles: Variational quantum state diagonalization. npj Quantum Information, 5(1):57, 2019. [doi:10.1038/s41534-019-0167-6]

[44]   Anthony Leverrier, Vivien Londe, and Gilles Zémor: Towards local testability for quantum coding. Quantum, 6(661):1–43, 2022. [doi:10.22331/q-2022-02-24-661, arXiv:1911.03069]

[45]   Vivien Londe and Anthony Leverrier: Golden codes: Quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds. Quantum Inf. Comput., 19(5 & 6):361–391, 2019. [doi:10.26421/QIC19.5-6]

[46]   Shachar Lovett and Emanuele Viola: Bounded-depth circuits cannot sample good codes. Comput. Complexity, 21(2):245–266, 2012. [doi:10.1007/s00037-012-0039-3, ECCC:TR10-115]

[47]   Anand Natarajan and Thomas Vidick: Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. In Proc. 59th FOCS, pp. 731–742. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00075]

[48]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge Univ. Press, 2010. [doi:10.1017/CBO9780511976667]

[49]   Chinmay Nirkhe: Lower bounds on the complexity of quantum proofs. Ph. D. thesis, EECS Dept., UC Berkeley, 2022. Available as Tech Report UCB/EECS-2022-236.

[50]   Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen: Approximate low-weight check codes and circuit lower bounds for noisy ground states. In Proc. 45th Internat. Colloq. on Automata, Languages, and Programming (ICALP’18), volume 107, pp. 91:1–11. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ICALP.2018.91]

[51]   Pavel Panteleev and Gleb Kalachev: Quantum LDPC codes with almost linear minimum distance. IEEE Trans. Inform. Theory, 68(1):213–229, 2021. [doi:10.1109/tit.2021.3119384, arXiv:2012.04068]

[52]   Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien: A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5(4213):1–7, 2014. [doi:10.1038/ncomms5213]

[53]   Robert Raussendorf and Hans J. Briegel: A one-way quantum computer. Phys. Rev. Lett., 86(22):5188–5191, 2001. [doi:10.1103/PhysRevLett.86.5188]

[54]   Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel: Measurement-based quantum computation on cluster states. Phys. Rev. A, 68(2):022312, 2003. [doi:10.1103/PhysRevA.68.022312]

[55]   Jean-Pierre Tillich and Gilles Zémor: Quantum LDPC codes with positive rate and minimum distance proportional to the square root of blocklength. IEEE Trans. Inform. Theory, 60(2):1193–1202, 2014. Preliminary version in Internat. Symp. Info. Thy (ISIT’09). [doi:10.1109/TIT.2013.2292061]

[56]   Joel A. Tropp: User-friendly tail bounds for sums of random matrices. Found. Computational Math., 12(4):389–434, 2012. [doi:10.1007/s10208-011-9099-z]

[57]   Armin Uhlmann: The “transition probability” in the state space of a *-algebra. Rep. Math. Phys., 9(2):273–279, 1976. [doi:10.1016/0034-4877(76)90060-4]

[58]   Steven R. White: Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett., 69(19):2863–2866, 1992. [doi:10.1103/PhysRevLett.69.2863]