Graph-theoretical optimization of fusion-based graph state generation

Seok-Hyung Lee1,2 and Hyunseok Jeong1

1Department of Physics and Astronomy, Seoul National University, Seoul 08826, Republic of Korea
2Centre for Engineered Quantum Systems, School of Physics, University of Sydney, Sydney, NSW 2006, Australia

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


Graph states are versatile resources for various quantum information processing tasks, including measurement-based quantum computing and quantum repeaters. Although the type-II fusion gate enables all-optical generation of graph states by combining small graph states, its non-deterministic nature hinders the efficient generation of large graph states. In this work, we present a graph-theoretical strategy to effectively optimize fusion-based generation of any given graph state, along with a Python package OptGraphState. Our strategy comprises three stages: simplifying the target graph state, building a fusion network, and determining the order of fusions. Utilizing this proposed method, we evaluate the resource overheads of random graphs and various well-known graphs. Additionally, we investigate the success probability of graph state generation given a restricted number of available resource states. We expect that our strategy and software will assist researchers in developing and assessing experimentally viable schemes that use photonic graph states.

Graph states, which are quantum states where qubits are entangled in a way instructed by a graph structure, are versatile resource states for quantum computing and communication. In particular, graph states in photonic systems can be used for measurement-based quantum computing and fusion-based quantum computing, which are promising candidates for near-term fault-tolerant quantum computing. In this work, we propose a method to build arbitrary photonic graph states from initial three-photon basic resource states. This is achieved through a series of "fusion" operations, where smaller graph states are probabilistically merged into larger ones via specific photon measurements. The core of our strategy is a graph-theoretical framework designed to minimize the resource requirements of this process, enhancing efficiency and feasibility.

► BibTeX data

► References

[1] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. 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).

[2] Robert Raussendorf and Hans J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188–5191 (2001).

[3] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. ``Measurement-based quantum computation on cluster states''. Phys. Rev. A 68, 022312 (2003).

[4] R. Raussendorf, J. Harrington, and K. Goyal. ``A fault-tolerant one-way quantum computer''. Ann. Phys. 321, 2242–2270 (2006).

[5] R. Raussendorf, J. Harrington, and K. Goyal. ``Topological fault-tolerance in cluster state quantum computation''. New J. Phys. 9, 199 (2007).

[6] Sara Bartolucci, Patrick Birchall, Hector Bombin, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, et al. ``Fusion-based quantum computation''. Nat. Commun. 14, 912 (2023).

[7] D. Schlingemann and R. F. Werner. ``Quantum error-correcting codes associated with graphs''. Phys. Rev. A 65, 012308 (2001).

[8] A. Pirker, J. Wallnöfer, H. J. Briegel, and W. Dür. ``Construction of optimal resources for concatenated quantum protocols''. Phys. Rev. A 95, 062332 (2017).

[9] Damian Markham and Barry C. Sanders. ``Graph states for quantum secret sharing''. Phys. Rev. A 78, 042309 (2008).

[10] B. A. Bell, Damian Markham, D. A. Herrera-Martí, Anne Marin, W. J. Wadsworth, J. G. Rarity, and M. S. Tame. ``Experimental demonstration of graph-state quantum secret sharing''. Nat. Commun. 5, 5480 (2014).

[11] M. Zwerger, W. Dür, and H. J. Briegel. ``Measurement-based quantum repeaters''. Phys. Rev. A 85, 062326 (2012).

[12] M. Zwerger, H. J. Briegel, and W. Dür. ``Universal and optimal error thresholds for measurement-based entanglement purification''. Phys. Rev. Lett. 110, 260503 (2013).

[13] Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo. ``All-photonic quantum repeaters''. Nat. Commun. 6, 6787 (2015).

[14] J. Wallnöfer, M. Zwerger, C. Muschik, N. Sangouard, and W. Dür. ``Two-dimensional quantum repeaters''. Phys. Rev. A 94, 052307 (2016).

[15] Nathan Shettell and Damian Markham. ``Graph states as a resource for quantum metrology''. Phys. Rev. Lett. 124, 110502 (2020).

[16] Michael A. Nielsen. ``Optical quantum computation using cluster states''. Phys. Rev. Lett. 93, 040503 (2004).

[17] Daniel E. Browne and Terry Rudolph. ``Resource-efficient linear optical quantum computation''. Phys. Rev. Lett. 95, 010501 (2005).

[18] Jeremy C. Adcock, Sam Morley-Short, Joshua W. Silverstone, and Mark G. Thompson. ``Hard limits on the postselectability of optical graph states''. Quantum Sci. Technol. 4, 015010 (2018).

[19] Holger F. Hofmann and Shigeki Takeuchi. ``Quantum phase gate for photonic qubits using only beam splitters and postselection''. Phys. Rev. A 66, 024308 (2002).

[20] T. C. Ralph, N. K. Langford, T. B. Bell, and A. G. White. ``Linear optical controlled-NOT gate in the coincidence basis''. Phys. Rev. A 65, 062324 (2002).

[21] Ying Li, Peter C. Humphreys, Gabriel J. Mendoza, and Simon C. Benjamin. ``Resource costs for fault-tolerant linear optical quantum computing''. Phys. Rev. X 5, 041007 (2015).

[22] Samuel L. Braunstein and A. Mann. ``Measurement of the Bell operator and quantum teleportation''. Phys. Rev. A 51, R1727–R1730 (1995).

[23] W. P. Grice. ``Arbitrarily complete Bell-state measurement using only linear optical elements''. Phys. Rev. A 84, 042331 (2011).

[24] Fabian Ewert and Peter van Loock. ``$3/​4$-efficient Bell measurement with passive linear optics and unentangled ancillae''. Phys. Rev. Lett. 113, 140403 (2014).

[25] Seung-Woo Lee, Kimin Park, Timothy C. Ralph, and Hyunseok Jeong. ``Nearly deterministic Bell measurement with multiphoton entanglement for efficient quantum-information processing''. Phys. Rev. A 92, 052324 (2015).

[26] Seung-Woo Lee, Timothy C. Ralph, and Hyunseok Jeong. ``Fundamental building block for all-optical scalable quantum networks''. Phys. Rev. A 100, 052303 (2019).

[27] Keisuke Fujii and Yuuki Tokunaga. ``Fault-tolerant topological one-way quantum computation with probabilistic two-qubit gates''. Phys. Rev. Lett. 105, 250503 (2010).

[28] Ying Li, Sean D. Barrett, Thomas M. Stace, and Simon C. Benjamin. ``Fault tolerant quantum computation with nondeterministic gates''. Phys. Rev. Lett. 105, 250502 (2010).

[29] H. Jeong, M. S. Kim, and Jinhyoung Lee. ``Quantum-information processing for a coherent superposition state via a mixedentangled coherent channel''. Phys. Rev. A 64, 052308 (2001).

[30] H. Jeong and M. S. Kim. ``Efficient quantum computation using coherent states''. Phys. Rev. A 65, 042305 (2002).

[31] Srikrishna Omkar, Yong Siah Teo, and Hyunseok Jeong. ``Resource-efficient topological fault-tolerant quantum computation with hybrid entanglement of light''. Phys. Rev. Lett. 125, 060501 (2020).

[32] Srikrishna Omkar, Y. S. Teo, Seung-Woo Lee, and Hyunseok Jeong. ``Highly photon-loss-tolerant quantum computing using hybrid qubits''. Phys. Rev. A 103, 032602 (2021).

[33] Shuntaro Takeda, Takahiro Mizuta, Maria Fuwa, Peter Van Loock, and Akira Furusawa. ``Deterministic quantum teleportation of photonic quantum bits by a hybrid technique''. Nature 500, 315–318 (2013).

[34] Hussain A. Zaidi and Peter van Loock. ``Beating the one-half limit of ancilla-free linear optics Bell measurements''. Phys. Rev. Lett. 110, 260501 (2013).

[35] Seok-Hyung Lee, Srikrishna Omkar, Yong Siah Teo, and Hyunseok Jeong. ``Parity-encoding-based quantum computing with bayesian error tracking''. npj Quantum Inf. 9, 39 (2023).

[36] Gerald Gilbert, Michael Hamrick, and Yaakov S. Weinstein. ``Efficient construction of photonic quantum-computational clusters''. Phys. Rev. A 73, 064303 (2006).

[37] Konrad Kieling, David Gross, and Jens Eisert. ``Minimal resources for linear optical one-way computing''. J. Opt. Soc. Am. B 24, 184–188 (2007).

[38] 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).

[39] Srikrishna Omkar, Seok-Hyung Lee, Yong Siah Teo, Seung-Woo Lee, and Hyunseok Jeong. ``All-photonic architecture for scalable quantum computing with greenberger-horne-zeilinger states''. PRX Quantum 3, 030309 (2022).

[40] Michael Varnava, Daniel E. Browne, and Terry Rudolph. ``Loss tolerance in one-way quantum computation via counterfactual error correction''. Phys. Rev. Lett. 97, 120501 (2006).

[41] N. Lütkenhaus, J. Calsamiglia, and K.-A. Suominen. ``Bell measurements for teleportation''. Phys. Rev. A 59, 3295–3300 (1999).

[42] 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).

[43] C. Schön, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf. ``Sequential generation of entangled multiqubit states''. Phys. Rev. Lett. 95, 110503 (2005).

[44] Netanel H. Lindner and Terry Rudolph. ``Proposal for pulsed on-demand sources of photonic cluster state strings''. Phys. Rev. Lett. 103, 113602 (2009).

[45] 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).

[46] Shuntaro Takeda, Kan Takase, and Akira Furusawa. ``On-demand photonic entanglement synthesizer''. Science Advances 5, eaaw4530 (2019).

[47] 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).

[48] John W. Moon and Leo Moser. ``On cliques in graphs''. Isr. J. Math. 3, 23–28 (1965).

[49] Eugene L. Lawler, Jan Karel Lenstra, and A. H. G. Rinnooy Kan. ``Generating all maximal independent sets: NP-hardness and polynomial-time algorithms''. SIAM J. Comput. 9, 558–565 (1980).

[50] Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. ``A new algorithm for generating all the maximal independent sets''. SIAM J. Comput. 6, 505–517 (1977).

[51] Gabor Csardi and Tamas Nepusz. ``The igraph software package for complex network research''. InterJournal Complex Systems, 1695 (2006). url: https:/​/​

[52] David Eppstein, Maarten Löffler, and Darren Strash. ``Listing all maximal cliques in sparse graphs in near-optimal time''. In International Symposium on Algorithms and Computation. Pages 403–414. Springer (2010).

[53] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. ``Exploring network structure, dynamics, and function using NetworkX''. In Gäel Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference (SciPy2008). Pages 11–15. Pasadena, CA USA (2008). url: https:/​/​​biblio/​960616.

[54] Zvi Galil. ``Efficient algorithms for finding maximum matching in graphs''. ACM Comput. Surv. 18, 23–38 (1986).

[55] Paul Erdős and Alfréd Rényi. ``On random graphs I''. Publicationes mathematicae 6, 290–297 (1959).

[56] T. C. Ralph, A. J. F. Hayes, and Alexei Gilchrist. ``Loss-tolerant optical qubits''. Phys. Rev. Lett. 95, 100501 (2005).

[57] Sean D. Barrett and Thomas M. Stace. ``Fault tolerant quantum computation with very high threshold for loss errors''. Phys. Rev. Lett. 105, 200502 (2010).

[58] James M. Auger, Hussain Anwar, Mercedes Gimeno-Segovia, Thomas M. Stace, and Dan E. Browne. ``Fault-tolerant quantum computation with nondeterministic entangling gates''. Phys. Rev. A 97, 030301 (2018).

[59] G. B. Arfken, H. J. Weber, and F. E. Harris. ``Mathematical methods for physicists: A comprehensive guide''. Elsevier Science. (2011). url: https:/​/​​books?id=JOpHkJF-qcwC.

[60] 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).

[61] Axel Dahlberg and Stephanie Wehner. ``Transforming graph states using single-qubit operations''. Philos. T. Roy. Soc. A 376, 20170325 (2018).

[62] M. Hein, J. Eisert, and H. J. Briegel. ``Multiparty entanglement in graph states''. Phys. Rev. A 69, 062311 (2004).

Cited by

[1] Sobhan Ghanbari, Jie Lin, Benjamin MacLellan, Luc Robichaud, Piotr Roztocki, and Hoi-Kwong Lo, "Optimization of deterministic photonic graph state generation via local operations", arXiv:2401.00635, (2023).

[2] Brendan Pankovich, Alex Neville, Angus Kan, Srikrishna Omkar, Kwok Ho Wan, and Kamil Brádler, "Flexible entangled state generation in linear optics", arXiv:2310.06832, (2023).

[3] Seungbeom Chin, "Boson subtraction as an alternative to fusion gates for generating graph states", arXiv:2306.15148, (2023).

[4] Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, and Stéphan Thomassé, "Vertex-minor universal graphs for generating entangled quantum subsystems", arXiv:2402.06260, (2024).

[5] Jie Lin, Benjamin MacLellan, Sobhan Ghanbari, Julie Belleville, Khuong Tran, Luc Robichaud, Roger G. Melko, Hoi-Kwong Lo, and Piotr Roztocki, "GraphiQ: Quantum circuit design for photonic graph states", arXiv:2402.09285, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-02-27 14:46:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-02-27 14:46:51).