Complexity of graph-state preparation by Clifford circuits

Soh Kumabe; Ryuhei Mori; Yusei Yoshimura

doi:10.22331/q-2026-07-18-2165

Complexity of graph-state preparation by Clifford circuits

Soh Kumabe¹, Ryuhei Mori², and Yusei Yoshimura³

¹CyberAgent, Japan
²Graduate School of Mathematics, Nagoya University, Japan
³School of Computing, The Institute of Science Tokyo, Japan

Published:	2026-07-18, volume 10, page 2165
Editor:	Miriam Backens
Eprint:	arXiv:2402.05874v4
Doi:	https://doi.org/10.22331/q-2026-07-18-2165
Citation:	Quantum 10, 2165 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state $|G\rangle$ as the minimum number of two-qubit Clifford operations required to generate $|G\rangle$ from $|0\rangle^{\otimes (n+s)}$ for some $s\ge 0$. Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, $|G\rangle$ can be generated from another graph state $|H\rangle$ by an algorithm of CZ-complexity at most $t$ if and only if $G$ can be obtained from $H$ by vertex deletions, local complementations and at most $t$ elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph $G$ with $n$ vertices and rank-width $r$, the CZ-complexity is $O(rn)$, and if $G$ is connected then it is at least $n+r-2$. We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity $O(n)$ and $O(n\log n)$, respectively.

► BibTeX data

@article{Kumabe2026complexityofgraph,
  doi = {10.22331/q-2026-07-18-2165},
  url = {https://doi.org/10.22331/q-2026-07-18-2165},
  title = {Complexity of graph-state preparation by {C}lifford circuits},
  author = {Kumabe, Soh and Mori, Ryuhei and Yoshimura, Yusei},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2165},
  month = jul,
  year = {2026}
}

► References

[1] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. ``Graphical description of the action of local Clifford transformations on graph states''. Phys. Rev. A 69, 022316 (2004).
https://doi.org/10.1103/PhysRevA.69.022316

[2] Wolfgang Dür, Hans Aschauer, and Hans J. Briegel. ``Multiparticle entanglement purification for graph states''. Phys. Rev. Lett. 91, 107903 (2003).
https://doi.org/10.1103/PhysRevLett.91.107903

[3] Marc Hein, Jens Eisert, and Hans J. Briegel. ``Multiparty entanglement in graph states''. Phys. Rev. A 69, 062311 (2004).
https://doi.org/10.1103/PhysRevA.69.062311

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

[5] Maarten Van den Nest, Wolfgang Dür, Guifré Vidal, and Hans J. Briegel. ``Classical simulation versus universality in measurement-based quantum computation''. Phys. Rev. A 75, 012337 (2007).
https://doi.org/10.1103/PhysRevA.75.012337

[6] Sergey Bravyi and Robert Raussendorf. ``Measurement-based quantum computation with the toric code states''. Phys. Rev. A 76, 022304 (2007).
https://doi.org/10.1103/PhysRevA.76.022304

[7] Brent Harrison, Vishnu Iyer, Ojas Parekh, Kevin Thompson, and Andrew Zhao. ``Fermionic insights into measurement-based quantum computation: Circle graph states are not universal resources'' (2025). arXiv:2510.05557.
arXiv:2510.05557

[8] Frederik Hahn, Rose McCarty, Hendrik Poulsen Nautrup, and Nathan Claudet. ``The structure of circle graph states'' (2026). arXiv:2603.08847.
arXiv:2603.08847

[9] Matthew B. Elliott, Bryan Eastin, and Carlton M. Caves. ``Graphical description of the action of Clifford operators on stabilizer states''. Phys. Rev. A 77, 042307 (2008).
https://doi.org/10.1103/PhysRevA.77.042307

[10] Axel Dahlberg and Stephanie Wehner. ``Transforming graph states using single-qubit operations''. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 376, 20170325 (2018).
https://doi.org/10.1098/rsta.2017.0325

[11] Jeremy C. Adcock, Sam Morley-Short, Axel Dahlberg, and Joshua W. Silverstone. ``Mapping graph state orbits under local complementation''. Quantum 4, 305 (2020).
https://doi.org/10.22331/q-2020-08-07-305

[12] Nathan Claudet and Simon Perdrix. ``Local equivalence of stabilizer states: A graphical characterisation''. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025).
https://doi.org/10.4230/LIPIcs.STACS.2025.27

[13] Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida, and José R. Portillo. ``Optimal preparation of graph states''. Phys. Rev. A 83, 042314 (2011).
https://doi.org/10.1103/PhysRevA.83.042314

[14] Hemant Sharma, Kenneth Goodenough, Johannes Borregaard, Filip Rozpędek, and Jonas Helsen. ``Minimising the number of edges in LC-equivalent graph states''. Quantum 10, 2001 (2026).
https://doi.org/10.22331/q-2026-02-09-2001

[15] Zhengfeng Ji, Jianxin Chen, Zhaohui Wei, and Mingsheng Ying. ``The LU-LC conjecture is false''. Quantum Information and Computation 10, 97–108 (2010).
https://doi.org/10.26421/QIC10.1-2-8

[16] Ketan N. Patel, Igor L. Markov, and John P. Hayes. ``Optimal synthesis of linear reversible circuits''. Quantum Information and Computation 8, 0282–0294 (2008).
https://doi.org/10.26421/QIC8.3-4-4

[17] Sang-il Oum and Paul Seymour. ``Approximating clique-width and branch-width''. Journal of Combinatorial Theory, Series B 96, 514–528 (2006).
https://doi.org/10.1016/j.jctb.2005.10.006

[18] Sang-il Oum. ``Rank-width: Algorithmic and structural results''. Discrete Applied Mathematics 231, 15–24 (2017).
https://doi.org/10.1016/j.dam.2016.08.006

[19] Choongbum Lee, Joonkyung Lee, and Sang-il Oum. ``Rank-width of random graphs''. Journal of Graph Theory 70, 339–347 (2012).
https://doi.org/10.1002/jgt.20620

[20] James Davies and Andrew Jena. ``Preparing graph states forbidding a vertex-minor'' (2025). arXiv:2504.00291.
arXiv:2504.00291

[21] Andrew Jena. ``Graph-theoretic techniques for optimizing NISQ algorithms''. PhD thesis. University of Waterloo. (2024). url: https://hdl.handle.net/10012/20343.
https://hdl.handle.net/10012/20343

[22] Donggyu Kim and Sang-il Oum. ``Vertex-minors of graphs: A survey''. Discrete Applied Mathematics 351, 54–73 (2024).
https://doi.org/10.1016/j.dam.2024.03.011

[23] André Bouchet. ``Isotropic systems''. European Journal of Combinatorics 8, 231–244 (1987).
https://doi.org/10.1016/S0195-6698(87)80027-6

[24] André Bouchet. ``Graphic presentations of isotropic systems''. Journal of Combinatorial Theory, Series B 45, 58–76 (1988).
https://doi.org/10.1016/0095-8956(88)90055-X

[25] André Bouchet. ``Connectivity of isotropic systems''. Annals of the New York Academy of Sciences 555, 81–93 (1989).
https://doi.org/10.1111/j.1749-6632.1989.tb22439.x

[26] André Bouchet. ``$\kappa$-transformations, local complementations and switching''. In Geňa Hahn, Gert Sabidussi, and Robert E. Woodrow, editors, Cycles and Rays. Pages 41–50. Springer Netherlands, Dordrecht (1990).
https://doi.org/10.1007/978-94-009-0517-7_5

[27] André Bouchet. ``An efficient algorithm to recognize locally equivalent graphs''. Combinatorica 11, 315–329 (1991).
https://doi.org/10.1007/BF01275668

[28] André Bouchet. ``Recognizing locally equivalent graphs''. Discrete Mathematics 114, 75–86 (1993).
https://doi.org/10.1016/0012-365X(93)90357-Y

[29] André Bouchet. ``Circle graph obstructions''. Journal of Combinatorial Theory, Series B 60, 107–144 (1994).
https://doi.org/10.1006/jctb.1994.1008

[30] Anton Kotzig. ``Eulerian lines in finite $4$-valent graphs and their transformations''. In Theory of Graphs (Proc. Colloq., Tihany, 1966). Pages 219–230. Academic Press, New York-London (1968).

[31] Dmitriĭ G. Fon-Der-Flaass. ``Local complementations of simple and directed graphs''. In Aleksei D. Korshunov, editor, Discrete Analysis and Operations Research. Pages 15–34. Springer Netherlands, Dordrecht (1996).
https://doi.org/10.1007/978-94-009-1606-7_3

[32] André Bouchet. ``Digraph decompositions and Eulerian systems''. SIAM Journal on Algebraic Discrete Methods 8, 323–337 (1987).
https://doi.org/10.1137/0608028

[33] Sang-il Oum. ``Rank-width and vertex-minors''. Journal of Combinatorial Theory, Series B 95, 79–100 (2005).
https://doi.org/10.1016/j.jctb.2005.03.003

[34] Sang-il Oum and Paul Seymour. ``Testing branch-width''. Journal of Combinatorial Theory, Series B 97, 385–393 (2007).
https://doi.org/10.1016/j.jctb.2006.06.006

[35] Sang-il Oum. ``Computing rank-width exactly''. Information Processing Letters 109, 745–748 (2009).
https://doi.org/10.1016/j.ipl.2009.03.018

[36] Bruno Courcelle and Sang-il Oum. ``Vertex-minors, monadic second-order logic, and a conjecture by Seese''. Journal of Combinatorial Theory, Series B 97, 91–126 (2007).
https://doi.org/10.1016/j.jctb.2006.04.003

[37] Fedor V. Fomin and Tuukka Korhonen. ``Fast FPT-approximation of branchwidth''. SIAM Journal on Computing 53, 1085–1131 (2024).
https://doi.org/10.1137/22M153937X

[38] Tuukka Korhonen and Marek Sokołowski. ``Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Pages 1538–1549. STOC 2024. Association for Computing Machinery (2024).
https://doi.org/10.1145/3618260.3649732

[39] Tuukka Korhonen and Sang-il Oum. ``Branch-width of connectivity functions is fixed-parameter tractable'' (2026). arXiv:2601.04756.
arXiv:2601.04756

[40] Peter Høyer, Mehdi Mhalla, and Simon Perdrix. ``Resources required for preparing graph states''. In Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006. Proceedings 17. Pages 638–649. Springer (2006).
https://doi.org/10.1007/11940128_64

[41] Jérôme Javelle, Mehdi Mhalla, and Simon Perdrix. ``On the minimum degree up to local complementation: Bounds and complexity''. In Graph-Theoretic Concepts in Computer Science. Pages 138–147. Springer Berlin Heidelberg (2012).
https://doi.org/10.1007/978-3-642-34611-8_16

[42] David Cattanéo and Simon Perdrix. ``Minimum degree up to local complementation: Bounds, parameterized complexity, and exact algorithms''. In Algorithms and Computation. Pages 259–270. Springer Berlin Heidelberg (2015).
https://doi.org/10.1007/978-3-662-48971-0_23

[43] Nathan Claudet and Simon Perdrix. ``Covering a graph with minimal local sets''. In Graph-Theoretic Concepts in Computer Science. Pages 136–150. Springer Nature Switzerland (2025).
https://doi.org/10.1007/978-3-031-75409-8_10

[44] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997). arXiv:quant-ph/9705052.
arXiv:quant-ph/9705052

[45] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. ``How to transform graph states using single-qubit operations: Computational complexity and algorithms''. Quantum Science and Technology 5, 045016 (2020).
https://doi.org/10.1088/2058-9565/aba763

[46] Martin C. Golumbic and Udi Rotics. ``On the clique-width of some perfect graph classes''. International Journal of Foundations of Computer Science 11, 423–443 (2000).
https://doi.org/10.1142/S0129054100000260

[47] Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan. ``The grid theorem for vertex-minors''. Journal of Combinatorial Theory, Series B 158, 93–116 (2023).
https://doi.org/10.1016/j.jctb.2020.08.004

[48] Norman Biggs. ``Algebraic graph theory''. Cambridge Mathematical Library. Cambridge University Press. (1993). 2nd edition.
https://doi.org/10.1017/CBO9780511608704

[49] Hubert de Fraysseix and Patrice Ossona de Mendez. ``On a characterization of Gauss codes''. Discrete & Computational Geometry 22, 287–295 (1999).
https://doi.org/10.1007/PL00009461

[50] Sergey Bravyi, Joseph A. Latone, and Dmitri Maslov. ``6-qubit optimal Clifford circuits''. npj Quantum Information 8, 79 (2022).
https://doi.org/10.1038/s41534-022-00583-7

[51] Lars Eirik Danielsen and Matthew G. Parker. ``On the classification of all self-dual additive codes over $\mathrm{GF}(4)$ of length up to 12''. Journal of Combinatorial Theory, Series A 113, 1351–1367 (2006).
https://doi.org/10.1016/j.jcta.2005.12.004

[52] Lars Eirik Danielsen. ``Graph-based classification of self-dual additive codes over finite fields''. Advances in Mathematics of Communications 3, 329–348 (2009).
https://doi.org/10.3934/amc.2009.3.329

[53] Eric M. Rains and Neil J.A. Sloane. ``Self-dual codes'' (2002). arXiv:math/0208001.
arXiv:math/0208001

[54] Gabriele Nebe, Eric M. Rains, and Neil J.A. Sloane. ``Self-dual codes and invariant theory''. Springer. (2006).
https://doi.org/10.1007/3-540-30731-1

[55] Mithilesh Kumar, Srimathi Varadharajan, and Håvard Raddum. ``Graphs and self-dual additive codes over $\mathrm{GF}(4)$''. In Proc. The Eleventh International Workshop on Coding and Cryptography (WCC 2019). (2019). url: https://www.lebesgue.fr/sites/default/files/proceedings_WCC/WCC_2019_paper_24.pdf.
https://www.lebesgue.fr/sites/default/files/proceedings_WCC/WCC_2019_paper_24.pdf

Cited by

[1] Julia Freund, Alexander Pirker, Lina Vandré, and Wolfgang Dür, "Graph state extraction from two-dimensional cluster states", New Journal of Physics 27 9, 094505 (2025).

[2] Eric Chitambar, Kenneth Goodenough, Otfried Gühne, Rose McCarty, Simon Perdrix, Vito Scarola, Shuo Sun, and Quntao Zhang, "Quantum Graph States: Bridging Classical Theory and Quantum Innovation, Workshop Summary", arXiv:2508.04823, (2025).

[3] Matthias C. Löbl, Love A. Pettersson, Andrew Jena, Luca Dellantonio, Stefano Paesani, and Anders S. Sørensen, "Generating graph states with a single quantum emitter and the minimum number of fusions", Physical Review A 111 5, 052604 (2025).

[4] William Cashman, Giovanni de Felice, and Aleks Kissinger, "Finding trail covers: near-optimal decompositions of graph states as linear fusion networks", arXiv:2508.18375, (2025).

[5] Hemant Sharma, Kenneth Goodenough, Johannes Borregaard, Filip Rozpędek, and Jonas Helsen, "Minimising the number of edges in LC-equivalent graph states", arXiv:2506.00292, (2025).

[6] James Brown, Jason Iaconis, Yuri Alexeev, Linta Joseph, Spencer Churchill, Kenny Heitritter, William Aguilar-Calvo, Martin Roetteler, and Martin Suchara, "Mid-Circuit Measurements for Clifford Noise Reduction in Hamiltonian Simulations", arXiv:2605.06792, (2026).

[7] Konstantinos-Rafail Revis, Hrachya Zakaryan, and Zahra Raissi, "Orbit classification and analysis of qutrit graph states under local complementation and local scaling", arXiv:2506.05478, (2025).

[8] Nicholas Connolly, Shin Nishio, and Kae Nemoto, "Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions", arXiv:2602.23825, (2026).

[9] James Davies and Andrew Jena, "Preparing graph states forbidding a vertex-minor", arXiv:2504.00291, (2025).

[10] Nathan Claudet, "Local Equivalences of Graph States", arXiv:2511.22271, (2025).

[11] Michael Doherty, Matteo Puviani, Jasmine Brewer, Gabriel Matos, David Amaro, Ben Criger, and David T. Stephen, "Fast stabilizer state preparation via AI-optimized graph decimation", arXiv:2603.17743, (2026).

[12] Hemant Sharma, Kenneth Goodenough, Johannes Borregaard, Filip Rozpędek, and Jonas Helsen, "Minimising the number of edges in LC-equivalent graph states", Quantum 10, 2001 (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-07-18 14:15:50). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2026-07-18 14:15:49: Could not fetch cited-by data for 10.22331/q-2026-07-18-2165 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.