# Characterization of solvable spin models via graph invariants

Adrian Chapman and Steven T. Flammia

Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, Australia

### Abstract

Exactly solvable models are essential in physics. For many-body spin-$\mathbf{\sf{1}/{2}}$ 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.

An important situation in theoretical physics, called a duality, occurs when the behaviors of two physical systems perfectly coincide. A physical system is any isolated section of the universe, such as a collection of gas particles in a box, or vibrational waves traveling along a guitar string. A duality between two systems allows physicists to talk about the physics of one system in terms of the other system. Systems which are related in this way can be surprisingly different, and finding dualities is often a key step to understanding the behaviors of both. In the scenarios where one system looks very complicated, the other system can be very simple, and vice versa. By thinking in terms of the simpler system, physicists can bypass a great deal of complexity to understand the more complicated one.

In this work, we examine a certain class of dualites between two systems: quantum spin lattices and noninteracting fermions. A spin lattice consists of many interacting compass needles, or spins, arranged in some structure. Each spin feels the competing, or “frustrating”, influence from many different nearby spins, making the behavior of this model appear very complicated. A noninteracting fermion system consists of particles hopping between sites in a similarly discrete arrangement. Because the particles are fermions, they cannot occupy the same site, but they otherwise do not influence each other. In contrast to the spin model, the noninteracting nature of the fermion model makes it much simpler to work with. By considering the precise frustration structure of the spin model as a kind of network, we apply tools from network theory to find collections of spins which behave like emergent fermions, allowing us to extract the behavior of these complicated models in terms of the simpler noninteracting fermions. Though these types of dualities have been explored in the past, we developed a new framework to systematically find them. We expect these results to lead to the design of new quantum materials for the development of a quantum computer.

### ► References

[1] E. Lieb, T. Schultz, and D. Mattis, Annals of Physics 16, 407 (1961).
https:/​/​doi.org/​10.1016/​0003-4916(61)90115-4

[2] P. Jordan and E. Wigner, Zeitschrift für Physik 47, 631 (1928).
https:/​/​doi.org/​10.1007/​BF01331938

[3] E. Fradkin, Phys. Rev. Lett. 63, 322 (1989).
https:/​/​doi.org/​10.1103/​PhysRevLett.63.322

[4] Y. R. Wang, Phys. Rev. B 43, 3786 (1991).
https:/​/​doi.org/​10.1103/​PhysRevB.43.3786

[5] L. Huerta and J. Zanelli, Phys. Rev. Lett. 71, 3622 (1993).
https:/​/​doi.org/​10.1103/​PhysRevLett.71.3622

[6] C. D. Batista and G. Ortiz, Phys. Rev. Lett. 86, 1082 (2001).
https:/​/​doi.org/​10.1103/​PhysRevLett.86.1082

[7] F. Verstraete and J. I. Cirac, Journal of Statistical Mechanics: Theory and Experiment 2005, P09012 (2005).
https:/​/​doi.org/​10.1088/​1742-5468/​2005/​09/​p09012

[8] Z. Nussinov, G. Ortiz, and E. Cobanera, Phys. Rev. B 86, 085415 (2012).
https:/​/​doi.org/​10.1103/​PhysRevB.86.085415

[9] Y.-A. Chen, A. Kapustin, and DJ. Radičević, Annals of Physics 393, 234 (2018).
https:/​/​doi.org/​10.1016/​j.aop.2018.03.024

[10] S. Backens, A. Shnirman, and Y. Makhlin, Scientific reports 9, 2598 (2019).
https:/​/​doi.org/​10.1038/​s41598-018-38128-8

[11] N. Tantivasadakarn, arXiv e-prints , arXiv:2002.11345 (2020), arXiv:2002.11345 [cond-mat.str-el].
arXiv:2002.11345

[12] A. Kitaev, Annals of Physics 321, 2 (2006).
https:/​/​doi.org/​10.1016/​j.aop.2005.10.005

[13] E. Knill, ArXiv e-prints (2001), arXiv:quant-ph/​0108033.
arXiv:arXiv:quant-ph/0108033

[14] B. M. Terhal and D. P. DiVincenzo, Phys. Rev. A 65, 032325 (2002).
https:/​/​doi.org/​10.1103/​PhysRevA.65.032325

[15] M. Van Den Nest, Quantum Info. Comput. 11, 784 (2011).
http:/​/​dl.acm.org/​citation.cfm?id=2230936.2230941

[16] D. J. Brod, Phys. Rev. A 93, 062332 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.93.062332

[17] R. Jozsa and A. Miyake, Proc. R. Soc. A 464, 3089 (2008).
https:/​/​doi.org/​10.1098/​rspa.2008.0189

[18] D. J. Brod and E. F. Galvão, Phys. Rev. A 84, 022310 (2011).
https:/​/​doi.org/​10.1103/​PhysRevA.84.022310

[19] S. Bravyi, Phys. Rev. A 73, 042313 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.042313

[20] M. Hebenstreit, R. Jozsa, B. Kraus, S. Strelchuk, and M. Yoganathan, Phys. Rev. Lett. 123, 080503 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.123.080503

[21] D. J. Brod and A. M. Childs, Quant. Info. Comput. 14, 901 (2014).
https:/​/​doi.org/​10.26421/​qic14.11-12

[22] L. G. Valiant, SIAM Journal on Computing 31, 1229 (2002).
https:/​/​doi.org/​10.1137/​S0097539700377025

[23] 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–261.
https:/​/​doi.org/​10.1007/​11750321_24

[24] J. Cai, V. Choudhary, and P. Lu, in Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) (2007) pp. 305–318.
https:/​/​doi.org/​10.1109/​CCC.2007.22

[25] L. G. Valiant, SIAM Journal on Computing 37, 1565 (2008).
https:/​/​doi.org/​10.1137/​070682575

[26] C. H. Papadimitriou, in Encyclopedia of Computer Science (John Wiley and Sons Ltd., Chichester, UK, 1994) pp. 260–265.
http:/​/​dl.acm.org/​citation.cfm?id=1074100.1074233

[27] P. Kasteleyn, Physica 27, 1209 (1961).
https:/​/​doi.org/​10.1016/​0031-8914(61)90063-5

[28] H. N. V. Temperley and M. E. Fisher, Philosophical Magazine 6, 1061 (1961).
https:/​/​doi.org/​10.1080/​14786436108243366

[29] M. Planat and M. Saniga, Quant. Inf. Comput. 8, 127 (2008), arXiv:quant-ph/​0701211 [quant-ph].
arXiv:quant-ph/0701211

[30] A. Jena, S. Genin, and M. Mosca, arXiv e-prints , arXiv:1907.07859 (2019), arXiv:1907.07859 [quant-ph].
arXiv:1907.07859

[31] V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov, The Journal of Chemical Physics 152, 124114 (2020).
https:/​/​doi.org/​10.1063/​1.5141458

[32] 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].
arXiv:1908.08067

[33] A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi, Journal of Chemical Theory and Computation 16, 190 (2019).
https:/​/​doi.org/​10.1021/​acs.jctc.9b00791

[34] T.-C. Yen, V. Verteletskyi, and A. F. Izmaylov, Journal of Chemical Theory and Computation 16, 2400 (2020).
https:/​/​doi.org/​10.1021/​acs.jctc.0c00008

[35] 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].
arXiv:1907.13623

[36] 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].
arXiv:1908.06942

[37] X. Bonet-Monroig, R. Babbush, and T. E. O'Brien, arXiv e-prints , arXiv:1908.05628 (2019), arXiv:1908.05628 [quant-ph].
arXiv:1908.05628

[38] N. D. Roussopoulos, Information Processing Letters 2, 108 (1973).
https:/​/​doi.org/​10.1016/​0020-0190(73)90029-x

[39] P. G. H. Lehot, J. ACM 21, 569 (1974).
https:/​/​doi.org/​10.1145/​321850.321853

[40] D. G. Degiorgi and K. Simon, in Graph-Theoretic Concepts in Computer Science (Springer Berlin Heidelberg, Berlin, Heidelberg, 1995) pp. 37–48.
https:/​/​doi.org/​10.1007/​3-540-60618-1_64

[41] A. J. Kollár, M. Fitzpatrick, and A. A. Houck, Nature 571, 45 (2019a).
https:/​/​doi.org/​10.1038/​s41586-019-1348-3

[42] A. J. Kollár, M. Fitzpatrick, P. Sarnak, and A. A. Houck, Communications in Mathematical Physics , online only (2019b).
https:/​/​doi.org/​10.1007/​s00220-019-03645-8

[43] I. Boettcher, P. Bienias, R. Belyansky, A. J. Kollár, and A. V. Gorshkov, arXiv e-prints , arXiv:1910.12318 (2019), arXiv:1910.12318 [quant-ph].
arXiv:1910.12318

[44] 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).
https:/​/​www.iopconferences.org/​iop/​frontend/​reg/​absViewDocumentFE.csp?documentID=28672&eventID=1264

[45] H. Whitney, American Journal of Mathematics 54, 150 (1932).
https:/​/​doi.org/​10.2307/​2371086

[46] D. M. Goodmanson, American Journal of Physics 64, 870 (1996).
https:/​/​doi.org/​10.1119/​1.18113

[47] L. W. Beineke, Journal of Combinatorial Theory 9, 129 (1970).
https:/​/​doi.org/​10.1016/​s0021-9800(70)80019-9

[48] Ľ. Šoltés, Discrete Mathematics 132, 391 (1994).
https:/​/​doi.org/​10.1016/​0012-365x(92)00577-e

[49] Y. Yang, J. Lin, and C. Wang, Discrete Mathematics 252, 287 (2002).
https:/​/​doi.org/​10.1016/​S0012-365X(01)00459-9

[50] P. Erdős, A. W. Goodman, and L. Pósa, Canadian Journal of Mathematics 18, 106 (1966).
https:/​/​doi.org/​10.4153/​CJM-1966-014-3

[51] F. Harary, Graph Theory, Addison Wesley series in mathematics (Addison-Wesley, 1971).

[52] J. Krausz, Matematikai és Fizikai Lapok 50 (1943).
http:/​/​real-j.mtak.hu/​7300/​

[53] A. Bednarek, Discrete Mathematics 56, 83 (1985).
https:/​/​doi.org/​10.1016/​0012-365x(85)90196-7

[54] M. Suchara, S. Bravyi, and B. Terhal, Journal of Physics A: Mathematical and Theoretical 44, 155301 (2011).
https:/​/​doi.org/​10.1088/​1751-8113/​44/​15/​155301

[55] H. Bombín, New Journal of Physics 18, 043038 (2016).
https:/​/​doi.org/​10.1088/​1367-2630/​18/​4/​043038

[56] H. Bombín, Phys. Rev. X 5, 031043 (2015).
https:/​/​doi.org/​10.1103/​PhysRevX.5.031043

[57] A. Kubica and M. E. Beverland, Phys. Rev. A 91, 032330 (2015).
https:/​/​doi.org/​10.1103/​PhysRevA.91.032330

[58] H. Bombín, New Journal of Physics 17, 083002 (2015).
https:/​/​doi.org/​10.1088/​1367-2630/​17/​8/​083002

[59] B. J. Brown, N. H. Nickerson, and D. E. Browne, Nature Communications 7, 12302 (2016).
https:/​/​doi.org/​10.1038/​ncomms12302

[60] A. Y. Kitaev, Physics-Uspekhi 44, 131 (2001).
https:/​/​doi.org/​10.1070/​1063-7869/​44/​10s/​s29

[61] J. Klassen and B. M. Terhal, Quantum 3, 139 (2019).
https:/​/​doi.org/​10.22331/​q-2019-05-06-139

[62] P. Fendley, Journal of Physics A: Mathematical and Theoretical 52, 335002 (2019).
https:/​/​doi.org/​10.1088/​1751-8121/​ab305d

[63] S. B. Bravyi and A. Y. Kitaev, Ann. Phys. (N. Y.) 298, 210 (2002).
https:/​/​doi.org/​10.1006/​aphy.2002.6254

[64] J. T. Seeley, M. J. Richard, and P. J. Love, The Journal of Chemical Physics 137, 224109 (2012).
https:/​/​doi.org/​10.1063/​1.4768229

[65] K. Setia, S. Bravyi, A. Mezzacapo, and J. D. Whitfield, Phys. Rev. Research 1, 033033 (2019).
https:/​/​doi.org/​10.1103/​PhysRevResearch.1.033033

[66] R. C. Ball, Phys. Rev. Lett. 95, 176407 (2005).
https:/​/​doi.org/​10.1103/​PhysRevLett.95.176407

[67] S. Bravyi, J. M. Gambetta, A. Mezzacapo, and K. Temme, arXiv e-prints , arXiv:1701.08213 (2017), arXiv:1701.08213 [quant-ph].
arXiv:1701.08213

[68] M. Steudtner and S. Wehner, New Journal of Physics 20, 063010 (2018).
https:/​/​doi.org/​10.1088/​1367-2630/​aac54f

[69] Z. Jiang, J. McClean, R. Babbush, and H. Neven, Phys. Rev. Applied 12, 064041 (2019).
https:/​/​doi.org/​10.1103/​PhysRevApplied.12.064041

[70] V. Havlíček, M. Troyer, and J. D. Whitfield, Phys. Rev. A 95, 032332 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.032332

[71] Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, arXiv e-prints , arXiv:1910.10746 (2019), arXiv:1910.10746 [quant-ph].
arXiv:1910.10746

[72] S. Bravyi and D. Gosset, Communications in Mathematical Physics 356, 451 (2017).
https:/​/​doi.org/​10.1007/​s00220-017-2976-9

[73] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

### Cited by

[1] Masahiro Ogura, Yukihisa Imamura, Naruhiko Kameyama, Kazuhiko Minami, and Masatoshi Sato, "Geometric criterion for solvability of lattice spin systems", Physical Review B 102 24, 245118 (2020).

[2] Artur F Izmaylov and Tzu-Ching Yen, "How to define quantum mean-field solvable Hamiltonians using Lie algebras", Quantum Science and Technology 6 4, 044006 (2021).

[3] Bart van Voorden, Matteo Marcuzzi, Kareljan Schoutens, and Jiří Minář, "Disorder enhanced quantum many-body scars in Hilbert hypercubes", Physical Review B 103 22, L220301 (2021).

[4] Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, "A note on simplicial cliques", Discrete Mathematics 344 9, 112470 (2021).

[5] Matteo Ippoliti, Michael J. Gullans, Sarang Gopalakrishnan, David A. Huse, and Vedika Khemani, "Entanglement Phase Transitions in Measurement-Only Dynamics", Physical Review X 11 1, 011030 (2021).

[6] Raditya Weda Bomantara, Sen Mu, and Jiangbin Gong, "Topological and dynamical features of periodically driven spin ladders", Physical Review B 103 23, 235404 (2021).

[7] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, "Low-Depth Mechanisms for Quantum Optimization", PRX Quantum 2 3, 030312 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-19 22:36:41) and SAO/NASA ADS (last updated successfully 2021-10-19 22:36:42). The list may be incomplete as not all publishers provide suitable and complete citation data.