×

Transforming graph states using single-qubit operations. (English) Zbl 1404.81073

Summary: Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. What is more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool – for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph \(G'\) is a vertex-minor of another graph \(G\). The vertex-minor problem is, in general, \(\mathbb{NP}\)-Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the rank-width which equals the Schmidt-rank width of a subclass of stabilizer states called graph states, and thus intuitively is a measure of entanglement. Here, we show that the vertex-minor problem can be solved in time \(O(|G|^3)\), where \(|G|\) is the size of the graph \(G\), whenever the rank-width of \(G\) and the size of \(G'\) are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information.

MSC:

81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Gottesman D. (1999)The Heisenberg representation of quantum computers. In Proc. of the XXII Int. Colloquium on Group Theoretical Methods in Physics, Hobart, Tasmania, 13-17 July, 1998, vol. 1, pp. 32-43.
[2] Markham D, Sanders BC. (2008) Graph states for quantum secret sharing. Phys. Rev. A Atomic Mol. Opt. Phys. 78, 042309. (doi:10.1103/PhysRevA.78.042309) · Zbl 1255.81125 · doi:10.1103/PhysRevA.78.042309
[3] Christandl M, Wehner S. (2005)Quantum anonymous transmissions. In Advances in Cryptology - ASIACRYPT 2005 (ed. R Bimal), pp. 217-235. Berlin, Germany: Springer. · Zbl 1154.94383
[4] Ribeiro J, Murta G, Wehner S. (2018) Fully device-independent conference key agreement. Phys. Rev. A 97, 022307. (doi:10.1103/PhysRevA.97.022307) · doi:10.1103/PhysRevA.97.022307
[5] Jozsa R, Abrams DS, Dowling JP, Williams CP. (2000) Quantum clock synchronization based on shared prior entanglement. Phys. Rev. Lett. 85, 2010-2013. (doi:10.1103/PhysRevLett.85.2010) · doi:10.1103/PhysRevLett.85.2010
[6] Raussendorf R, Briegel HJ. (2001) A one-way quantum computer. Phys. Rev. Lett. 86, 5188-5191. (doi:10.1103/PhysRevLett.86.5188) · doi:10.1103/PhysRevLett.86.5188
[7] Gottesman D. (1997)Stabilizer codes and quantum error correction. PhD thesis, California Institute of Technology, Pasadena, CA, USA.
[8] Azuma K, Tamaki K, Lo HK. (2015) All-photonic quantum repeaters. Nat. Commun. 6, 1-7. (doi:10.1038/ncomms7787) · doi:10.1038/ncomms7787
[9] Van den Nest M, Dehaene J, De Moor B. (2004) Graphical description of the action of local Clifford transformations on graph states. Phys. Rev. A 69, 022316. (doi:10.1103/PhysRevA.69.022316) · doi:10.1103/PhysRevA.69.022316
[10] Bouchet A. (1991) An efficient algorithm to recognize locally equivalent graphs. Combinatorica 11, 315-329. (doi:10.1007/BF01275668) · Zbl 0744.05052 · doi:10.1007/BF01275668
[11] Van den Nest M, Dehaene J, DeMoor B. (2004) Efficient algorithm to recognize the local Clifford equivalence of graph states. Phys. Rev. A 70, 034302. (doi:10.1103/PhysRevA.70.034302) · doi:10.1103/PhysRevA.70.034302
[12] Dahlberg A, Helsen J, Wehner S. In preparation. How to transform graph states using single-qubit operations and why this is NP-Complete.
[13] Langer A, Reidl F, Rossmanith P, Sikdar S. (2014) Practical algorithms for MSO model-checking on tree-decomposable graphs. Comput. Sci. Rev. 13-14, 39-74. (doi:10.1016/j.cosrev.2014.08.001) · Zbl 1302.68184 · doi:10.1016/j.cosrev.2014.08.001
[14] Ganian R, Hliněný P. (2010) On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Appl. Math. 158, 851-867. (doi:10.1016/j.dam.2009.10.018) · Zbl 1231.05096 · doi:10.1016/j.dam.2009.10.018
[15] SAGE. (2017)SageMath. See http://www.sagemath.org/.
[16] MONA. (2016)The MONA project. See http://www.brics.dk/mona/index.html.
[17] GitHub. (2018)Git-repository with implemented code. See https://github.com/AckslD/vertex-minors.
[18] Hein M, Dür W, Eisert J, Raussendorf R, Van den Nest M, Briegel HJ. (2006) Entanglement in graph states and its applications. Quantum Comput. Algorithms Chaos 162, 115-218.
[19] Hein M, Eisert J, Briegel HJ. (2004) Multiparty entanglement in graph states. Phys. Rev. A Atomic Mol. Opt. Phys. 69, 062311. (doi:10.1103/PhysRevA.69.062311) · Zbl 1232.81007 · doi:10.1103/PhysRevA.69.062311
[20] Bouchet A. (1988) Graphic presentations of isotropic systems. J. Comb. Theory Ser. B 45, 58-76. (doi:10.1016/0095-8956(88)90055-X) · Zbl 0662.05014 · doi:10.1016/0095-8956(88)90055-X
[21] Robertson N, Seymour P. (1986) Graph minors: algorithmic aspects of tree-width. J. Algorithms 7, 309-322. (doi:10.1016/0196-6774(86)90023-4) · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[22] Downey RG, Fellows MR. (2012)Parameterized complexity. New York, NY: Springer.
[23] Oum SI. (2005) Rank-width and vertex-minors. J. Comb. Theory. Ser. B 95, 79-100. (doi:10.1016/j.jctb.2005.03.003) · Zbl 1070.05023 · doi:10.1016/j.jctb.2005.03.003
[24] Van den Nest M, Dür W, Vidal G, Briegel HJ. (2007) Classical simulation versus universality in measurement-based quantum computation. Phys. Rev. A 75, 012337. (doi:10.1103/PhysRevA.75.012337) · doi:10.1103/PhysRevA.75.012337
[25] Courcelle B, Oum SI. (2007) Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory. Ser. B 97, 91-126. (doi:10.1016/j.jctb.2006.04.003) · Zbl 1121.03016 · doi:10.1016/j.jctb.2006.04.003
[26] Courcelle B. (1990) The monadic second-order theory of graphs. I. Recognizable sets of finite graphs. Info. Comput. 85, 12-75. (doi:10.1016/0890-5401(90)90043-H) · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H
[27] Gupta A, Nishimura N. (1996) The complexity of subgraph isomorphism for classes of partial k-trees. Theor. Comput. Sci. 164, 287-298. (doi:10.1016/0304-3975(96)00046-1) · Zbl 0871.68139 · doi:10.1016/0304-3975(96)00046-1
[28] Courcelle B, Engelfriet J(2011) Graph structure and monadic second-order logic: a language theoretic approach, 1st edn. New York, NY: Cambridge University Press.
[29] Oum SI, Seymour P. (2006) Approximating clique-width and branch-width. J. Comb. Theory. Ser. B 96, 514-528. (doi:10.1016/j.jctb.2005.10.006) · Zbl 1114.05022 · doi:10.1016/j.jctb.2005.10.006
[30] Langer A, Rossmanith P, Sikdar S. (2011)Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract). In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). LNCS, vol. 6648, pp. 505-516. New York, NY: Springer. · Zbl 1331.68111
[31] Bouchet A. (1987) Isotropic systems. Eur. J. Combin. 8, 231-244. (doi:10.1016/S0195-6698(87)80027-6) · Zbl 0642.05015 · doi:10.1016/S0195-6698(87)80027-6
[32] Aschauer H, Dür W, Briegel HJ. (2005) Multiparticle entanglement purification for two-colorable graph states. Phys. Rev. A Atomic Mol. Optical Phys. 71, 1-22. (doi:10.1103/PhysRevA.71.012319) · doi:10.1103/PhysRevA.71.012319
[33] Bouchet A. · Zbl 0788.05081 · doi:10.1016/0012-365X(93)90357-Y
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.