Useful entanglement can be extracted from noisy graph states
Summarize this article with:
AbstractCluster states and graph states in general offer a useful model of the stabilizer formalism and a path toward the development of measurement-based quantum computation. Their defining structure – the stabilizer group – encodes all possible correlations that can be observed during measurement. The measurement outcomes which are consistent with the stabilizer structure make error correction possible. Here, we leverage both properties to design feasible families of states that can be used as robust building blocks of quantum computation. This procedure reduces the effect of experimentally relevant noise models on the extraction of smaller entangled states from the larger noisy graph state. In particular, we study the extraction of Bell pairs from linearly extended graph states – this has the immediate consequence for state teleportation across the graph. We show that robust entanglement can be extracted by proper design of the linear graph with only a minimal overhead of the physical qubits. This scenario is relevant to systems in which the entanglement can be created between neighboring sites. The results shown in this work provide a mathematical framework for noise reduction in measurement-based quantum computation. With proper connectivity structures, the effect of noise can be minimized for a large class of realistic noise processes.Featured image: (top left) A simple path graph state can be used to generate a Bell pair via X-basis measurements on internal qubits. (bottom left) Preparation noise, modelled here as a missing edge, breaks the connectivity and destroys the entanglement between the terminal vertices. (right) The "crazy" graph is a robust alternative; dominant noise effects are suppressed and the target Bell pair remains largely untouched even with several missing edges. Popular summaryDistributing entanglement across a chain of qubits is straightforward in principle, but noise can break any single link and ruin the whole thing. Here we show that certain graph structures, notably the "crazy graph", tolerate noise much better than simple path graphs. Their redundant connectivity allows errors to be detected or even corrected automatically during the measurement process. For the crazy graph, the noise sensitivity stays constant no matter how long the chain gets, with only a small overhead in qubit count. This makes them practical candidates for robust entanglement distribution in quantum networks.► BibTeX data@article{Szymanski2026usefulentanglement, doi = {10.22331/q-2026-01-21-1977}, url = {https://doi.org/10.22331/q-2026-01-21-1977}, title = {Useful entanglement can be extracted from noisy graph states}, author = {Szyma{\'{n}}ski, Konrad and Vandr{\'{e}}, Lina and G{\"{u}}hne, Otfried}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1977}, month = jan, year = {2026} }► References [1] R. Raussendorf and H. J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188 (2001). https://doi.org/10.1103/physrevlett.86.5188 [2] M. A. Nielsen. ``Cluster-state quantum computation''. Rep. Math. Phys. 57, 147 (2006). https://doi.org/10.1016/s0034-4877(06)80014-5 [3] E. Muñoz‐Coreas and H. Thapliyal. ``Everything you always wanted to know about quantum circuits'' (2022). Wiley Encyclopedia of Electrical and Electronics Engineering. [4] M. P.A. Fisher, V. Khemani, A. Nahum, and S. Vijay. ``Random quantum circuits''. Annu. Rev. Condens. Matter Phys. 14, 335 (2023). https://doi.org/10.1146/annurev-conmatphys-031720-030658 [5] R. Raussendorf, D. E. Browne, and H. J. Briegel. ``Measurement-based quantum computation on cluster states''. Phys. Rev. A 68, 022312 (2003). https://doi.org/10.1103/PhysRevA.68.022312 [6] M. Rossi, M. Huber, D. Bruß, and C. Macchiavello. ``Quantum hypergraph states''. New J. Phys. 15, 113022 (2013). https://doi.org/10.1088/1367-2630/15/11/113022 [7] M. Hein, W. Dür, J. Eisert, et al. ``Entanglement in graph states and its applications''. arXiv:quant-ph/0602096, Proceedings of the International School of Physics “Enrico Fermi” 162, 115 (2006). https://doi.org/10.3254/978-1-61499-018-5-115 arXiv:quant-ph/0602096 [8] C. Kruszynska and B. Kraus. ``Local entanglability and multipartite entanglement''. Phys. Rev. A 79, 052304 (2009). https://doi.org/10.1103/PhysRevA.79.052304 [9] R. Qu, J. Wang, Z.-S. Li, and Y.-R. Bao. ``Encoding hypergraphs into quantum states''. Phys. Rev. A 87, 022311 (2013). https://doi.org/10.1103/PhysRevA.87.022311 [10] M. Gachechiladze, O. Gühne, and A. Miyake. ``Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states''. Phys. Rev. A 99, 052304 (2019). https://doi.org/10.1103/physreva.99.052304 [11] L. Vandré and O. Gühne. ``Entanglement purification of hypergraph states''. Phys. Rev. A 108, 062417 (2023). https://doi.org/10.1103/PhysRevA.108.062417 [12] F. Hahn, A. Pappa, and J. Eisert. ``Quantum network routing and local complementation''. npj Quantum Inf. 5, 76 (2019). https://doi.org/10.1038/s41534-019-0191-6 [13] V. Mannalath and A. Pathak. ``Multiparty entanglement routing in quantum networks''. Phys. Rev. A 108, 062614 (2023). https://doi.org/10.1103/physreva.108.062614 [14] C. Meignant, D. Markham, and F. Grosshans. ``Distributing graph states over arbitrary quantum networks''. Phys. Rev. A 100, 052333 (2019). https://doi.org/10.1103/physreva.100.052333 [15] A. Sen, K. Goodenough, and D. Towsley. ``Multipartite entanglement in quantum networks using subgraph complementations''. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Volume 02, pages 252–253. (2023). https://doi.org/10.1109/QCE57702.2023.10229 [16] X. Fan, C. Zhan, H. Gupta, and C. R. Ramakrishnan. ``Optimized distribution of entanglement graph states in quantum networks''. IEEE Trans. Quantum Eng. 6, 1 (2025). https://doi.org/10.1109/TQE.2025.3552006 [17] N. Basak and G. Paul. ``Improved routing of multiparty entanglement over quantum networks'' (2024). arXiv:2409.14694. arXiv:2409.14694 [18] C. H. Bennett, G. Brassard, C. Crépeau, et al. ``Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels''. Phys. Rev. Lett. 70, 1895 (1993). https://doi.org/10.1103/PhysRevLett.70.1895 [19] D. Bouwmeester, J.-W. Pan, K. Mattle, et al. ``Experimental quantum teleportation''. Nature 390, 575 (1997). https://doi.org/10.1038/37539 [20] M. F. Mor-Ruiz and W. Dür. ``Influence of noise in entanglement-based quantum networks''. IEEE J. Sel. Area. Comm 42, 1793 (2024). https://doi.org/10.1109/jsac.2024.3380089 [21] R. Frantzeskakis, C. Liu, Z. Raissi, et al. ``Extracting perfect GHZ states from imperfect weighted graph states via entanglement concentration''. Phys. Rev. Res. 5, 023124 (2023). https://doi.org/10.1103/PhysRevResearch.5.023124 [22] T. Wagner, H. Kampermann, D. Bruß, and M. Kliesch. ``Learning logical Pauli noise in quantum error correction''. Phys. Rev. Lett. 130, 200601 (2023). https://doi.org/10.1103/physrevlett.130.200601 [23] D. Miller, D. Loss, I. Tavernelli, et al. ``Shor–Laflamme distributions of graph states and noise robustness of entanglement''. J. Phys. A 56, 335303 (2023). https://doi.org/10.1088/1751-8121/ace8d4 [24] S. Morley-Short, M. Gimeno-Segovia, T. Rudolph, and H. Cable. ``Loss-tolerant teleportation on large stabilizer states''. Quantum Sci. Technol. 4, 025014 (2019). https://doi.org/10.1088/2058-9565/aaf6c4 [25] J. de Jong, F. Hahn, N. Tcholtchev, M. Hauswirth, and A. Pappa. ``Extracting GHZ states from linear cluster states''. Phys. Rev. Res. 6, 013330 (2024). https://doi.org/10.1103/physrevresearch.6.013330 [26] M. F. Mor-Ruiz and W. Dür. ``Noisy stabilizer formalism''. Phys. Rev. A 107, 032424 (2023). https://doi.org/10.1103/PhysRevA.107.032424 [27] J. Freund, A. Pirker, L. Vandré, and W. Dür. ``Graph state extraction from two-dimensional cluster states''. New J. Phys. 27, 094505 (2025). https://doi.org/10.1088/1367-2630/ae02bd [28] A. Dahlberg, J. Helsen, and S. Wehner. ``How to transform graph states using single-qubit operations: computational complexity and algorithms''. Quantum Sci. Technol. 5, 045016 (2020). https://doi.org/10.1088/2058-9565/aba763 [29] A. Dahlberg, J. Helsen, and S. Wehner. ``Transforming graph states to Bell-pairs is NP-Complete''. Quantum 4, 348 (2020). https://doi.org/10.22331/q-2020-10-22-348 [30] H. Aschauer, W. Dür, and H.-J. Briegel. ``Multiparticle entanglement purification for two-colorable graph states''. Phys. Rev. A 71, 012319 (2005). https://doi.org/10.1103/PhysRevA.71.012319 [31] C. Kruszynska, A. Miyake, H.-J. Briegel, and W. Dür. ``Entanglement purification protocols for all graph states''. Phys. Rev. A 74, 052316 (2006). https://doi.org/10.1103/physreva.74.052316 [32] A. Sajjad, E. Kaur, K. Goodenough, D. Towsley, and S. Guha. ``Lower bounds on bipartite entanglement in noisy graph states'' (2024). arXiv:2404.09014. arXiv:2404.09014 [33] Konrad Szymański, Lina Vandré, and Otfried Gühne (2025). Code repository on Zenodo: https://doi.org/10.5281/zenodo.14893380. https://doi.org/10.5281/zenodo.14893380 [34] J.-Y. Wu, H. Kampermann, and D. Bruß. ``Determining X-chains in graph states''. J. Phys. A 49, 055302 (2015). https://doi.org/10.1088/1751-8113/49/5/055302 [35] L. Hartmann, J. Calsamiglia, W. Dür, and H. J. Briegel. ``Weighted graph states and applications to spin chains, lattices and gases''. J. Phys. B 40, S1 (2007). https://doi.org/10.1088/0953-4075/40/9/S01 [36] D. M. Greenberger, M. A. Horne, and A. Zeilinger. ``Going beyond Bell’s theorem''. In Bell’s theorem, Quantum Theory and Conceptions of the Universe. Page 69. Springer (1989). https://doi.org/10.1007/978-94-017-0849-4_10 [37] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J. Briegel. ``Universal resources for measurement-based quantum computation''. Phys. Rev. Lett. 97, 150504 (2006). https://doi.org/10.1103/physrevlett.97.150504 [38] S. Cao, B. Wu, F. Chen, et al. ``Generation of genuine entanglement up to 51 superconducting qubits''. Nature 619, 738 (2023). https://doi.org/10.1038/s41586-023-06195-1 [39] P. Thomas, L. Ruscio, O. Morin, and G. Rempe. ``Efficient generation of entangled multiphoton graph states from a single atom''. Nature 608, 677 (2022). https://doi.org/10.1038/s41586-022-04987-5 [40] M. Van den Nest, J. Dehaene, and B. 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 [41] V. Mannalath and A. Pathak. ``Entanglement routing and bottlenecks in grid networks''. Ann. Phys. 20, 2400316 (2025). https://doi.org/10.1002/andp.202400316 [42] J. Stehlik, D. M. Zajac, D. L. Underwood, et al. ``Tunable coupling architecture for fixed-frequency transmon superconducting qubits''. Phys. Rev. Lett. 127, 080505 (2021). https://doi.org/10.1103/physrevlett.127.080505 [43] J. Long, T. Zhao, M. Bal, et al. ``A universal quantum gate set for transmon qubits with strong ZZ interactions'' (2021). arXiv:2103.12305. arXiv:2103.12305 [44] H. Wunderlich, C. Wunderlich, K. Singer, and F. Schmidt-Kaler. ``Two-dimensional cluster-state preparation with linear ion traps''. Phys. Rev. A 79, 052324 (2009). https://doi.org/10.1103/physreva.79.052324 [45] C. Piltz, T. Sriarunothai, A.F. Varón, and C. Wunderlich. ``A trapped-ion-based quantum byte with $10^{-5}$ next-neighbour cross-talk''. Nat. Commun. 5, 052324 (2014). https://doi.org/10.1038/ncomms5679 [46] J.-Y. Wu, M. Rossi, H. Kampermann, et al. ``Randomized graph states and their entanglement properties''. Phys. Rev. A 89, 052335 (2014). https://doi.org/10.1103/PhysRevA.89.052335 [47] P. Erdős and A. Rényi. ``On random graphs. I.''. Publ. Math. 6, 290 (1959). https://doi.org/10.5486/pmd.1959.6.3-4.12 [48] D. E. Browne and T. Rudolph. ``Resource-efficient linear optical quantum computation''. Phys. Rev. Lett. 95, 010501 (2005). https://doi.org/10.1103/physrevlett.95.010501 [49] P. P. Rohde and T. C. Ralph. ``Error models for mode mismatch in linear optics quantum computing''. Phys. Rev. A 73, 062312 (2006). https://doi.org/10.1103/physreva.73.062312 [50] S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves. ``Sufficient conditions for efficient classical simulation of quantum optics''. Phys. Rev. X 6, 021039 (2016). https://doi.org/10.1103/physrevx.6.021039 [51] J. Anders, E. Andersson, D. E Browne, et al. ``Ancilla-driven quantum computation with twisted graph states''. Theor. Comput. Sci. 430, 51 (2012). https://doi.org/10.1016/j.tcs.2012.02.007 [52] T. Rudolph. ``Why I am optimistic about the silicon-photonic route to quantum computing''. APL photonics 2, 030901 (2017). https://doi.org/10.1063/1.4976737 [53] U. I. Meyer, F. Grosshans, and D. Markham. ``Inflated graph states refuting communication-assisted local-hidden-variable models''. Phys. Rev. A 108, 012402 (2023). https://doi.org/10.1103/physreva.108.012402 [54] U. I. Meyer, I. Šupić, F. Grosshans, and D. Markham. ``Self-testing graph states permitting bounded classical communication'' (2024). arXiv:2404.03496. https://doi.org/10.22331/q-2026-01-08-1961 arXiv:2404.03496 [55] N. Shettell and D. Markham. ``Graph states as a resource for quantum metrology''. Phys. Rev. Lett. 124, 110502 (2020). https://doi.org/10.1103/physrevlett.124.110502 [56] G. Li, Y. Ding, and Y. Xie. ``Tackling the qubit mapping problem for NISQ-era quantum devices''. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS ’19. ACM (2019). https://doi.org/10.1145/3297858.3304023 [57] C.-Y. Lu, X.-Q. Zhou, O. Gühne, et al. ``Experimental entanglement of six photons in graph states''. Nat. Phys. 3, 91 (2007). https://doi.org/10.1038/nphys507Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-21 10:03:51: Could not fetch cited-by data for 10.22331/q-2026-01-21-1977 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-21 10:03:51: 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. AbstractCluster states and graph states in general offer a useful model of the stabilizer formalism and a path toward the development of measurement-based quantum computation. Their defining structure – the stabilizer group – encodes all possible correlations that can be observed during measurement. The measurement outcomes which are consistent with the stabilizer structure make error correction possible. Here, we leverage both properties to design feasible families of states that can be used as robust building blocks of quantum computation. This procedure reduces the effect of experimentally relevant noise models on the extraction of smaller entangled states from the larger noisy graph state. In particular, we study the extraction of Bell pairs from linearly extended graph states – this has the immediate consequence for state teleportation across the graph. We show that robust entanglement can be extracted by proper design of the linear graph with only a minimal overhead of the physical qubits. This scenario is relevant to systems in which the entanglement can be created between neighboring sites. The results shown in this work provide a mathematical framework for noise reduction in measurement-based quantum computation. With proper connectivity structures, the effect of noise can be minimized for a large class of realistic noise processes.Featured image: (top left) A simple path graph state can be used to generate a Bell pair via X-basis measurements on internal qubits. (bottom left) Preparation noise, modelled here as a missing edge, breaks the connectivity and destroys the entanglement between the terminal vertices. (right) The "crazy" graph is a robust alternative; dominant noise effects are suppressed and the target Bell pair remains largely untouched even with several missing edges. Popular summaryDistributing entanglement across a chain of qubits is straightforward in principle, but noise can break any single link and ruin the whole thing. Here we show that certain graph structures, notably the "crazy graph", tolerate noise much better than simple path graphs. Their redundant connectivity allows errors to be detected or even corrected automatically during the measurement process. For the crazy graph, the noise sensitivity stays constant no matter how long the chain gets, with only a small overhead in qubit count. This makes them practical candidates for robust entanglement distribution in quantum networks.► BibTeX data@article{Szymanski2026usefulentanglement, doi = {10.22331/q-2026-01-21-1977}, url = {https://doi.org/10.22331/q-2026-01-21-1977}, title = {Useful entanglement can be extracted from noisy graph states}, author = {Szyma{\'{n}}ski, Konrad and Vandr{\'{e}}, Lina and G{\"{u}}hne, Otfried}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1977}, month = jan, year = {2026} }► References [1] R. Raussendorf and H. J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188 (2001). https://doi.org/10.1103/physrevlett.86.5188 [2] M. A. Nielsen. ``Cluster-state quantum computation''. Rep. Math. Phys. 57, 147 (2006). https://doi.org/10.1016/s0034-4877(06)80014-5 [3] E. Muñoz‐Coreas and H. Thapliyal. ``Everything you always wanted to know about quantum circuits'' (2022). Wiley Encyclopedia of Electrical and Electronics Engineering. [4] M. P.A. Fisher, V. Khemani, A. Nahum, and S. Vijay. ``Random quantum circuits''. Annu. Rev. Condens. Matter Phys. 14, 335 (2023). https://doi.org/10.1146/annurev-conmatphys-031720-030658 [5] R. Raussendorf, D. E. Browne, and H. J. Briegel. ``Measurement-based quantum computation on cluster states''. Phys. Rev. A 68, 022312 (2003). https://doi.org/10.1103/PhysRevA.68.022312 [6] M. Rossi, M. Huber, D. Bruß, and C. Macchiavello. ``Quantum hypergraph states''. New J. Phys. 15, 113022 (2013). https://doi.org/10.1088/1367-2630/15/11/113022 [7] M. Hein, W. Dür, J. Eisert, et al. ``Entanglement in graph states and its applications''. arXiv:quant-ph/0602096, Proceedings of the International School of Physics “Enrico Fermi” 162, 115 (2006). https://doi.org/10.3254/978-1-61499-018-5-115 arXiv:quant-ph/0602096 [8] C. Kruszynska and B. Kraus. ``Local entanglability and multipartite entanglement''. Phys. Rev. A 79, 052304 (2009). https://doi.org/10.1103/PhysRevA.79.052304 [9] R. Qu, J. Wang, Z.-S. Li, and Y.-R. Bao. ``Encoding hypergraphs into quantum states''. Phys. Rev. A 87, 022311 (2013). https://doi.org/10.1103/PhysRevA.87.022311 [10] M. Gachechiladze, O. Gühne, and A. Miyake. ``Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states''. Phys. Rev. A 99, 052304 (2019). https://doi.org/10.1103/physreva.99.052304 [11] L. Vandré and O. Gühne. ``Entanglement purification of hypergraph states''. Phys. Rev. A 108, 062417 (2023). https://doi.org/10.1103/PhysRevA.108.062417 [12] F. Hahn, A. Pappa, and J. Eisert. ``Quantum network routing and local complementation''. npj Quantum Inf. 5, 76 (2019). https://doi.org/10.1038/s41534-019-0191-6 [13] V. Mannalath and A. Pathak. ``Multiparty entanglement routing in quantum networks''. Phys. Rev. A 108, 062614 (2023). https://doi.org/10.1103/physreva.108.062614 [14] C. Meignant, D. Markham, and F. Grosshans. ``Distributing graph states over arbitrary quantum networks''. Phys. Rev. A 100, 052333 (2019). https://doi.org/10.1103/physreva.100.052333 [15] A. Sen, K. Goodenough, and D. Towsley. ``Multipartite entanglement in quantum networks using subgraph complementations''. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Volume 02, pages 252–253. (2023). https://doi.org/10.1109/QCE57702.2023.10229 [16] X. Fan, C. Zhan, H. Gupta, and C. R. Ramakrishnan. ``Optimized distribution of entanglement graph states in quantum networks''. IEEE Trans. Quantum Eng. 6, 1 (2025). https://doi.org/10.1109/TQE.2025.3552006 [17] N. Basak and G. Paul. ``Improved routing of multiparty entanglement over quantum networks'' (2024). arXiv:2409.14694. arXiv:2409.14694 [18] C. H. Bennett, G. Brassard, C. Crépeau, et al. ``Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels''. Phys. Rev. Lett. 70, 1895 (1993). https://doi.org/10.1103/PhysRevLett.70.1895 [19] D. Bouwmeester, J.-W. Pan, K. Mattle, et al. ``Experimental quantum teleportation''. Nature 390, 575 (1997). https://doi.org/10.1038/37539 [20] M. F. Mor-Ruiz and W. Dür. ``Influence of noise in entanglement-based quantum networks''. IEEE J. Sel. Area. Comm 42, 1793 (2024). https://doi.org/10.1109/jsac.2024.3380089 [21] R. Frantzeskakis, C. Liu, Z. Raissi, et al. ``Extracting perfect GHZ states from imperfect weighted graph states via entanglement concentration''. Phys. Rev. Res. 5, 023124 (2023). https://doi.org/10.1103/PhysRevResearch.5.023124 [22] T. Wagner, H. Kampermann, D. Bruß, and M. Kliesch. ``Learning logical Pauli noise in quantum error correction''. Phys. Rev. Lett. 130, 200601 (2023). https://doi.org/10.1103/physrevlett.130.200601 [23] D. Miller, D. Loss, I. Tavernelli, et al. ``Shor–Laflamme distributions of graph states and noise robustness of entanglement''. J. Phys. A 56, 335303 (2023). https://doi.org/10.1088/1751-8121/ace8d4 [24] S. Morley-Short, M. Gimeno-Segovia, T. Rudolph, and H. Cable. ``Loss-tolerant teleportation on large stabilizer states''. Quantum Sci. Technol. 4, 025014 (2019). https://doi.org/10.1088/2058-9565/aaf6c4 [25] J. de Jong, F. Hahn, N. Tcholtchev, M. Hauswirth, and A. Pappa. ``Extracting GHZ states from linear cluster states''. Phys. Rev. Res. 6, 013330 (2024). https://doi.org/10.1103/physrevresearch.6.013330 [26] M. F. Mor-Ruiz and W. Dür. ``Noisy stabilizer formalism''. Phys. Rev. A 107, 032424 (2023). https://doi.org/10.1103/PhysRevA.107.032424 [27] J. Freund, A. Pirker, L. Vandré, and W. Dür. ``Graph state extraction from two-dimensional cluster states''. New J. Phys. 27, 094505 (2025). https://doi.org/10.1088/1367-2630/ae02bd [28] A. Dahlberg, J. Helsen, and S. Wehner. ``How to transform graph states using single-qubit operations: computational complexity and algorithms''. Quantum Sci. Technol. 5, 045016 (2020). https://doi.org/10.1088/2058-9565/aba763 [29] A. Dahlberg, J. Helsen, and S. Wehner. ``Transforming graph states to Bell-pairs is NP-Complete''. Quantum 4, 348 (2020). https://doi.org/10.22331/q-2020-10-22-348 [30] H. Aschauer, W. Dür, and H.-J. Briegel. ``Multiparticle entanglement purification for two-colorable graph states''. Phys. Rev. A 71, 012319 (2005). https://doi.org/10.1103/PhysRevA.71.012319 [31] C. Kruszynska, A. Miyake, H.-J. Briegel, and W. Dür. ``Entanglement purification protocols for all graph states''. Phys. Rev. A 74, 052316 (2006). https://doi.org/10.1103/physreva.74.052316 [32] A. Sajjad, E. Kaur, K. Goodenough, D. Towsley, and S. Guha. ``Lower bounds on bipartite entanglement in noisy graph states'' (2024). arXiv:2404.09014. arXiv:2404.09014 [33] Konrad Szymański, Lina Vandré, and Otfried Gühne (2025). Code repository on Zenodo: https://doi.org/10.5281/zenodo.14893380. https://doi.org/10.5281/zenodo.14893380 [34] J.-Y. Wu, H. Kampermann, and D. Bruß. ``Determining X-chains in graph states''. J. Phys. A 49, 055302 (2015). https://doi.org/10.1088/1751-8113/49/5/055302 [35] L. Hartmann, J. Calsamiglia, W. Dür, and H. J. Briegel. ``Weighted graph states and applications to spin chains, lattices and gases''. J. Phys. B 40, S1 (2007). https://doi.org/10.1088/0953-4075/40/9/S01 [36] D. M. Greenberger, M. A. Horne, and A. Zeilinger. ``Going beyond Bell’s theorem''. In Bell’s theorem, Quantum Theory and Conceptions of the Universe. Page 69. Springer (1989). https://doi.org/10.1007/978-94-017-0849-4_10 [37] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J. Briegel. ``Universal resources for measurement-based quantum computation''. Phys. Rev. Lett. 97, 150504 (2006). https://doi.org/10.1103/physrevlett.97.150504 [38] S. Cao, B. Wu, F. Chen, et al. ``Generation of genuine entanglement up to 51 superconducting qubits''. Nature 619, 738 (2023). https://doi.org/10.1038/s41586-023-06195-1 [39] P. Thomas, L. Ruscio, O. Morin, and G. Rempe. ``Efficient generation of entangled multiphoton graph states from a single atom''. Nature 608, 677 (2022). https://doi.org/10.1038/s41586-022-04987-5 [40] M. Van den Nest, J. Dehaene, and B. 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 [41] V. Mannalath and A. Pathak. ``Entanglement routing and bottlenecks in grid networks''. Ann. Phys. 20, 2400316 (2025). https://doi.org/10.1002/andp.202400316 [42] J. Stehlik, D. M. Zajac, D. L. Underwood, et al. ``Tunable coupling architecture for fixed-frequency transmon superconducting qubits''. Phys. Rev. Lett. 127, 080505 (2021). https://doi.org/10.1103/physrevlett.127.080505 [43] J. Long, T. Zhao, M. Bal, et al. ``A universal quantum gate set for transmon qubits with strong ZZ interactions'' (2021). arXiv:2103.12305. arXiv:2103.12305 [44] H. Wunderlich, C. Wunderlich, K. Singer, and F. Schmidt-Kaler. ``Two-dimensional cluster-state preparation with linear ion traps''. Phys. Rev. A 79, 052324 (2009). https://doi.org/10.1103/physreva.79.052324 [45] C. Piltz, T. Sriarunothai, A.F. Varón, and C. Wunderlich. ``A trapped-ion-based quantum byte with $10^{-5}$ next-neighbour cross-talk''. Nat. Commun. 5, 052324 (2014). https://doi.org/10.1038/ncomms5679 [46] J.-Y. Wu, M. Rossi, H. Kampermann, et al. ``Randomized graph states and their entanglement properties''. Phys. Rev. A 89, 052335 (2014). https://doi.org/10.1103/PhysRevA.89.052335 [47] P. Erdős and A. Rényi. ``On random graphs. I.''. Publ. Math. 6, 290 (1959). https://doi.org/10.5486/pmd.1959.6.3-4.12 [48] D. E. Browne and T. Rudolph. ``Resource-efficient linear optical quantum computation''. Phys. Rev. Lett. 95, 010501 (2005). https://doi.org/10.1103/physrevlett.95.010501 [49] P. P. Rohde and T. C. Ralph. ``Error models for mode mismatch in linear optics quantum computing''. Phys. Rev. A 73, 062312 (2006). https://doi.org/10.1103/physreva.73.062312 [50] S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves. ``Sufficient conditions for efficient classical simulation of quantum optics''. Phys. Rev. X 6, 021039 (2016). https://doi.org/10.1103/physrevx.6.021039 [51] J. Anders, E. Andersson, D. E Browne, et al. ``Ancilla-driven quantum computation with twisted graph states''. Theor. Comput. Sci. 430, 51 (2012). https://doi.org/10.1016/j.tcs.2012.02.007 [52] T. Rudolph. ``Why I am optimistic about the silicon-photonic route to quantum computing''. APL photonics 2, 030901 (2017). https://doi.org/10.1063/1.4976737 [53] U. I. Meyer, F. Grosshans, and D. Markham. ``Inflated graph states refuting communication-assisted local-hidden-variable models''. Phys. Rev. A 108, 012402 (2023). https://doi.org/10.1103/physreva.108.012402 [54] U. I. Meyer, I. Šupić, F. Grosshans, and D. Markham. ``Self-testing graph states permitting bounded classical communication'' (2024). arXiv:2404.03496. https://doi.org/10.22331/q-2026-01-08-1961 arXiv:2404.03496 [55] N. Shettell and D. Markham. ``Graph states as a resource for quantum metrology''. Phys. Rev. Lett. 124, 110502 (2020). https://doi.org/10.1103/physrevlett.124.110502 [56] G. Li, Y. Ding, and Y. Xie. ``Tackling the qubit mapping problem for NISQ-era quantum devices''. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS ’19. ACM (2019). https://doi.org/10.1145/3297858.3304023 [57] C.-Y. Lu, X.-Q. Zhou, O. Gühne, et al. ``Experimental entanglement of six photons in graph states''. Nat. Phys. 3, 91 (2007). https://doi.org/10.1038/nphys507Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-21 10:03:51: Could not fetch cited-by data for 10.22331/q-2026-01-21-1977 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-21 10:03:51: 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.