{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:33Z","timestamp":1750220973556,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1410022"],"award-info":[{"award-number":["CCF-1410022"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["PGSD Award"],"award-info":[{"award-number":["PGSD Award"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-12-1-0541"],"award-info":[{"award-number":["W911NF-12-1-0541"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316384","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"481-490","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Good approximate quantum LDPC codes from spacetime circuit Hamiltonians"],"prefix":"10.1145","author":[{"given":"Thomas C.","family":"Bohdanowicz","sequence":"first","affiliation":[{"name":"California Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elizabeth","family":"Crosson","sequence":"additional","affiliation":[{"name":"University of New Mexico, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chinmay","family":"Nirkhe","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"Yuen","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/2491533.2491549"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1137\/140975498"},{"key":"e_1_3_2_1_3_1","volume-title":"On Gap-Simulation of Hamiltonians and the Impossibility of Quantum Degree-Reduction. arXiv preprint arXiv:1804.11084","author":"Aharonov Dorit","year":"2018","unstructured":"Dorit Aharonov and Leo Zhou . 2018. On Gap-Simulation of Hamiltonians and the Impossibility of Quantum Degree-Reduction. arXiv preprint arXiv:1804.11084 ( 2018 ). Dorit Aharonov and Leo Zhou. 2018. On Gap-Simulation of Hamiltonians and the Impossibility of Quantum Degree-Reduction. arXiv preprint arXiv:1804.11084 (2018)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1007\/JHEP04(2015)163"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1109\/TIT.2017.2663199"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1145\/1468075.1468121"},{"unstructured":"Johannes Bausch and Elizabeth Crosson. 2018.  Johannes Bausch and Elizabeth Crosson. 2018.","key":"e_1_3_2_1_7_1"},{"unstructured":"Analysis and limitations of modified circuit-to-Hamiltonian constructions. Quantum 2 (Sept. 2018) 94. 2018- 09- 19- 94  Analysis and limitations of modified circuit-to-Hamiltonian constructions. Quantum 2 (Sept. 2018) 94. 2018- 09- 19- 94","key":"e_1_3_2_1_8_1"},{"key":"e_1_3_2_1_9_1","volume-title":"General conditions for approximate quantum error correction and near-optimal recovery channels. Physical review letters 104, 12","author":"B\u00e9ny C\u00e9dric","year":"2010","unstructured":"C\u00e9dric B\u00e9ny and Ognyan Oreshkov . 2010. General conditions for approximate quantum error correction and near-optimal recovery channels. Physical review letters 104, 12 ( 2010 ), 120501. C\u00e9dric B\u00e9ny and Ognyan Oreshkov. 2010. General conditions for approximate quantum error correction and near-optimal recovery channels. Physical review letters 104, 12 (2010), 120501."},{"doi-asserted-by":"crossref","unstructured":"Thomas C. Bohdanowicz Elizabeth Crosson Chinmay Nirkhe and Henry Yuen. 2018. Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. (2018). arXiv: arXiv:1811.00277  Thomas C. Bohdanowicz Elizabeth Crosson Chinmay Nirkhe and Henry Yuen. 2018. Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. (2018). arXiv: arXiv:1811.00277","key":"e_1_3_2_1_10_1","DOI":"10.1145\/3313276.3316384"},{"key":"e_1_3_2_1_11_1","volume-title":"Quantum Error Correcting Codes in Eigenstates of Translation-Invariant Spin Chains. arXiv preprint arXiv:1710.04631","author":"Brandao Fernando GSL","year":"2017","unstructured":"Fernando GSL Brandao , Elizabeth Crosson , M Burak \u015eahino\u011flu , and John Bowen . 2017. Quantum Error Correcting Codes in Eigenstates of Translation-Invariant Spin Chains. arXiv preprint arXiv:1710.04631 ( 2017 ). Fernando GSL Brandao, Elizabeth Crosson, M Burak \u015eahino\u011flu, and John Bowen. 2017. Quantum Error Correcting Codes in Eigenstates of Translation-Invariant Spin Chains. arXiv preprint arXiv:1710.04631 (2017)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/2591796.2591870"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1063\/1.3490195"},{"unstructured":"Nikolas P Breuckmann and Barbara M Terhal. 2014.  Nikolas P Breuckmann and Barbara M Terhal. 2014.","key":"e_1_3_2_1_14_1"},{"key":"e_1_3_2_1_15_1","volume-title":"Journal of Physics A: Mathematical and Theoretical 47, 19","author":"Hamiltonian","year":"2014","unstructured":"Space-time circuit-to- Hamiltonian construction and its applications. Journal of Physics A: Mathematical and Theoretical 47, 19 ( 2014 ), 195304. Space-time circuit-to-Hamiltonian construction and its applications. Journal of Physics A: Mathematical and Theoretical 47, 19 (2014), 195304."},{"unstructured":"10\n    The proof has been ommitted and can be found in the full version { 9 }. STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Thomas C. Bohdanowicz Elizabeth Crosson Chinmay Nirkhe and Henry Yuen  10 The proof has been ommitted and can be found in the full version { 9 }. STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Thomas C. Bohdanowicz Elizabeth Crosson Chinmay Nirkhe and Henry Yuen","key":"e_1_3_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1109\/ISIT.2013.6620245"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1103\/PhysRevA.97.062306"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1103\/PhysRevA.54.1098"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1007\/11426639_17"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1109\/FOCS.2017.46"},{"key":"e_1_3_2_1_22_1","volume-title":"The Need for Structure in Quantum LDPC Codes. arXiv preprint arXiv:1610.07478","author":"Eldar Lior","year":"2016","unstructured":"Lior Eldar , Maris Ozols , and Kevin F Thompson . 2016. The Need for Structure in Quantum LDPC Codes. arXiv preprint arXiv:1610.07478 ( 2016 ). Lior Eldar, Maris Ozols, and Kevin F Thompson. 2016. The Need for Structure in Quantum LDPC Codes. arXiv preprint arXiv:1610.07478 (2016)."},{"unstructured":"Steven T Flammia Jeongwan Haah Michael J Kastoryano and Isaac H Kim. 2017.  Steven T Flammia Jeongwan Haah Michael J Kastoryano and Isaac H Kim. 2017.","key":"e_1_3_2_1_23_1"},{"key":"e_1_3_2_1_24_1","volume-title":"4","author":"Limits","year":"2017","unstructured":"Limits on the storage of quantum information in a volume of space. Quantum 1 ( 2017 ), 4 . Limits on the storage of quantum information in a volume of space. Quantum 1 (2017), 4."},{"key":"e_1_3_2_1_25_1","volume-title":"Z2-systolic freedom and quantum codes. Mathematics of quantum computation","author":"Freedman Michael H","year":"2002","unstructured":"Michael H Freedman , David A Meyer , and Feng Luo . 2002. Z2-systolic freedom and quantum codes. Mathematics of quantum computation , Chapman & amp; Hall\/CRC ( 2002 ), 287\u2013320. Michael H Freedman, David A Meyer, and Feng Luo. 2002. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall\/CRC (2002), 287\u2013320."},{"doi-asserted-by":"crossref","unstructured":"Robert G. Gallager. 1963. Low-Density Parity-Check Codes. (1963).  Robert G. Gallager. 1963. Low-Density Parity-Check Codes. (1963).","key":"e_1_3_2_1_26_1","DOI":"10.7551\/mitpress\/4347.001.0001"},{"unstructured":"Anand Ganti and Rolando Somma. 2013.  Anand Ganti and Rolando Somma. 2013.","key":"e_1_3_2_1_27_1"},{"key":"e_1_3_2_1_28_1","volume-title":"International Journal of Quantum Information 11, 07","author":"On","year":"2013","unstructured":"On the gap of Hamiltonians for the adiabatic simulation of quantum circuits. International Journal of Quantum Information 11, 07 ( 2013 ), 1350063. On the gap of Hamiltonians for the adiabatic simulation of quantum circuits. International Journal of Quantum Information 11, 07 (2013), 1350063."},{"key":"e_1_3_2_1_29_1","volume-title":"History-state Hamiltonians are critical. arXiv preprint arXiv:1810.06528","author":"Gonz\u00e1lez-Guill\u00e9n Carlos E","year":"2018","unstructured":"Carlos E Gonz\u00e1lez-Guill\u00e9n and Toby S Cubitt . 2018. History-state Hamiltonians are critical. arXiv preprint arXiv:1810.06528 ( 2018 ). Carlos E Gonz\u00e1lez-Guill\u00e9n and Toby S Cubitt. 2018. History-state Hamiltonians are critical. arXiv preprint arXiv:1810.06528 (2018)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1103\/PhysRevLett.114.140501"},{"unstructured":"Daniel Gottesman. 2013.  Daniel Gottesman. 2013.","key":"e_1_3_2_1_31_1"},{"volume-title":"arXiv preprint arXiv:1310.2984","year":"2013","unstructured":"Fault-tolerant quantum computation with constant overhead. arXiv preprint arXiv:1310.2984 ( 2013 ). Fault-tolerant quantum computation with constant overhead. arXiv preprint arXiv:1310.2984 (2013).","key":"e_1_3_2_1_32_1"},{"key":"e_1_3_2_1_33_1","volume-title":"Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information &amp","author":"Hastings Matthew B","year":"2013","unstructured":"Matthew B Hastings . 2013. Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information &amp ; Computation 13, 5-6 ( 2013 ), 393\u2013429. Matthew B Hastings. 2013. Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information & Computation 13, 5-6 (2013), 393\u2013429."},{"key":"e_1_3_2_1_34_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"67","author":"Hastings Matthew B","year":"2017","unstructured":"Matthew B Hastings . 2017 . Quantum Codes from High-Dimensional Manifolds . In LIPIcs-Leibniz International Proceedings in Informatics , Vol. 67 . Matthew B Hastings. 2017. Quantum Codes from High-Dimensional Manifolds. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 67."},{"unstructured":"Mathew B Hastings. 2017.  Mathew B Hastings. 2017.","key":"e_1_3_2_1_35_1"},{"key":"e_1_3_2_1_36_1","volume-title":"Quantum Information &amp","author":"Weight","year":"2017","unstructured":"Weight reduction for quantum codes. Quantum Information &amp ; Computation 17, 15-16 ( 2017 ), 1307\u20131334. Weight reduction for quantum codes. Quantum Information & Computation 17, 15-16 (2017), 1307\u20131334."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1002\/rsa.10051"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1016\/S0003-4916(02)00018-0"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1023\/A:1007351803403"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1088\/1742-5468\/aa7ee2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1103\/PhysRevA.56.2567"},{"unstructured":"Seth Lloyd Peter Shor and Kevin Thompson. 2017.  Seth Lloyd Peter Shor and Kevin Thompson. 2017.","key":"e_1_3_2_1_42_1"},{"key":"e_1_3_2_1_43_1","volume-title":"arXiv preprint arXiv:1703.00382","author":"Capacity Achieving LDPC","year":"2017","unstructured":"polylog- LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel . arXiv preprint arXiv:1703.00382 ( 2017 ). polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel. arXiv preprint arXiv:1703.00382 (2017)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1088\/1367-2630\/18\/2\/023042"},{"unstructured":"Neal Madras and Dana Randall. 2002.  Neal Madras and Dana Randall. 2002.","key":"e_1_3_2_1_45_1"},{"doi-asserted-by":"crossref","unstructured":"Markov chain decomposition for convergence rate analysis. Ann. Appl. Probab. 12 2 (05 2002) 581\u2013606.  Markov chain decomposition for convergence rate analysis. Ann. Appl. Probab. 12 2 (05 2002) 581\u2013606.","key":"e_1_3_2_1_46_1","DOI":"10.1214\/aoap\/1026915617"},{"key":"e_1_3_2_1_47_1","volume-title":"Simple proof of equivalence between adiabatic quantum computation and the circuit model. Physical review letters 99, 7","author":"Mizel Ari","year":"2007","unstructured":"Ari Mizel , Daniel A Lidar , and Morgan Mitchell . 2007. Simple proof of equivalence between adiabatic quantum computation and the circuit model. Physical review letters 99, 7 ( 2007 ), 070502. Ari Mizel, Daniel A Lidar, and Morgan Mitchell. 2007. Simple proof of equivalence between adiabatic quantum computation and the circuit model. Physical review letters 99, 7 (2007), 070502."},{"key":"e_1_3_2_1_48_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"107","author":"Nirkhe Chinmay","year":"2018","unstructured":"Chinmay Nirkhe , Umesh Vazirani , and Henry Yuen . 2018 . Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 107 . 91:1\u201391:11. Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen. 2018. Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 107. 91:1\u201391:11."},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. R. Soc. Lond. A 452","author":"Steane Andrew","year":"1996","unstructured":"Andrew Steane . 1996 . Multiple-particle interference and quantum error correction . Proc. R. Soc. Lond. A 452 , 1954 (1996), 2551\u20132577. Andrew Steane. 1996. Multiple-particle interference and quantum error correction. Proc. R. Soc. Lond. A 452, 1954 (1996), 2551\u20132577."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_50_1","DOI":"10.1109\/TIT.2013.2292061"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '19","name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316384","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":50,"alternative-id":["10.1145\/3313276.3316384","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316384","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}