QuTech – TU Delft, Lorentzweg 1, 2628CJ Delft, The Netherlands
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Critical to the construction of large scale quantum networks, i.e. a quantum internet, is the development of fast algorithms for managing entanglement present in the network. One fundamental building block for a quantum internet is the distribution of Bell pairs between distant nodes in the network. Here we focus on the problem of transforming multipartite entangled states into the tensor product of bipartite Bell pairs between specific nodes using only a certain class of local operations and classical communication. In particular we study the problem of deciding whether a given graph state, and in general a stabilizer state, can be transformed into a set of Bell pairs on specific vertices using only single-qubit Clifford operations, single-qubit Pauli measurements and classical communication. We prove that this problem is ${mathbb{NP}}$-Complete.
► BibTeX data
► References
[1] Stephanie Wehner, David Elkouss, and Ronald Hanson. Quantum internet: A vision for the road ahead. Science, 362 (6412): eaam9288, Oct 2018. ISSN 0036-8075. 10.1126/science.aam9288. URL http://www.sciencemag.org/lookup/doi/10.1126/ science.aam9288.
https://doi.org/10.1126/science.aam9288
http://www.sciencemag.org/lookup/doi/10.1126/%20%20science.aam9288
[2] Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas, Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha. Routing entanglement in the quantum internet. npj Quantum Information, 5 (1): 25, 2019a. 10.1038/s41534-019-0139-x.
https://doi.org/10.1038/s41534-019-0139-x
[3] Mihir Pant, Don Towsley, Dirk Englund, and Saikat Guha. Percolation thresholds for photonic quantum computing. Nature Communications, 10 (1): 1070, 2019b. ISSN 2041-1723. 10.1038/s41467-019-08948-x.
https://doi.org/10.1038/s41467-019-08948-x
[4] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 10th anniversary edition edition, 2010. ISBN 9780511976667. 10.1017/CBO9780511976667. URL http://ebooks.cambridge.org/ref/id/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
http://ebooks.cambridge.org/ref/id/CBO9780511976667
[5] Takaaki Matsuo, Takahiko Satoh, Shota Nagayama, and Rodney Van Meter. Analysis of measurement-based quantum network coding over repeater networks under noisy conditions. Physical Review A, 97: 13, 10 2017. 10.1103/PhysRevA.97.062328.
https://doi.org/10.1103/PhysRevA.97.062328
[6] N. Kalb, A. A. Reiserer, P. C. Humphreys, J. J. W. Bakermans, S. J. Kamerling, N. H. Nickerson, S. C. Benjamin, D. J. Twitchen, M. Markham, and R. Hanson. Entanglement distillation between solid-state quantum network nodes. Science, 356 (6341): 928–932, jun 2017. ISSN 0036-8075. 10.1126/science.aan0070. URL http://www.sciencemag.org/lookup/doi/10.1126/ science.aan0070.
https://doi.org/10.1126/science.aan0070
http://www.sciencemag.org/lookup/doi/10.1126/%20%20science.aan0070
[7] H. Bombin and M. A. Martin-Delgado. Exact topological quantum order in $d=3$ and beyond: Branyons and brane-net condensates. Phys. Rev. B, 75: 075103, Feb 2007. 10.1103/PhysRevB.75.075103. URL https://link.aps.org/doi/10.1103/PhysRevB.75.075103.
https://doi.org/10.1103/PhysRevB.75.075103
[8] Héctor Bombín. Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes. New Journal of Physics, 17 (8): 083002, aug 2015. 10.1088/1367-2630/17/8/083002. URL https://doi.org/10.1088.
https://doi.org/10.1088/1367-2630/17/8/083002
[9] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M Van den Nest, H. J. Briegel, M. Van den Nest, and H. J. Briegel. Entanglement in Graph States and its Applications. Quantum Computers, Algorithms and Chaos, pages 1–99, 2006. ISSN 1050-2947. 10.3254/978-1-61499-018-5-115. URL http://arxiv.org/abs/quant-ph/0602096.
https://doi.org/10.3254/978-1-61499-018-5-115
arXiv:quant-ph/0602096
[10] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Graphical description of the action of local clifford transformations on graph states. Physical Review A, 69 (2): 022316, 2004. 10.1103/PhysRevA.69.022316.
https://doi.org/10.1103/PhysRevA.69.022316
[11] Axel Dahlberg and Stephanie Wehner. Transforming graph states using single-qubit operations. Phil. Trans. R. Soc. A 376, One contribution of 15 to a discussion meeting issue ‘Foundations of quantum mechanics and their impact on contemporary society’, 2018. 10.1098/rsta.2017.0325.
https://doi.org/10.1098/rsta.2017.0325
[12] 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 (4): 045016, sep 2020. 10.1088/2058-9565/aba763.
https://doi.org/10.1088/2058-9565/aba763
[13] F. Hahn, A. Pappa, and J. Eisert. Quantum network routing and local complementation. npj Quantum Information, 5 (1): 76, Sep 2019. ISSN 2056-6387. 10.1038/s41534-019-0191-6.
https://doi.org/10.1038/s41534-019-0191-6
[14] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. The complexity of the vertex-minor problem. arXiv preprint arXiv:1906.05689, 2019.
arXiv:1906.05689
[15] Hans J. Briegel and Robert Raussendorf. Persistent entanglement in arrays of interacting particles. Phys. Rev. Lett., 86: 910–913, Jan 2001. 10.1103/PhysRevLett.86.910. URL https://link.aps.org/doi/10.1103/PhysRevLett.86.910.
https://doi.org/10.1103/PhysRevLett.86.910
[16] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/PhysRevLett.86.5188. URL https://link.aps.org/doi/10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188
[17] André Bouchet. An efficient algorithm to recognize locally equivalent graphs. Combinatorica, 11 (4): 315–329, 1991. ISSN 0209-9683. 10.1007/BF01275668. URL http://link.springer.com/10.1007/BF01275668.
https://doi.org/10.1007/BF01275668
[18] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Efficient algorithm to recognize the local Clifford equivalence of graph states. Physical Review A, 70 (3): 034302, 2004. ISSN 1050-2947. 10.1103/PhysRevA.70.034302. URL https://link.aps.org/doi/10.1103/PhysRevA.70.034302.
https://doi.org/10.1103/PhysRevA.70.034302
[19] Sang Il Oum. Rank-width and vertex-minors. Journal of Combinatorial Theory. Series B, 95 (1): 79–100, 2005. ISSN 00958956. 10.1016/j.jctb.2005.03.003.
https://doi.org/10.1016/j.jctb.2005.03.003
[20] Bruno Courcelle and Sang il Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory. Series B, 97 (1): 91–126, 2007. ISSN 00958956. 10.1016/j.jctb.2006.04.003.
https://doi.org/10.1016/j.jctb.2006.04.003
[21] Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language Theoretic Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2011. 10.1017/CBO9780511977619.
https://doi.org/10.1017/CBO9780511977619
[22] M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel. Classical simulation versus universality in measurement-based quantum computation. Physical Review A, 75 (1): 012337, 2007. ISSN 1050-2947. 10.1103/PhysRevA.75.012337. URL https://link.aps.org/doi/10.1103/PhysRevA.75.012337.
https://doi.org/10.1103/PhysRevA.75.012337
[23] Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. Practical algorithms for mso model-checking on tree-decomposable graphs. Comput. Sci. Rev., 13 (C): 39–74, November 2014. ISSN 1574-0137. 10.1016/j.cosrev.2014.08.001. URL http://dx.doi.org/10.1016/j.cosrev.2014.08.001.
https://doi.org/10.1016/j.cosrev.2014.08.001
[24] Bernardo Martin, Angel Sanchez, Cesar Beltran-Royo, and Abraham Duarte. Solving the edge-disjoint paths problem using a two-stage method. International Transactions in Operational Research, 27 (1): 435–457, 2020. 10.1111/itor.12544. URL https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12544.
https://doi.org/10.1111/itor.12544
[25] André Bouchet. Graphic presentations of isotropic systems. Journal of Combinatorial Theory, Series B, 45 (1): 58–76, 1988. ISSN 10960902. 10.1016/0095-8956(88)90055-X.
https://doi.org/10.1016/0095-8956(88)90055-X
[26] Anton Kotzig. Quelques remarques sur les transformations $kappa$. In seminaire Paris, 1977.
[27] André Bouchet. Caracterisation des symboles croises de genre nul. Comptes Rendus de l’Académie des Sciences, 274: 724–727, 1972.
[28] André Bouchet. Circle Graph Obstructions. Journal of Combinatorial Theory, Series B, 60 (1): 107–144, 1994. 10.1006/jctb.1994.1008.
https://doi.org/10.1006/jctb.1994.1008
[29] Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. North-Holland Publishing Co., 2nd edition, 2004. ISBN 978-0444515308. 10.1016/C2013-0-10739-8.
https://doi.org/10.1016/C2013-0-10739-8
[30] Norman Biggs, E Keith Lloyd, and Robin J Wilson. Graph Theory, 1736-1936. Oxford University Press, 1976. ISBN 9780198539162.
[31] Jens Vygen. Np-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61 (1): 83–90, 1995. 10.1016/0166-218X(93)E0177-Z.
https://doi.org/10.1016/0166-218X(93)E0177-Z
[32] M. Fleury. Deux problemes de Geometrie de sitation. Journal de mathematiques elementaires, 2nd (2): 257–261, 1883.
[33] Shimon Even. Graph Algorithms. Cambridge University Press, 2 edition, 2011. 10.1017/CBO9781139015165.
https://doi.org/10.1017/CBO9781139015165
Cited by
[1] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner, “Counting single-qubit Clifford equivalent graph states is #P -complete”, Journal of Mathematical Physics 61 2, 022202 (2020).
The above citations are from SAO/NASA ADS (last updated successfully 2020-10-26 03:05:50). 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 2020-10-26 03:05:49).
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.
Source: https://quantum-journal.org/papers/q-2020-10-22-348/
