{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T04:02:58Z","timestamp":1750564978011,"version":"3.41.0"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031970627","type":"print"},{"value":"9783031970634","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-97063-4_5","type":"book-chapter","created":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T07:42:40Z","timestamp":1750491760000},"page":"54-70","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Universal Graph Theory Operations for\u00a0Graph State Preparation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3853-5404","authenticated-orcid":false,"given":"Tristan","family":"Cam","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3671-8607","authenticated-orcid":false,"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4023-8677","authenticated-orcid":false,"given":"Yvan","family":"Le Borgne","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5624-2955","authenticated-orcid":false,"given":"Simon","family":"Martiel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,22]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","unstructured":"Adcock, J.C., Morley-Short, S., Dahlberg, A., Silverstone, J.W.: Mapping graph state orbits under local complementation. Quantum 4, 305 (2020). https:\/\/doi.org\/10.22331\/q-2020-08-07-305","DOI":"10.22331\/q-2020-08-07-305"},{"issue":"6","key":"5_CR2","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1109\/tcad.2013.2244643","volume":"32","author":"M Amy","year":"2013","unstructured":"Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32(6), 818\u2013830 (2013). https:\/\/doi.org\/10.1109\/tcad.2013.2244643","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01275668","volume":"11","author":"A Bouchet","year":"1991","unstructured":"Bouchet, A.: An efficient algorithm to recognize locally equivalent graphs. Combinatorica 11, 315\u2013329 (1991). https:\/\/doi.org\/10.1007\/BF01275668","journal-title":"Combinatorica"},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Brandhofer, S., Polian, I., Barz, S., Bhatti, D.: Hardware-efficient preparation of architecture-specific graph states on near-term quantum computers, vol. 15(2095). Springer Nature\/Scientific Reports (2025). https:\/\/doi.org\/10.1038\/s41598-024-82715-x","DOI":"10.1038\/s41598-024-82715-x"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Goubault\u00a0de Brugi\u00e8re, T., Martiel, S.: Shallower cnot circuits on realistic quantum hardware. ACM Trans. Quant. Comput. (2024). https:\/\/doi.org\/10.1145\/3700884","DOI":"10.1145\/3700884"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Goubault\u00a0de Brugi\u00e8re, T., Martiel, S., Vuillot, C.: A graph-state based synthesis framework for clifford isometries. Quantum 9, 1589 (2025). https:\/\/doi.org\/10.22331\/q-2025-01-14-1589","DOI":"10.22331\/q-2025-01-14-1589"},{"key":"5_CR7","doi-asserted-by":"publisher","unstructured":"Cabello, A., Danielsen, L.E., L\u00f3pez-Tarrida, A.J., Portillo, J.R.: Optimal preparation of graph states. Phys. Rev. A 83(4) (2011). https:\/\/doi.org\/10.1103\/physreva.83.042314","DOI":"10.1103\/physreva.83.042314"},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Chia, N.H., Chung, K.M., Lai, C.Y.: On the need for large quantum depth. J. ACM 70(1) (2023). https:\/\/doi.org\/10.1145\/3570637","DOI":"10.1145\/3570637"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Dahlberg, A., Wehner, S.: Transforming graph states using single-qubit operations. Philosoph. Trans. Roy. Soc. Math. Phys. Eng. Sci. 376(2123) (2018). https:\/\/doi.org\/10.1098\/rsta.2017.0325","DOI":"10.1098\/rsta.2017.0325"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Dawson, C.M., Nielsen, M.A.: The Solovay-Kitaev algorithm. Quant. Inf. Comput. 6(1), 81\u201395 (2006). https:\/\/doi.org\/10.26421\/QIC6.1-6","DOI":"10.26421\/QIC6.1-6"},{"key":"5_CR11","doi-asserted-by":"publisher","unstructured":"Duncan, R., Kissinger, A., Perdrix, S., van\u00a0de Wetering, J.: Graph-theoretic simplification of quantum circuits with the ZX-calculus. Quantum 4, 279 (2020). https:\/\/doi.org\/10.22331\/q-2020-06-04-279","DOI":"10.22331\/q-2020-06-04-279"},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Duncan, R., Perdrix, S.: Graph states and the necessity of EULER decomposition. In: Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe (CiE). Lecture Notes in Computer Science, vol.\u00a05635, pp. 167\u2013177. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-03073-4_18","DOI":"10.1007\/978-3-642-03073-4_18"},{"issue":"6598","key":"5_CR13","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1126\/science.abo6587","volume":"376","author":"S Ebadi","year":"2022","unstructured":"Ebadi, S., Keesling, A., Cain, M., Wang, T.T., Levine, H., et al.: Quantum optimization of maximum independent set using RYDBERG atom arrays. Science 376(6598), 1209\u20131215 (2022). https:\/\/doi.org\/10.1126\/science.abo6587","journal-title":"Science"},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"1918","DOI":"10.1038\/s41467-017-01904-7","volume":"8","author":"C Figgatt","year":"2017","unstructured":"Figgatt, C., Maslov, D., Landsman, K.A., Linke, N.M., Debnath, S., Monroe, C.: Complete 3-qubit grover search on a programmable quantum computer. Nat. Commun. 8(1), 1918 (2017). https:\/\/doi.org\/10.1038\/s41467-017-01904-7","journal-title":"Nat. Commun."},{"key":"5_CR15","doi-asserted-by":"publisher","unstructured":"Flammia, S.T., Liu, Y.K.: Direct fidelity estimation from few Pauli measurements. Phys. Rev. Lett. 106(23) (2011). https:\/\/doi.org\/10.1103\/physrevlett.106.230501","DOI":"10.1103\/physrevlett.106.230501"},{"issue":"6598","key":"5_CR16","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1126\/science.abn7293","volume":"376","author":"HY Huang","year":"2022","unstructured":"Huang, H.Y., Broughton, M., Cotler, J., Chen, S., Li, J., et al.: Quantum advantage in learning from experiments. Science 376(6598), 1182\u20131186 (2022). https:\/\/doi.org\/10.1126\/science.abn7293","journal-title":"Science"},{"key":"5_CR17","doi-asserted-by":"publisher","unstructured":"Jozsa, R., Linden, N.: On the role of entanglement in quantum-computational speed-up. Proc. Roy. Soc. Lond. Ser. A: Math. Phys. Eng. Sci. 459(2036), 2011\u20132032 (2003). https:\/\/doi.org\/10.1098\/rspa.2002.1097","DOI":"10.1098\/rspa.2002.1097"},{"key":"5_CR18","doi-asserted-by":"publisher","unstructured":"Kalev, A., Kyrillidis, A., Linke, N.M.: Validating and certifying stabilizer states. Phys. Rev. A 99(4) (2019). https:\/\/doi.org\/10.1103\/physreva.99.042337","DOI":"10.1103\/physreva.99.042337"},{"key":"5_CR19","doi-asserted-by":"publisher","unstructured":"Kissinger, A., de\u00a0Griend, A.M.V.: Cnot circuit extraction for topologically-constrained quantum memories. Quant. Inf. Comput. 20(7-8), 581\u2013596 (2020). https:\/\/doi.org\/10.26421\/QIC20.7-8-4","DOI":"10.26421\/QIC20.7-8-4"},{"key":"5_CR20","doi-asserted-by":"publisher","unstructured":"Kliuchnikov, V., Maslov, D.: Optimization of clifford circuits. Phys. Rev. A 88(5) (2013). https:\/\/doi.org\/10.1103\/physreva.88.052307","DOI":"10.1103\/physreva.88.052307"},{"key":"5_CR21","unstructured":"Kotzig, A.: Eulerian lines in finite 4valent graphs and their transfomations. Theory Graphs 219\u2013230 (1968)"},{"key":"5_CR22","doi-asserted-by":"publisher","unstructured":"Kumabe, S., Mori, R., Yoshimura, Y.: Complexity of graph-state preparation by clifford circuits (2025). https:\/\/doi.org\/10.48550\/arXiv.2402.05874","DOI":"10.48550\/arXiv.2402.05874"},{"key":"5_CR23","doi-asserted-by":"publisher","unstructured":"Martinez, E.A., Monz, T., Nigg, D., Schindler, P., Blatt, R.: Compiling quantum algorithms for architectures with multi-qubit gates. New J. Phys. 18(6) (2016). https:\/\/doi.org\/10.1088\/1367-2630\/18\/6\/063029","DOI":"10.1088\/1367-2630\/18\/6\/063029"},{"issue":"7","key":"5_CR24","doi-asserted-by":"publisher","first-page":"4729","DOI":"10.1109\/tit.2018.2825602","volume":"64","author":"D Maslov","year":"2018","unstructured":"Maslov, D., Roetteler, M.: Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. IEEE Trans. Inf. Theory 64(7), 4729\u20134738 (2018). https:\/\/doi.org\/10.1109\/tit.2018.2825602","journal-title":"IEEE Trans. Inf. Theory"},{"key":"5_CR25","unstructured":"M\u00f6tt\u00f6nen$$^1$$, M., Vartiainen, J.J.: Decompositions of general quantum gates. Trends Quant. Comput. Res.\u00a0149 (2006)"},{"key":"5_CR26","doi-asserted-by":"publisher","unstructured":"Van\u00a0den Nest, M., Dehaene, J., De\u00a0Moor, B.: Graphical description of the action of local clifford transformations on graph states. Phys. Rev. A 69(2) (2004). https:\/\/doi.org\/10.1103\/physreva.69.022316","DOI":"10.1103\/physreva.69.022316"},{"key":"5_CR27","doi-asserted-by":"publisher","unstructured":"Pokharel, B., Lidar, D.A.: Demonstration of algorithmic quantum speedup. Phys. Rev. Lett. 130(21) (2023). https:\/\/doi.org\/10.1103\/physrevlett.130.210602","DOI":"10.1103\/physrevlett.130.210602"},{"key":"5_CR28","doi-asserted-by":"publisher","unstructured":"Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018). https:\/\/doi.org\/10.22331\/q-2018-08-06-79","DOI":"10.22331\/q-2018-08-06-79"},{"key":"5_CR29","doi-asserted-by":"publisher","unstructured":"Raussendorf, R., Browne, D.E., Briegel, H.J.: Measurement-based quantum computation on cluster states. Phys. Rev. A 68(2) (2003). https:\/\/doi.org\/10.1103\/physreva.68.022312","DOI":"10.1103\/physreva.68.022312"},{"key":"5_CR30","doi-asserted-by":"publisher","unstructured":"Roy, T., Hazra, S., Kundu, S., Chand, M., Patankar, M.P., Vijay, R.: Programmable superconducting processor with native three-qubit gates. Phys. Rev. Appl. 14(1) (2020). https:\/\/doi.org\/10.1103\/physrevapplied.14.014072","DOI":"10.1103\/physrevapplied.14.014072"},{"issue":"5","key":"5_CR31","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/s0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997). https:\/\/doi.org\/10.1137\/s0097539795293172","journal-title":"SIAM J. Comput."},{"key":"5_CR32","doi-asserted-by":"publisher","unstructured":"Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91(14) (2003). https:\/\/doi.org\/10.1103\/physrevlett.91.147902","DOI":"10.1103\/physrevlett.91.147902"},{"issue":"3","key":"5_CR33","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s10957-023-02229-w","volume":"197","author":"F Wagner","year":"2023","unstructured":"Wagner, F., B\u00e4rmann, A., Liers, F., Weissenb\u00e4ck, M.: Improving quantum computation by optimized qubit routing. J. Optim. Theory Appl. 197(3), 1161\u20131194 (2023). https:\/\/doi.org\/10.1007\/s10957-023-02229-w","journal-title":"J. Optim. Theory Appl."},{"key":"5_CR34","doi-asserted-by":"publisher","unstructured":"Wright, K., Beck, K.M., Debnath, S., Amini, J., Nam, Y., et\u00a0al.: Benchmarking an 11-qubit quantum computer. Nature Communications 10(1) (Nov 2019). https:\/\/doi.org\/10.1038\/s41467-019-13534-2","DOI":"10.1038\/s41467-019-13534-2"},{"key":"5_CR35","doi-asserted-by":"publisher","unstructured":"Xia, Y., Li, W., Zhuang, Q., Zhang, Z.: Quantum-enhanced data classification with a variational entangled sensor network. Phys. Rev. X 11(2) (2021). https:\/\/doi.org\/10.1103\/physrevx.11.021047","DOI":"10.1103\/physrevx.11.021047"},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2024.3402085","volume":"5","author":"W Yang","year":"2024","unstructured":"Yang, W., Rall, P.: Harnessing the power of long-range entanglement for Clifford circuit synthesis. IEEE Trans. Quant. Eng. 5, 1\u201310 (2024). https:\/\/doi.org\/10.1109\/TQE.2024.3402085","journal-title":"IEEE Trans. Quant. Eng."},{"key":"5_CR37","doi-asserted-by":"publisher","unstructured":"Yuan, P., Zhang, S.: Full characterization of the depth overhead for quantum circuit compilation with arbitrary qubit connectivity constraint. arXiv preprint arXiv:2402.02403 (2024). https:\/\/doi.org\/10.48550\/arXiv.2402.02403","DOI":"10.48550\/arXiv.2402.02403"},{"key":"5_CR38","doi-asserted-by":"publisher","unstructured":"Zhang, C., Hayes, A.B., Qiu, L., Jin, Y., Chen, Y., Zhang, E.Z.: Time-optimal qubit mapping. In: 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 360\u2013374. Association for Computing Machinery (2021). https:\/\/doi.org\/10.1145\/3445814.3446706","DOI":"10.1145\/3445814.3446706"},{"key":"5_CR39","doi-asserted-by":"publisher","unstructured":"Zhou, M.G., Cao, X.Y., Lu, Y.S., Wang, Y., Bao, Y., et\u00a0al.: Experimental quantum advantage with quantum coupon collector. Research 2022 (2022). https:\/\/doi.org\/10.34133\/2022\/9798679","DOI":"10.34133\/2022\/9798679"}],"container-title":["Lecture Notes in Computer Science","Reversible Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-97063-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T07:42:41Z","timestamp":1750491761000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-97063-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031970627","9783031970634"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-97063-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reversible Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Odense","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/reversible-computation-2025.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}