Minimising the number of edges in LC-equivalent graph states
Summarize this article with:
AbstractGraph states are a powerful class of entangled states with numerous applications in quantum communication and quantum computation. Local Clifford (LC) operations that map one graph state to another can alter the structure of the corresponding graphs, including changing the number of edges. Here, we tackle the associated edge-minimisation problem: finding graphs with the minimum number of edges in the LC-equivalence class of a given graph. Such graphs are called minimum edge representatives (MER) and are crucial for minimising the resources required to create a graph state. We leverage Bouchet's algebraic formulation of LC-equivalence to encode the edge-minimisation problem as an integer linear program (EDM-ILP). We further propose a simulated annealing (EDM-SA) approach guided by the local clustering coefficient for edge minimisation. We identify new MERs for graph states with up to 16 qubits by combining EDM-SA and EDM-ILP. We extend the ILP to weighted-edge minimisation, where each edge has an associated weight, and prove that this problem is NP-complete. Finally, we employ our tools to minimise the resources required to create all-photonic generalised repeater graph states using fusion operations.Featured image: An example of how edge-minimisation works. Both graph states are local Clifford equivalent.Popular summaryOur algorithms for edge-minimisation find LC-equivalent graph states (locally equivalent graphs) that have minimum number of edges to a given graph state. This allows for the simplification of the required graph, which can be leveraged to save resources required for graph state creation.► BibTeX data@article{Sharma2026minimisingnumberof, doi = {10.22331/q-2026-02-09-2001}, url = {https://doi.org/10.22331/q-2026-02-09-2001}, title = {Minimising the number of edges in {LC}-equivalent graph states}, author = {Sharma, Hemant and Goodenough, Kenneth and Borregaard, Johannes and Rozp{\k{e}}dek, Filip and Helsen, Jonas}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2001}, month = feb, year = {2026} }► References [1] M. Hein, J. Eisert, and H. J. Briegel. ``Multiparty entanglement in graph states''. Phys. Rev. A 69, 062311 (2004). https://doi.org/10.1103/PhysRevA.69.062311 [2] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, Maarten Van den Nest, and H-J Briegel. ``Entanglement in graph states and its applications''. In Quantum computers, algorithms and chaos. Pages 115–218. IOS Press (2006). https://doi.org/10.48550/arXiv.quant-ph/0602096 arXiv:quant-ph/0602096 [3] Robert Raussendorf and Hans J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188–5191 (2001). https://doi.org/10.1103/PhysRevLett.86.5188 [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] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest. ``Measurement-based quantum computation''. Nature Physics 5, 19–26 (2009). https://doi.org/10.1038/nphys1157 [6] Thierry N Kaldenbach and Matthias Heller. ``Mapping quantum circuits to shallow-depth measurement patterns based on graph states''. Quantum Science and Technology 10, 015010 (2024). https://doi.org/10.1088/2058-9565/ad802b [7] Madhav Krishnan Vijayan, Alexandru Paler, Jason Gavriel, Casey R Myers, Peter P Rohde, and Simon J Devitt. ``Compilation of algorithm-specific graph states for quantum circuits''. Quantum Science and Technology 9, 025005 (2024). https://doi.org/10.1088/2058-9565/ad1f39 [8] Thierry N. Kaldenbach, Isaac D. Smith, Hendrik Poulsen Nautrup, Matthias Heller, and Hans J. Briegel. ``Efficient preparation of resource states for hamiltonian simulation and universal quantum computation'' (2025). arXiv:2509.05404. arXiv:2509.05404 [9] Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo. ``All-photonic quantum repeaters''. Nature Communications 6 (2015). https://doi.org/10.1038/ncomms7787 [10] Mihir Pant, Hari Krovi, Dirk Englund, and Saikat Guha. ``Rate-distance tradeoff and resource costs for all-optical quantum repeaters''. Phys. Rev. A 95, 012304 (2017). https://doi.org/10.1103/PhysRevA.95.012304 [11] Filip Rozpędek, Kaushik P. Seshadreesan, Paul Polakos, Liang Jiang, and Saikat Guha. ``All-photonic gottesman-kitaev-preskill–qubit repeater using analog-information-assisted multiplexed entanglement ranking''. Phys. Rev. Res. 5, 043056 (2023). https://doi.org/10.1103/PhysRevResearch.5.043056 [12] Eneet Kaur, Ashlesha Patil, and Saikat Guha. ``Resource-efficient loss-aware photonic-graph-state preparation using atomic emitters''. Phys. Rev. A 112, 062608 (2025). https://doi.org/10.1103/2cbn-448l [13] Ashlesha Patil and Saikat Guha. ``An improved design for all-photonic quantum repeaters'' (2024). arXiv:2405.11768. arXiv:2405.11768 [14] Bikun Li, Kenneth Goodenough, Filip Rozpędek, and Liang Jiang. ``Generalized quantum repeater graph states''. Phys. Rev. Lett. 134, 190801 (2025). https://doi.org/10.1103/PhysRevLett.134.190801 [15] Johannes Borregaard, Hannes Pichler, Tim Schröder, Mikhail D. Lukin, Peter Lodahl, and Anders S. Sørensen. ``One-way quantum repeater based on near-deterministic photon-emitter interfaces''. Phys. Rev. X 10, 021071 (2020). https://doi.org/10.1103/PhysRevX.10.021071 [16] Thomas J. Bell, Love A. Pettersson, and Stefano Paesani. ``Optimizing graph codes for measurement-based loss tolerance''. PRX Quantum 4, 020328 (2023). https://doi.org/10.1103/PRXQuantum.4.020328 [17] Ashlesha Patil and Saikat Guha. ``Tree cluster state generation using percolation''.
In Optica Quantum 2.0 Conference and Exhibition. Page QTh4A.3. QUANTUM.
Optica Publishing Group (2023). https://doi.org/10.1364/quantum.2023.qth4a.3 [18] Nathan Shettell and Damian Markham. ``Graph states as a resource for quantum metrology''. Phys. Rev. Lett. 124, 110502 (2020). https://doi.org/10.1103/PhysRevLett.124.110502 [19] I. Schwartz, D. Cogan, E. R. Schmidgall, Y. Don, L. Gantz, O. Kenneth, N. H. Lindner, and D. Gershoni. ``Deterministic generation of a cluster state of entangled photons''. Science 354, 434–437 (2016). https://doi.org/10.1126/science.aah4758 [20] Mikkel V. Larsen, Xueshi Guo, Casper R. Breum, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen. ``Deterministic generation of a two-dimensional cluster state''. Science 366, 369–372 (2019). https://doi.org/10.1126/science.aay4354 [21] Warit Asavanant, Yu Shiozawa, Shota Yokoyama, Baramee Charoensombutamon, Hiroki Emura, Rafael N. Alexander, Shuntaro Takeda, Jun ichi Yoshikawa, Nicolas C. Menicucci, Hidehiro Yonezawa, and Akira Furusawa. ``Generation of time-domain-multiplexed two-dimensional cluster state''. Science 366, 373–376 (2019). https://doi.org/10.1126/science.aay2645 [22] D. Istrati, Y. Pilnyak, J. C. Loredo, C. Antón, N. Somaschi, P. Hilaire, H. Ollivier, M. Esmann, L. Cohen, L. Vidro, C. Millet, A. Lemaître, I. Sagnes, A. Harouri, L. Lanco, P. Senellart, and H. S. Eisenberg. ``Sequential generation of linear cluster states from a single photon emitter''. Nature Communications 11 (2020). https://doi.org/10.1038/s41467-020-19341-4 [23] Philip Thomas, Leonardo Ruscio, Olivier Morin, and Gerhard Rempe. ``Efficient generation of entangled multiphoton graph states from a single atom''. Nature 608, 677–681 (2022). https://doi.org/10.1038/s41586-022-04987-5 [24] Chan Roh, Geunhee Gwak, Young-Do Yoon, and Young-Sik Ra. ``Generation of three-dimensional cluster entangled state''. Nature Photonics 19, 526–532 (2025). https://doi.org/10.1038/s41566-025-01631-2 [25] Sirui Cao, Bujiao Wu, Fusheng Chen, et al. ``Generation of genuine entanglement up to 51 superconducting qubits''. Nature 619, 738–742 (2023). https://doi.org/10.1038/s41586-023-06195-1 [26] James O’Sullivan, Kevin Reuer, et al. ``Deterministic generation of two-dimensional multi-photon cluster states''. Nature Communications 16 (2025). https://doi.org/10.1038/s41467-025-60472-3 [27] Vinicius S Ferreira, Gihwan Kim, Andreas Butler, Hannes Pichler, and Oskar Painter. ``Deterministic generation of multidimensional photonic cluster states with a single quantum emitter''. Nature Physics 20, 865–870 (2024). https://doi.org/10.1038/s41567-024-02408-0 [28] Philip Thomas, Leonardo Ruscio, Olivier Morin, and Gerhard Rempe. ``Fusion of deterministically generated photonic graph states''. Nature 629, 567–572 (2024). https://doi.org/10.1038/s41586-024-07357-5 [29] Bikun Li, Sophia E. Economou, and Edwin Barnes. ``Photonic resource state generation from a minimal number of quantum emitters''. npj Quantum Information 8 (2022). https://doi.org/10.1038/s41534-022-00522-6 [30] Evangelia Takou, Edwin Barnes, and Sophia E Economou. ``Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols''. npj Quantum Information 11, 108 (2025). https://doi.org/10.1038/s41534-025-01056-3 [31] Seok-Hyung Lee and Hyunseok Jeong. ``Graph-theoretical optimization of fusion-based graph state generation''. Quantum 7, 1212 (2023). https://doi.org/10.22331/q-2023-12-20-1212 [32] Yingheng Li, Yue Dai, Aditya Pawar, Rongchao Dong, Jun Yang, Youtao Zhang, and Xulong Tang. ``Reinforcement learning-guided graph state generation in photonic quantum computers''. In Proceedings of the 52nd Annual International Symposium on Computer Architecture. Page 1598–1612. SIGARCH ’25. ACM (2025). https://doi.org/10.1145/3695053.3731085 [33] Daniel Bhatti and Kenneth Goodenough. ``Distributing graph states with a photon-weaving quantum server'' (2025). arXiv:2504.07410. arXiv:2504.07410 [34] 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 [35] Tingxiang Ji, Jianqing Liu, and Zheshen Zhang. ``Distributing arbitrary quantum graph states by graph transformation'' (2025). arXiv:2404.05537. arXiv:2404.05537 [36] 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 [37] 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 [38] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. ``Optimization by simulated annealing''. Science 220, 671–680 (1983). https://doi.org/10.1126/science.220.4598.671 [39] André Bouchet. ``An efficient algorithm to recognize locally equivalent graphs''. Combinatorica 11, 315–329 (1991). https://doi.org/10.1007/BF01275668 [40] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. ``The complexity of the vertex-minor problem''.
Information Processing Letters 175, 106222 (2022). https://doi.org/10.1016/j.ipl.2021.106222 [41] Daniel E. Browne and Terry Rudolph. ``Resource-efficient linear optical quantum computation''. Phys. Rev. Lett. 95, 010501 (2005). https://doi.org/10.1103/PhysRevLett.95.010501 [42] Duncan J Watts and Steven H Strogatz. ``Collective dynamics of `small-world' networks''. Nature 393, 440–442 (1998). https://doi.org/10.1038/30918 [43] Bruce Hajek. ``Cooling schedules for optimal annealing''. Page 147–150.
Springer New York. (1987). https://doi.org/10.1007/978-1-4612-4808-8_42 [44] Jeroen Dehaene, Maarten Van den Nest, Bart De Moor, and Frank Verstraete. ``Local permutations of products of bell states and entanglement distillation''. Phys. Rev. A 67, 022310 (2003). https://doi.org/10.1103/PhysRevA.67.022310 [45] Jeroen Dehaene and Bart De Moor. ``Clifford group, stabilizer states, and linear and quadratic operations over gf(2)''. Phys. Rev. A 68, 042318 (2003). https://doi.org/10.1103/PhysRevA.68.042318 [46] MOSEK ApS. ``Mosek optimizer api for python 10.2.1''. (2024). url: https://docs.mosek.com/latest/pythonapi/index.html. https://docs.mosek.com/latest/pythonapi/index.html [47] Simon Anders, Hans J Briegel, and Wolfgang Dür. ``A variational method based on weighted graph states''. New Journal of Physics 9, 361–361 (2007). https://doi.org/10.1088/1367-2630/9/10/361 [48] L Hartmann, J Calsamiglia, W Dür, and H J Briegel. ``Weighted graph states and applications to spin chains, lattices and gases''. Journal of Physics B: Atomic, Molecular and Optical Physics 40, S1 (2007). https://doi.org/10.1088/0953-4075/40/9/S01 [49] 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 [50] 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 [51] 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 [52] P. Erdős and A. Rényi. ``On random graphs. i.''.
Publicationes Mathematicae Debrecen 6, 290–297 (2022). https://doi.org/10.5486/pmd.1959.6.3-4.12 [53] E. N. Gilbert. ``Random graphs''. The Annals of Mathematical Statistics 30, 1141–1144 (1959). https://doi.org/10.1214/aoms/1177706098 [54] S. L. Hakimi. ``On realizability of a set of integers as degrees of the vertices of a linear graph. i''. Journal of the Society for Industrial and Applied Mathematics 10, 496–506 (1962). https://doi.org/10.1137/0110037 [55] Václav Havel. ``A remark on the existence of finite graphs''. Časopis pro pěstování matematiky 080, 477–480 (1955). https://doi.org/10.21136/cpm.1955.108220 [56] Donovan Buterakos, Edwin Barnes, and Sophia E. Economou. ``Deterministic generation of all-photonic quantum repeaters from solid-state emitters''. Phys. Rev. X 7, 041023 (2017). https://doi.org/10.1103/PhysRevX.7.041023 [57] Yuan Zhan, Paul Hilaire, Edwin Barnes, Sophia E. Economou, and Shuo Sun. ``Performance analysis of quantum repeaters enabled by deterministically generated photonic graph states''. Quantum 7, 924 (2023). https://doi.org/10.22331/q-2023-02-16-924 [58] Michael Varnava, Daniel E. Browne, and Terry Rudolph. ``How good must single photon sources and detectors be for efficient linear optical quantum computation?''. Phys. Rev. Lett. 100, 060502 (2008). https://doi.org/10.1103/PhysRevLett.100.060502 [59] Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura. ``Complexity of graph-state preparation by clifford circuits'' (2025). arXiv:2402.05874. arXiv:2402.05874 [60] Andrew Jena. ``Graph-theoretic techniques for optimizing nisq algorithms'' (2024). [61] James Davies and Andrew Jena. ``Preparing graph states forbidding a vertex-minor'' (2025). arXiv:2504.00291. arXiv:2504.00291 [62] Z.-F. Ji, J.-X. Chen, Z.-H. Wei, and M.-S. Ying. ``The lu-lc conjecture is false''. Quantum Information and Computation 10, 97–108 (2010). https://doi.org/10.26421/qic10.1-2-8 [63] Adam Burchardt, Jarn de Jong, and Lina Vandré. ``Algorithm to verify local equivalence of stabilizer states'' (2025). arXiv:2410.03961. arXiv:2410.03961 [64] 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. Dagstuhl, Germany (2025). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2025.27 [65] Nathan Claudet and Simon Perdrix. ``Deciding local unitary equivalence of graph states in quasi-polynomial time''. In LIPIcs, Volume 334, ICALP 2025. Volume 334, pages 59:1–59:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025). https://doi.org/10.4230/LIPICS.ICALP.2025.59 [66] Hemant Sharma. ``Release 1.0.1: graph_state_optimization''. https://doi.org/10.5281/zenodo.15534878 (2025). https://doi.org/10.5281/zenodo.15534878 [67] Hemant Sharma. ``Data accompanying graph_state_optimization. this includes the sampled graphs and mers corresponding to those graphs.''. https://doi.org/10.5281/zenodo.15534839 (2025). https://doi.org/10.5281/zenodo.15534839 [68] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. ``Efficient algorithm to recognize the local clifford equivalence of graph states''. Phys. Rev. A 70, 034302 (2004). https://doi.org/10.1103/PhysRevA.70.034302 [69] Sobhan Ghanbari, Jie Lin, Benjamin MacLellan, Luc Robichaud, Piotr Roztocki, and Hoi-Kwong Lo. ``Optimization of deterministic photonic-graph-state generation via local operations''. Phys. Rev. A 110, 052605 (2024). https://doi.org/10.1103/PhysRevA.110.052605Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-09 11:43:45: Could not fetch cited-by data for 10.22331/q-2026-02-09-2001 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-09 11:43:46: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractGraph states are a powerful class of entangled states with numerous applications in quantum communication and quantum computation. Local Clifford (LC) operations that map one graph state to another can alter the structure of the corresponding graphs, including changing the number of edges. Here, we tackle the associated edge-minimisation problem: finding graphs with the minimum number of edges in the LC-equivalence class of a given graph. Such graphs are called minimum edge representatives (MER) and are crucial for minimising the resources required to create a graph state. We leverage Bouchet's algebraic formulation of LC-equivalence to encode the edge-minimisation problem as an integer linear program (EDM-ILP). We further propose a simulated annealing (EDM-SA) approach guided by the local clustering coefficient for edge minimisation. We identify new MERs for graph states with up to 16 qubits by combining EDM-SA and EDM-ILP. We extend the ILP to weighted-edge minimisation, where each edge has an associated weight, and prove that this problem is NP-complete. Finally, we employ our tools to minimise the resources required to create all-photonic generalised repeater graph states using fusion operations.Featured image: An example of how edge-minimisation works. Both graph states are local Clifford equivalent.Popular summaryOur algorithms for edge-minimisation find LC-equivalent graph states (locally equivalent graphs) that have minimum number of edges to a given graph state. This allows for the simplification of the required graph, which can be leveraged to save resources required for graph state creation.► BibTeX data@article{Sharma2026minimisingnumberof, doi = {10.22331/q-2026-02-09-2001}, url = {https://doi.org/10.22331/q-2026-02-09-2001}, title = {Minimising the number of edges in {LC}-equivalent graph states}, author = {Sharma, Hemant and Goodenough, Kenneth and Borregaard, Johannes and Rozp{\k{e}}dek, Filip and Helsen, Jonas}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2001}, month = feb, year = {2026} }► References [1] M. Hein, J. Eisert, and H. J. Briegel. ``Multiparty entanglement in graph states''. Phys. Rev. A 69, 062311 (2004). https://doi.org/10.1103/PhysRevA.69.062311 [2] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, Maarten Van den Nest, and H-J Briegel. ``Entanglement in graph states and its applications''. In Quantum computers, algorithms and chaos. Pages 115–218. IOS Press (2006). https://doi.org/10.48550/arXiv.quant-ph/0602096 arXiv:quant-ph/0602096 [3] Robert Raussendorf and Hans J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188–5191 (2001). https://doi.org/10.1103/PhysRevLett.86.5188 [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] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest. ``Measurement-based quantum computation''. Nature Physics 5, 19–26 (2009). https://doi.org/10.1038/nphys1157 [6] Thierry N Kaldenbach and Matthias Heller. ``Mapping quantum circuits to shallow-depth measurement patterns based on graph states''. Quantum Science and Technology 10, 015010 (2024). https://doi.org/10.1088/2058-9565/ad802b [7] Madhav Krishnan Vijayan, Alexandru Paler, Jason Gavriel, Casey R Myers, Peter P Rohde, and Simon J Devitt. ``Compilation of algorithm-specific graph states for quantum circuits''. Quantum Science and Technology 9, 025005 (2024). https://doi.org/10.1088/2058-9565/ad1f39 [8] Thierry N. Kaldenbach, Isaac D. Smith, Hendrik Poulsen Nautrup, Matthias Heller, and Hans J. Briegel. ``Efficient preparation of resource states for hamiltonian simulation and universal quantum computation'' (2025). arXiv:2509.05404. arXiv:2509.05404 [9] Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo. ``All-photonic quantum repeaters''. Nature Communications 6 (2015). https://doi.org/10.1038/ncomms7787 [10] Mihir Pant, Hari Krovi, Dirk Englund, and Saikat Guha. ``Rate-distance tradeoff and resource costs for all-optical quantum repeaters''. Phys. Rev. A 95, 012304 (2017). https://doi.org/10.1103/PhysRevA.95.012304 [11] Filip Rozpędek, Kaushik P. Seshadreesan, Paul Polakos, Liang Jiang, and Saikat Guha. ``All-photonic gottesman-kitaev-preskill–qubit repeater using analog-information-assisted multiplexed entanglement ranking''. Phys. Rev. Res. 5, 043056 (2023). https://doi.org/10.1103/PhysRevResearch.5.043056 [12] Eneet Kaur, Ashlesha Patil, and Saikat Guha. ``Resource-efficient loss-aware photonic-graph-state preparation using atomic emitters''. Phys. Rev. A 112, 062608 (2025). https://doi.org/10.1103/2cbn-448l [13] Ashlesha Patil and Saikat Guha. ``An improved design for all-photonic quantum repeaters'' (2024). arXiv:2405.11768. arXiv:2405.11768 [14] Bikun Li, Kenneth Goodenough, Filip Rozpędek, and Liang Jiang. ``Generalized quantum repeater graph states''. Phys. Rev. Lett. 134, 190801 (2025). https://doi.org/10.1103/PhysRevLett.134.190801 [15] Johannes Borregaard, Hannes Pichler, Tim Schröder, Mikhail D. Lukin, Peter Lodahl, and Anders S. Sørensen. ``One-way quantum repeater based on near-deterministic photon-emitter interfaces''. Phys. Rev. X 10, 021071 (2020). https://doi.org/10.1103/PhysRevX.10.021071 [16] Thomas J. Bell, Love A. Pettersson, and Stefano Paesani. ``Optimizing graph codes for measurement-based loss tolerance''. PRX Quantum 4, 020328 (2023). https://doi.org/10.1103/PRXQuantum.4.020328 [17] Ashlesha Patil and Saikat Guha. ``Tree cluster state generation using percolation''.
In Optica Quantum 2.0 Conference and Exhibition. Page QTh4A.3. QUANTUM.
Optica Publishing Group (2023). https://doi.org/10.1364/quantum.2023.qth4a.3 [18] Nathan Shettell and Damian Markham. ``Graph states as a resource for quantum metrology''. Phys. Rev. Lett. 124, 110502 (2020). https://doi.org/10.1103/PhysRevLett.124.110502 [19] I. Schwartz, D. Cogan, E. R. Schmidgall, Y. Don, L. Gantz, O. Kenneth, N. H. Lindner, and D. Gershoni. ``Deterministic generation of a cluster state of entangled photons''. Science 354, 434–437 (2016). https://doi.org/10.1126/science.aah4758 [20] Mikkel V. Larsen, Xueshi Guo, Casper R. Breum, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen. ``Deterministic generation of a two-dimensional cluster state''. Science 366, 369–372 (2019). https://doi.org/10.1126/science.aay4354 [21] Warit Asavanant, Yu Shiozawa, Shota Yokoyama, Baramee Charoensombutamon, Hiroki Emura, Rafael N. Alexander, Shuntaro Takeda, Jun ichi Yoshikawa, Nicolas C. Menicucci, Hidehiro Yonezawa, and Akira Furusawa. ``Generation of time-domain-multiplexed two-dimensional cluster state''. Science 366, 373–376 (2019). https://doi.org/10.1126/science.aay2645 [22] D. Istrati, Y. Pilnyak, J. C. Loredo, C. Antón, N. Somaschi, P. Hilaire, H. Ollivier, M. Esmann, L. Cohen, L. Vidro, C. Millet, A. Lemaître, I. Sagnes, A. Harouri, L. Lanco, P. Senellart, and H. S. Eisenberg. ``Sequential generation of linear cluster states from a single photon emitter''. Nature Communications 11 (2020). https://doi.org/10.1038/s41467-020-19341-4 [23] Philip Thomas, Leonardo Ruscio, Olivier Morin, and Gerhard Rempe. ``Efficient generation of entangled multiphoton graph states from a single atom''. Nature 608, 677–681 (2022). https://doi.org/10.1038/s41586-022-04987-5 [24] Chan Roh, Geunhee Gwak, Young-Do Yoon, and Young-Sik Ra. ``Generation of three-dimensional cluster entangled state''. Nature Photonics 19, 526–532 (2025). https://doi.org/10.1038/s41566-025-01631-2 [25] Sirui Cao, Bujiao Wu, Fusheng Chen, et al. ``Generation of genuine entanglement up to 51 superconducting qubits''. Nature 619, 738–742 (2023). https://doi.org/10.1038/s41586-023-06195-1 [26] James O’Sullivan, Kevin Reuer, et al. ``Deterministic generation of two-dimensional multi-photon cluster states''. Nature Communications 16 (2025). https://doi.org/10.1038/s41467-025-60472-3 [27] Vinicius S Ferreira, Gihwan Kim, Andreas Butler, Hannes Pichler, and Oskar Painter. ``Deterministic generation of multidimensional photonic cluster states with a single quantum emitter''. Nature Physics 20, 865–870 (2024). https://doi.org/10.1038/s41567-024-02408-0 [28] Philip Thomas, Leonardo Ruscio, Olivier Morin, and Gerhard Rempe. ``Fusion of deterministically generated photonic graph states''. Nature 629, 567–572 (2024). https://doi.org/10.1038/s41586-024-07357-5 [29] Bikun Li, Sophia E. Economou, and Edwin Barnes. ``Photonic resource state generation from a minimal number of quantum emitters''. npj Quantum Information 8 (2022). https://doi.org/10.1038/s41534-022-00522-6 [30] Evangelia Takou, Edwin Barnes, and Sophia E Economou. ``Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols''. npj Quantum Information 11, 108 (2025). https://doi.org/10.1038/s41534-025-01056-3 [31] Seok-Hyung Lee and Hyunseok Jeong. ``Graph-theoretical optimization of fusion-based graph state generation''. Quantum 7, 1212 (2023). https://doi.org/10.22331/q-2023-12-20-1212 [32] Yingheng Li, Yue Dai, Aditya Pawar, Rongchao Dong, Jun Yang, Youtao Zhang, and Xulong Tang. ``Reinforcement learning-guided graph state generation in photonic quantum computers''. In Proceedings of the 52nd Annual International Symposium on Computer Architecture. Page 1598–1612. SIGARCH ’25. ACM (2025). https://doi.org/10.1145/3695053.3731085 [33] Daniel Bhatti and Kenneth Goodenough. ``Distributing graph states with a photon-weaving quantum server'' (2025). arXiv:2504.07410. arXiv:2504.07410 [34] 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 [35] Tingxiang Ji, Jianqing Liu, and Zheshen Zhang. ``Distributing arbitrary quantum graph states by graph transformation'' (2025). arXiv:2404.05537. arXiv:2404.05537 [36] 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 [37] 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 [38] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. ``Optimization by simulated annealing''. Science 220, 671–680 (1983). https://doi.org/10.1126/science.220.4598.671 [39] André Bouchet. ``An efficient algorithm to recognize locally equivalent graphs''. Combinatorica 11, 315–329 (1991). https://doi.org/10.1007/BF01275668 [40] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. ``The complexity of the vertex-minor problem''.
Information Processing Letters 175, 106222 (2022). https://doi.org/10.1016/j.ipl.2021.106222 [41] Daniel E. Browne and Terry Rudolph. ``Resource-efficient linear optical quantum computation''. Phys. Rev. Lett. 95, 010501 (2005). https://doi.org/10.1103/PhysRevLett.95.010501 [42] Duncan J Watts and Steven H Strogatz. ``Collective dynamics of `small-world' networks''. Nature 393, 440–442 (1998). https://doi.org/10.1038/30918 [43] Bruce Hajek. ``Cooling schedules for optimal annealing''. Page 147–150.
Springer New York. (1987). https://doi.org/10.1007/978-1-4612-4808-8_42 [44] Jeroen Dehaene, Maarten Van den Nest, Bart De Moor, and Frank Verstraete. ``Local permutations of products of bell states and entanglement distillation''. Phys. Rev. A 67, 022310 (2003). https://doi.org/10.1103/PhysRevA.67.022310 [45] Jeroen Dehaene and Bart De Moor. ``Clifford group, stabilizer states, and linear and quadratic operations over gf(2)''. Phys. Rev. A 68, 042318 (2003). https://doi.org/10.1103/PhysRevA.68.042318 [46] MOSEK ApS. ``Mosek optimizer api for python 10.2.1''. (2024). url: https://docs.mosek.com/latest/pythonapi/index.html. https://docs.mosek.com/latest/pythonapi/index.html [47] Simon Anders, Hans J Briegel, and Wolfgang Dür. ``A variational method based on weighted graph states''. New Journal of Physics 9, 361–361 (2007). https://doi.org/10.1088/1367-2630/9/10/361 [48] L Hartmann, J Calsamiglia, W Dür, and H J Briegel. ``Weighted graph states and applications to spin chains, lattices and gases''. Journal of Physics B: Atomic, Molecular and Optical Physics 40, S1 (2007). https://doi.org/10.1088/0953-4075/40/9/S01 [49] 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 [50] 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 [51] 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 [52] P. Erdős and A. Rényi. ``On random graphs. i.''.
Publicationes Mathematicae Debrecen 6, 290–297 (2022). https://doi.org/10.5486/pmd.1959.6.3-4.12 [53] E. N. Gilbert. ``Random graphs''. The Annals of Mathematical Statistics 30, 1141–1144 (1959). https://doi.org/10.1214/aoms/1177706098 [54] S. L. Hakimi. ``On realizability of a set of integers as degrees of the vertices of a linear graph. i''. Journal of the Society for Industrial and Applied Mathematics 10, 496–506 (1962). https://doi.org/10.1137/0110037 [55] Václav Havel. ``A remark on the existence of finite graphs''. Časopis pro pěstování matematiky 080, 477–480 (1955). https://doi.org/10.21136/cpm.1955.108220 [56] Donovan Buterakos, Edwin Barnes, and Sophia E. Economou. ``Deterministic generation of all-photonic quantum repeaters from solid-state emitters''. Phys. Rev. X 7, 041023 (2017). https://doi.org/10.1103/PhysRevX.7.041023 [57] Yuan Zhan, Paul Hilaire, Edwin Barnes, Sophia E. Economou, and Shuo Sun. ``Performance analysis of quantum repeaters enabled by deterministically generated photonic graph states''. Quantum 7, 924 (2023). https://doi.org/10.22331/q-2023-02-16-924 [58] Michael Varnava, Daniel E. Browne, and Terry Rudolph. ``How good must single photon sources and detectors be for efficient linear optical quantum computation?''. Phys. Rev. Lett. 100, 060502 (2008). https://doi.org/10.1103/PhysRevLett.100.060502 [59] Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura. ``Complexity of graph-state preparation by clifford circuits'' (2025). arXiv:2402.05874. arXiv:2402.05874 [60] Andrew Jena. ``Graph-theoretic techniques for optimizing nisq algorithms'' (2024). [61] James Davies and Andrew Jena. ``Preparing graph states forbidding a vertex-minor'' (2025). arXiv:2504.00291. arXiv:2504.00291 [62] Z.-F. Ji, J.-X. Chen, Z.-H. Wei, and M.-S. Ying. ``The lu-lc conjecture is false''. Quantum Information and Computation 10, 97–108 (2010). https://doi.org/10.26421/qic10.1-2-8 [63] Adam Burchardt, Jarn de Jong, and Lina Vandré. ``Algorithm to verify local equivalence of stabilizer states'' (2025). arXiv:2410.03961. arXiv:2410.03961 [64] 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. Dagstuhl, Germany (2025). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2025.27 [65] Nathan Claudet and Simon Perdrix. ``Deciding local unitary equivalence of graph states in quasi-polynomial time''. In LIPIcs, Volume 334, ICALP 2025. Volume 334, pages 59:1–59:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025). https://doi.org/10.4230/LIPICS.ICALP.2025.59 [66] Hemant Sharma. ``Release 1.0.1: graph_state_optimization''. https://doi.org/10.5281/zenodo.15534878 (2025). https://doi.org/10.5281/zenodo.15534878 [67] Hemant Sharma. ``Data accompanying graph_state_optimization. this includes the sampled graphs and mers corresponding to those graphs.''. https://doi.org/10.5281/zenodo.15534839 (2025). https://doi.org/10.5281/zenodo.15534839 [68] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. ``Efficient algorithm to recognize the local clifford equivalence of graph states''. Phys. Rev. A 70, 034302 (2004). https://doi.org/10.1103/PhysRevA.70.034302 [69] Sobhan Ghanbari, Jie Lin, Benjamin MacLellan, Luc Robichaud, Piotr Roztocki, and Hoi-Kwong Lo. ``Optimization of deterministic photonic-graph-state generation via local operations''. Phys. Rev. A 110, 052605 (2024). https://doi.org/10.1103/PhysRevA.110.052605Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-09 11:43:45: Could not fetch cited-by data for 10.22331/q-2026-02-09-2001 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-09 11:43:46: No response from ADS or unable to decode the received json data when getting the list of citing works.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.