[15] M. Van Den Nest, Quantum Info. Comput. 11,
784 (2011).
[16] D. J. Brod, Phys. Rev. A 93, 062332 (2016).
[17] R. Jozsa and A. Miyake, Proc. R. Soc. A 464,
3089 (2008).
[18] D. J. Brod and E. F. Galvão, Phys. Rev. A 84,
022310 (2011).
[19] S. Bravyi, Phys. Rev. A 73, 042313 (2006).
[20] M. Hebenstreit, R. Jozsa, B. Kraus, S. Strelchuk,
and M. Yoganathan, Phys. Rev. Lett. 123,
080503 (2019).
[21] D. J. Brod and A. M. Childs, Quant. Info. Com-
put. 14, 901 (2014).
[22] L. G. Valiant, SIAM Journal on Computing 31,
1229 (2002).
[23] J.-Y. Cai and V. Choudhary, in Proceedings
of the Third International Conference on The-
ory and Applications of Models of Computation,
TAMC’06 (Springer-Verlag, Berlin, Heidelberg,
2006) pp. 248–261.
[24] J. Cai, V. Choudhary, and P. Lu, in Twenty-
Second Annual IEEE Conference on Computa-
tional Complexity (CCC’07) (2007) pp. 305–318.
[25] L. G. Valiant, SIAM Journal on Computing 37,
1565 (2008).
[26] C. H. Papadimitriou, in Encyclopedia of Com-
puter Science (John Wiley and Sons Ltd., Chich-
ester, UK, 1994) pp. 260–265.
[27] P. Kasteleyn, Physica 27, 1209 (1961).
[28] H. N. V. Temperley and M. E. Fisher, Philosoph-
ical Magazine 6, 1061 (1961).
[29] M. Planat and M. Saniga, Quant. Inf. Comput. 8,
127 (2008), arXiv:quant-ph/0701211 [quant-ph] .
[30] A. Jena, S. Genin, and M. Mosca, arXiv e-prints
, arXiv:1907.07859 (2019), arXiv:1907.07859
[quant-ph] .
[31] V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov,
The Journal of Chemical Physics 152, 124114
(2020).
[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] .
[33] A. F. Izmaylov, T.-C. Yen, R. A. Lang, and
V. Verteletskyi, Journal of Chemical Theory and
Computation 16, 190 (2019).
[34] T.-C. Yen, V. Verteletskyi, and A. F. Izmaylov,
Journal of Chemical Theory and Computation
16, 2400 (2020).
[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] .
[36] O. Crawford, B. van Straaten, D. Wang,
T. Parks, E. Campbell, and S. Brier-
ley, arXiv e-prints , arXiv:1908.06942 (2019),
arXiv:1908.06942 [quant-ph] .
[37] X. Bonet-Monroig, R. Babbush, and T. E.
O’Brien, arXiv e-prints , arXiv:1908.05628
(2019), arXiv:1908.05628 [quant-ph] .
[38] N. D. Roussopoulos, Information Processing Let-
ters 2, 108 (1973).
[39] P. G. H. Lehot, J. ACM 21, 569 (1974).
[40] D. G. Degiorgi and K. Simon, in Graph-Theoretic
Concepts in Computer Science (Springer Berlin
Heidelberg, Berlin, Heidelberg, 1995) pp. 37–48.
[41] A. J. Kollár, M. Fitzpatrick, and A. A. Houck,
Nature 571, 45 (2019).
[42] A. J. Kollár, M. Fitzpatrick, P. Sarnak, and
A. A. Houck, Communications in Mathematical
Physics , online only (2019).
[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] .
[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).
[45] H. Whitney, American Journal of Mathematics
54, 150 (1932).
[46] D. M. Goodmanson, American Journal of Physics
64, 870 (1996).
[47] L. W. Beineke, Journal of Combinatorial Theory
9, 129 (1970).
[48] Ľ. Šoltés, Discrete Mathematics 132, 391 (1994).
[49] Y. Yang, J. Lin, and C. Wang, Discrete Mathe-
matics 252, 287 (2002).
[50] P. Erdős, A. W. Goodman, and L. Pósa, Cana-
dian Journal of Mathematics 18, 106 (1966).
[51] F. Harary, Graph Theory, Addison Wesley series
in mathematics (Addison-Wesley, 1971).
[52] J. Krausz, Matematikai és Fizikai Lapok 50
(1943).
[53] A. Bednarek, Discrete Mathematics 56, 83
(1985).
[54] M. Suchara, S. Bravyi, and B. Terhal, Journal
of Physics A: Mathematical and Theoretical 44,
155301 (2011).
[55] H. Bombín, New Journal of Physics 18, 043038
(2016).
[56] H. Bombín, Phys. Rev. X 5, 031043 (2015).
[57] A. Kubica and M. E. Beverland, Phys. Rev. A
91, 032330 (2015).
[58] H. Bombín, New Journal of Physics 17, 083002
(2015).
[59] B. J. Brown, N. H. Nickerson, and D. E. Browne,
Nature Communications 7, 12302 (2016).
[60] A. Y. Kitaev, Physics-Uspekhi 44, 131 (2001).
[61] J. Klassen and B. M. Terhal, Quantum 3, 139
(2019).
[62] P. Fendley, Journal of Physics A: Mathematical
and Theoretical 52, 335002 (2019).
[63] S. B. Bravyi and A. Y. Kitaev, Ann. Phys. (N.
Y.) 298, 210 (2002).
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 19