{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T04:25:22Z","timestamp":1773375922181,"version":"3.50.1"},"reference-count":73,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T00:00:00Z","timestamp":1591228800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Exactly solvable models are essential in physics. For many-body spin-<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn mathvariant=\"sans-serif\">1<\/mml:mn><\/mml:mrow><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo mathvariant=\"sans-serif\">\/<\/mml:mo><\/mml:mrow><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn mathvariant=\"sans-serif\">2<\/mml:mn><\/mml:mrow><\/mml:mrow><\/mml:math>systems, an important class of such models consists of those that can be mapped to free fermions hopping on a graph. We provide a complete characterization of models which can be solved this way. Specifically, we reduce the problem of recognizing such spin models to the graph-theoretic problem of recognizing line graphs, which has been solved optimally. A corollary of our result is a complete set of constant-sized commutation structures that constitute the obstructions to a free-fermion solution. We find that symmetries are tightly constrained in these models. Pauli symmetries correspond to either: (i) cycles on the fermion hopping graph, (ii) the fermion parity operator, or (iii) logically encoded qubits. Clifford symmetries within one of these symmetry sectors, with three exceptions, must be symmetries of the free-fermion model itself. We demonstrate how several exact free-fermion solutions from the literature fit into our formalism and give an explicit example of a new model previously unknown to be solvable by free fermions.<\/jats:p>","DOI":"10.22331\/q-2020-06-04-278","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T12:36:52Z","timestamp":1591274212000},"page":"278","source":"Crossref","is-referenced-by-count":38,"title":["Characterization of solvable spin models via graph invariants"],"prefix":"10.22331","volume":"4","author":[{"given":"Adrian","family":"Chapman","sequence":"first","affiliation":[{"name":"Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3975-0226","authenticated-orcid":false,"given":"Steven T.","family":"Flammia","sequence":"additional","affiliation":[{"name":"Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, Australia"}]}],"member":"9598","published-online":{"date-parts":[[2020,6,4]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"E. Lieb, T. Schultz, and D. Mattis, Annals of Physics 16, 407 (1961).","DOI":"10.1016\/0003-4916(61)90115-4"},{"key":"1","doi-asserted-by":"publisher","unstructured":"P. Jordan and E. Wigner, Zeitschrift f\u00fcr Physik 47, 631 (1928).","DOI":"10.1007\/BF01331938"},{"key":"2","doi-asserted-by":"publisher","unstructured":"E. Fradkin, Phys. Rev. Lett. 63, 322 (1989).","DOI":"10.1103\/PhysRevLett.63.322"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Y. R. Wang, Phys. Rev. B 43, 3786 (1991).","DOI":"10.1103\/PhysRevB.43.3786"},{"key":"4","doi-asserted-by":"publisher","unstructured":"L. Huerta and J. Zanelli, Phys. Rev. Lett. 71, 3622 (1993).","DOI":"10.1103\/PhysRevLett.71.3622"},{"key":"5","doi-asserted-by":"publisher","unstructured":"C. D. Batista and G. Ortiz, Phys. Rev. Lett. 86, 1082 (2001).","DOI":"10.1103\/PhysRevLett.86.1082"},{"key":"6","doi-asserted-by":"publisher","unstructured":"F. Verstraete and J. I. Cirac, Journal of Statistical Mechanics: Theory and Experiment 2005, P09012 (2005).","DOI":"10.1088\/1742-5468\/2005\/09\/p09012"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Z. Nussinov, G. Ortiz, and E. Cobanera, Phys. Rev. B 86, 085415 (2012).","DOI":"10.1103\/PhysRevB.86.085415"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Y.-A. Chen, A. Kapustin, and DJ. Radi\u010devi\u0107, Annals of Physics 393, 234 (2018).","DOI":"10.1016\/j.aop.2018.03.024"},{"key":"9","doi-asserted-by":"publisher","unstructured":"S. Backens, A. Shnirman, and Y. Makhlin, Scientific reports 9, 2598 (2019).","DOI":"10.1038\/s41598-018-38128-8"},{"key":"10","unstructured":"N. Tantivasadakarn, arXiv e-prints , arXiv:2002.11345 (2020), arXiv:2002.11345 [cond-mat.str-el]."},{"key":"11","doi-asserted-by":"publisher","unstructured":"A. Kitaev, Annals of Physics 321, 2 (2006).","DOI":"10.1016\/j.aop.2005.10.005"},{"key":"12","unstructured":"E. Knill, ArXiv e-prints (2001), arXiv:quant-ph\/0108033."},{"key":"13","doi-asserted-by":"publisher","unstructured":"B. M. Terhal and D. P. DiVincenzo, Phys. Rev. A 65, 032325 (2002).","DOI":"10.1103\/PhysRevA.65.032325"},{"key":"14","unstructured":"M. Van Den Nest, Quantum Info. Comput. 11, 784 (2011)."},{"key":"15","doi-asserted-by":"publisher","unstructured":"D. J. Brod, Phys. Rev. A 93, 062332 (2016).","DOI":"10.1103\/PhysRevA.93.062332"},{"key":"16","doi-asserted-by":"publisher","unstructured":"R. Jozsa and A. Miyake, Proc. R. Soc. A 464, 3089 (2008).","DOI":"10.1098\/rspa.2008.0189"},{"key":"17","doi-asserted-by":"publisher","unstructured":"D. J. Brod and E. F. Galv\u00e3o, Phys. Rev. A 84, 022310 (2011).","DOI":"10.1103\/PhysRevA.84.022310"},{"key":"18","doi-asserted-by":"publisher","unstructured":"S. Bravyi, Phys. Rev. A 73, 042313 (2006).","DOI":"10.1103\/PhysRevA.73.042313"},{"key":"19","doi-asserted-by":"publisher","unstructured":"M. Hebenstreit, R. Jozsa, B. Kraus, S. Strelchuk, and M. Yoganathan, Phys. Rev. Lett. 123, 080503 (2019).","DOI":"10.1103\/PhysRevLett.123.080503"},{"key":"20","doi-asserted-by":"publisher","unstructured":"D. J. Brod and A. M. Childs, Quant. Info. Comput. 14, 901 (2014).","DOI":"10.26421\/qic14.11-12"},{"key":"21","doi-asserted-by":"publisher","unstructured":"L. G. Valiant, SIAM Journal on Computing 31, 1229 (2002).","DOI":"10.1137\/S0097539700377025"},{"key":"22","doi-asserted-by":"publisher","unstructured":"J.-Y. Cai and V. Choudhary, in Proceedings of the Third International Conference on Theory and Applications of Models of Computation, TAMC'06 (Springer-Verlag, Berlin, Heidelberg, 2006) pp. 248\u2013261.","DOI":"10.1007\/11750321_24"},{"key":"23","doi-asserted-by":"publisher","unstructured":"J. Cai, V. Choudhary, and P. Lu, in Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) (2007) pp. 305\u2013318.","DOI":"10.1109\/CCC.2007.22"},{"key":"24","doi-asserted-by":"publisher","unstructured":"L. G. Valiant, SIAM Journal on Computing 37, 1565 (2008).","DOI":"10.1137\/070682575"},{"key":"25","unstructured":"C. H. Papadimitriou, in Encyclopedia of Computer Science (John Wiley and Sons Ltd., Chichester, UK, 1994) pp. 260\u2013265."},{"key":"26","doi-asserted-by":"publisher","unstructured":"P. Kasteleyn, Physica 27, 1209 (1961).","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"27","doi-asserted-by":"publisher","unstructured":"H. N. V. Temperley and M. E. Fisher, Philosophical Magazine 6, 1061 (1961).","DOI":"10.1080\/14786436108243366"},{"key":"28","doi-asserted-by":"crossref","unstructured":"M. Planat and M. Saniga, Quant. Inf. Comput. 8, 127 (2008), arXiv:quant-ph\/0701211 [quant-ph].","DOI":"10.26421\/QIC8.1-2-9"},{"key":"29","unstructured":"A. Jena, S. Genin, and M. Mosca, arXiv e-prints , arXiv:1907.07859 (2019), arXiv:1907.07859 [quant-ph]."},{"key":"30","doi-asserted-by":"publisher","unstructured":"V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov, The Journal of Chemical Physics 152, 124114 (2020).","DOI":"10.1063\/1.5141458"},{"key":"31","unstructured":"A. Zhao, A. Tranter, W. M. Kirby, S. F. Ung, A. Miyake, and P. Love, arXiv e-prints , arXiv:1908.08067 (2019), arXiv:1908.08067 [quant-ph]."},{"key":"32","doi-asserted-by":"publisher","unstructured":"A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi, Journal of Chemical Theory and Computation 16, 190 (2019).","DOI":"10.1021\/acs.jctc.9b00791"},{"key":"33","doi-asserted-by":"publisher","unstructured":"T.-C. Yen, V. Verteletskyi, and A. F. Izmaylov, Journal of Chemical Theory and Computation 16, 2400 (2020).","DOI":"10.1021\/acs.jctc.0c00008"},{"key":"34","unstructured":"P. Gokhale, O. Angiuli, Y. Ding, K. Gui, T. Tomesh, M. Suchara, M. Martonosi, and F. T. Chong, arXiv e-prints , arXiv:1907.13623 (2019), arXiv:1907.13623 [quant-ph]."},{"key":"35","unstructured":"O. Crawford, B. van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley, arXiv e-prints , arXiv:1908.06942 (2019), arXiv:1908.06942 [quant-ph]."},{"key":"36","unstructured":"X. Bonet-Monroig, R. Babbush, and T. E. O'Brien, arXiv e-prints , arXiv:1908.05628 (2019), arXiv:1908.05628 [quant-ph]."},{"key":"37","doi-asserted-by":"publisher","unstructured":"N. D. Roussopoulos, Information Processing Letters 2, 108 (1973).","DOI":"10.1016\/0020-0190(73)90029-x"},{"key":"38","doi-asserted-by":"publisher","unstructured":"P. G. H. Lehot, J. ACM 21, 569 (1974).","DOI":"10.1145\/321850.321853"},{"key":"39","doi-asserted-by":"publisher","unstructured":"D. G. Degiorgi and K. Simon, in Graph-Theoretic Concepts in Computer Science (Springer Berlin Heidelberg, Berlin, Heidelberg, 1995) pp. 37\u201348.","DOI":"10.1007\/3-540-60618-1_64"},{"key":"40","doi-asserted-by":"publisher","unstructured":"A. J. Koll\u00e1r, M. Fitzpatrick, and A. A. Houck, Nature 571, 45 (2019a).","DOI":"10.1038\/s41586-019-1348-3"},{"key":"41","doi-asserted-by":"publisher","unstructured":"A. J. Koll\u00e1r, M. Fitzpatrick, P. Sarnak, and A. A. Houck, Communications in Mathematical Physics , online only (2019b).","DOI":"10.1007\/s00220-019-03645-8"},{"key":"42","unstructured":"I. Boettcher, P. Bienias, R. Belyansky, A. J. Koll\u00e1r, and A. V. Gorshkov, arXiv e-prints , arXiv:1910.12318 (2019), arXiv:1910.12318 [quant-ph]."},{"key":"43","unstructured":"T. Jochym-O'Connor, S. Roberts, S. Bartlett, and J. Preskill, ``Frustrated hexagonal gauge 3d color code,'' (2019), 5th International Conference on Quantum Error Correction (QEC 2019)."},{"key":"44","doi-asserted-by":"publisher","unstructured":"H. Whitney, American Journal of Mathematics 54, 150 (1932).","DOI":"10.2307\/2371086"},{"key":"45","doi-asserted-by":"publisher","unstructured":"D. M. Goodmanson, American Journal of Physics 64, 870 (1996).","DOI":"10.1119\/1.18113"},{"key":"46","doi-asserted-by":"publisher","unstructured":"L. W. Beineke, Journal of Combinatorial Theory 9, 129 (1970).","DOI":"10.1016\/s0021-9800(70)80019-9"},{"key":"47","doi-asserted-by":"publisher","unstructured":"\u013d. \u0160olt\u00e9s, Discrete Mathematics 132, 391 (1994).","DOI":"10.1016\/0012-365x(92)00577-e"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Y. Yang, J. Lin, and C. Wang, Discrete Mathematics 252, 287 (2002).","DOI":"10.1016\/S0012-365X(01)00459-9"},{"key":"49","doi-asserted-by":"publisher","unstructured":"P. Erd\u0151s, A. W. Goodman, and L. P\u00f3sa, Canadian Journal of Mathematics 18, 106 (1966).","DOI":"10.4153\/CJM-1966-014-3"},{"key":"50","unstructured":"F. Harary, Graph Theory, Addison Wesley series in mathematics (Addison-Wesley, 1971)."},{"key":"51","unstructured":"J. Krausz, Matematikai \u00e9s Fizikai Lapok 50 (1943)."},{"key":"52","doi-asserted-by":"publisher","unstructured":"A. Bednarek, Discrete Mathematics 56, 83 (1985).","DOI":"10.1016\/0012-365x(85)90196-7"},{"key":"53","doi-asserted-by":"publisher","unstructured":"M. Suchara, S. Bravyi, and B. Terhal, Journal of Physics A: Mathematical and Theoretical 44, 155301 (2011).","DOI":"10.1088\/1751-8113\/44\/15\/155301"},{"key":"54","doi-asserted-by":"publisher","unstructured":"H. Bomb\u00edn, New Journal of Physics 18, 043038 (2016).","DOI":"10.1088\/1367-2630\/18\/4\/043038"},{"key":"55","doi-asserted-by":"publisher","unstructured":"H. Bomb\u00edn, Phys. Rev. X 5, 031043 (2015).","DOI":"10.1103\/PhysRevX.5.031043"},{"key":"56","doi-asserted-by":"publisher","unstructured":"A. Kubica and M. E. Beverland, Phys. Rev. A 91, 032330 (2015).","DOI":"10.1103\/PhysRevA.91.032330"},{"key":"57","doi-asserted-by":"publisher","unstructured":"H. Bomb\u00edn, New Journal of Physics 17, 083002 (2015).","DOI":"10.1088\/1367-2630\/17\/8\/083002"},{"key":"58","doi-asserted-by":"publisher","unstructured":"B. J. Brown, N. H. Nickerson, and D. E. Browne, Nature Communications 7, 12302 (2016).","DOI":"10.1038\/ncomms12302"},{"key":"59","doi-asserted-by":"publisher","unstructured":"A. Y. Kitaev, Physics-Uspekhi 44, 131 (2001).","DOI":"10.1070\/1063-7869\/44\/10s\/s29"},{"key":"60","doi-asserted-by":"publisher","unstructured":"J. Klassen and B. M. Terhal, Quantum 3, 139 (2019).","DOI":"10.22331\/q-2019-05-06-139"},{"key":"61","doi-asserted-by":"publisher","unstructured":"P. Fendley, Journal of Physics A: Mathematical and Theoretical 52, 335002 (2019).","DOI":"10.1088\/1751-8121\/ab305d"},{"key":"62","doi-asserted-by":"publisher","unstructured":"S. B. Bravyi and A. Y. Kitaev, Ann. Phys. (N. Y.) 298, 210 (2002).","DOI":"10.1006\/aphy.2002.6254"},{"key":"63","doi-asserted-by":"publisher","unstructured":"J. T. Seeley, M. J. Richard, and P. J. Love, The Journal of Chemical Physics 137, 224109 (2012).","DOI":"10.1063\/1.4768229"},{"key":"64","doi-asserted-by":"publisher","unstructured":"K. Setia, S. Bravyi, A. Mezzacapo, and J. D. Whitfield, Phys. Rev. Research 1, 033033 (2019).","DOI":"10.1103\/PhysRevResearch.1.033033"},{"key":"65","doi-asserted-by":"publisher","unstructured":"R. C. Ball, Phys. Rev. Lett. 95, 176407 (2005).","DOI":"10.1103\/PhysRevLett.95.176407"},{"key":"66","unstructured":"S. Bravyi, J. M. Gambetta, A. Mezzacapo, and K. Temme, arXiv e-prints , arXiv:1701.08213 (2017), arXiv:1701.08213 [quant-ph]."},{"key":"67","doi-asserted-by":"publisher","unstructured":"M. Steudtner and S. Wehner, New Journal of Physics 20, 063010 (2018).","DOI":"10.1088\/1367-2630\/aac54f"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Z. Jiang, J. McClean, R. Babbush, and H. Neven, Phys. Rev. Applied 12, 064041 (2019).","DOI":"10.1103\/PhysRevApplied.12.064041"},{"key":"69","doi-asserted-by":"publisher","unstructured":"V. Havl\u00ed\u010dek, M. Troyer, and J. D. Whitfield, Phys. Rev. A 95, 032332 (2017).","DOI":"10.1103\/PhysRevA.95.032332"},{"key":"70","unstructured":"Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, arXiv e-prints , arXiv:1910.10746 (2019), arXiv:1910.10746 [quant-ph]."},{"key":"71","doi-asserted-by":"publisher","unstructured":"S. Bravyi and D. Gosset, Communications in Mathematical Physics 356, 451 (2017).","DOI":"10.1007\/s00220-017-2976-9"},{"key":"72","doi-asserted-by":"publisher","unstructured":"S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Quantum 3, 181 (2019).","DOI":"10.22331\/q-2019-09-02-181"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-06-04-278\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,18]],"date-time":"2021-03-18T16:01:48Z","timestamp":1616083308000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-06-04-278\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,4]]},"references-count":73,"URL":"https:\/\/doi.org\/10.22331\/q-2020-06-04-278","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,4]]},"article-number":"278"}}