Graph state

Last updated November 07, 2024

In quantum computing, a graph state is a special type of multi-qubit state that can be represented by a graph. Each qubit is represented by a vertex of the graph, and there is an edge between every interacting pair of qubits. In particular, they are a convenient way of representing certain types of entangled states.

Graph states are useful in quantum error-correcting codes, entanglement measurement and purification and for characterization of computational resources in measurement based quantum computing models. A graph state is a particular case of a stabilizer state as well as a 2-uniform hypergraph state, a generalization where the edges have cardinality between 1 and N.

Formal definition

Quantum graph states can be defined in two equivalent ways: through the notion of quantum circuits and stabilizer formalism.

Quantum circuit definition

Given a graph $G=(V,E)$ , with the set of vertices $V$ and the set of edges $E$ , the corresponding graph state is defined as

{\left|G\right\rangle }=\prod _{(a,b)\in E}U^{\{a,b\}}{\left|+\right\rangle }^{\otimes V}

where ${\left|+\right\rangle }={\frac {1}{\sqrt {2}}}({\left|0\right\rangle }+{\left|1\right\rangle })$ and the operator $U^{\{a,b\}}$ is the controlled-Z interaction between the two vertices (corresponding to two qubits) $a$ and $b$

U^{\{a,b\}}=\left[{\begin{array}{cccc}{1}&{0}&{0}&{0}\\{0}&{1}&{0}&{0}\\{0}&{0}&{1}&{0}\\{0}&{0}&{0}&{-1}\end{array}}\right]

Stabilizer formalism definition

An alternative and equivalent definition is the following, which makes use of the stabilizer formalism.

Define an operator $S_{v}$ for each vertex $v$ of $G$ :

S_{v}=\sigma _{x}^{(v)}\prod _{u\in N(v)}\sigma _{z}^{(u)}

where $\sigma _{x,y,z}$ are the Pauli matrices and $N(v)$ is the set of vertices adjacent to $v$ . The $S_{v}$ operators commute. The graph state ${\left|G\right\rangle }$ is defined as the simultaneous $+1$ -eigenvalue eigenstate of the $\left|V\right|$ operators $\left\{S_{v}\right\}_{v\in V}$ :

S_{v}{\left|G\right\rangle }={\left|G\right\rangle }

and thus every graph state is a stabilizer state.

Equivalence between the two definitions

A proof of the equivalence of the two definitions can be found in.^[1]^[2]

Examples

If $G=P_{3}$ is a three-vertex path, then the $S_{v}$ stabilizers are

{\begin{aligned}\sigma _{x}\otimes {}&\sigma _{z}\otimes I,\\\sigma _{z}\otimes {}&\sigma _{x}\otimes \sigma _{z},\\I\otimes {}&\sigma _{z}\otimes \sigma _{x}\end{aligned}}

The corresponding quantum state is

{\left|P_{3}\right\rangle }={\frac {1}{\sqrt {8}}}({\left|000\right\rangle }+{\left|100\right\rangle }+{\left|010\right\rangle }-{\left|110\right\rangle }+{\left|001\right\rangle }+{\left|101\right\rangle }-{\left|011\right\rangle }+{\left|111\right\rangle })

If $G=K_{3}$ is a triangle on three vertices, then the $S_{v}$ stabilizers are

{\begin{aligned}\sigma _{x}\otimes {}&\sigma _{z}\otimes \sigma _{z},\\\sigma _{z}\otimes {}&\sigma _{x}\otimes \sigma _{z},\\\sigma _{z}\otimes {}&\sigma _{z}\otimes \sigma _{x}\end{aligned}}

The corresponding quantum state is

{\left|K_{3}\right\rangle }={\frac {1}{\sqrt {8}}}({\left|000\right\rangle }+{\left|100\right\rangle }+{\left|010\right\rangle }-{\left|110\right\rangle }+{\left|001\right\rangle }-{\left|101\right\rangle }-{\left|011\right\rangle }-{\left|111\right\rangle })

Observe that ${\left|P_{3}\right\rangle }$ and ${\left|K_{3}\right\rangle }$ are locally equivalent to each other, i.e., can be mapped to each other by applying one-qubit unitary transformations. Indeed, switching $\sigma _{x}$ and $\sigma _{y}$ on the first and last qubits, while switching $\sigma _{y}$ and $\sigma _{z}$ on the middle qubit, maps the stabilizer group of one into that of the other.

Local Equivalence

Two graph states are called locally equivalent if one can be converted into the other by local unitary gates. If the conversion from one state to the other can be performed by local gates from the Clifford group, the two states are called locally Clifford equivalent. If and only if two graph states are locally Clifford equivalent, one graph can be converted into the other by a sequence of so-called "local complementations".^[3] This gives a useful tool for studying local Clifford equivalence by a simple graph-manipulation rule and corresponding equivalence classes of graph states have been studied in Refs.^[1]^[4]^[5] However, local Clifford equivalence of graph states only coincides with local unitary equivalence for small graph states^[1] and is generally not identical.^[6]

Entanglement criteria and Bell inequalities for graph states

After a graph state was created in an experiment, it is important to verify that indeed, an entangled quantum state has been created. The fidelity with respect to a $N$ -qubit graph state $|G_{N}\rangle$ is given by

$F_{GN}={\rm {Tr}}(\rho |G_{N}\rangle \langle G_{N}|),$

It has been shown that if $F_{GN}>1/2$ for a nontrivial graph state corresponding to a connected graph, then the state $\rho$ has genuine multiparticle entanglement.^[7]^[8] Thus, one can obtain an entanglement witness detecting entanglement close the graph states as

$W_{GN}={\frac {1}{2}}{\rm {Identity}}-|G_{N}\rangle \langle G_{N}|.$

where $\langle W_{GN}\rangle <0$ signals genuine multiparticle entanglement.

Such a witness cannot be measured directly. It has to be decomposed to a sum of correlations terms, which can then be measured. However, for large systems this approach can be difficult.

There are also entanglement witnesses that work in very large systems, and they also detect genuine multipartite entanglement close to graph states. Here, the graph state itself has to be genuine multipartite entangled, that is, it has to correspond to a connected graph. The witnesses need only the minimal two local measurement settings for graph states corresponding to two-colorable graphs.^[7]^[8] Similar conditions can also be used to put a lower bound on the fidelity with respect to an ideal graph state.^[8] These criteria have been used first in an experiment realizing four-qubit cluster states with photons.^[9] These approaches have also been used to propose methods for detecting entanglement in a smaller part of a large cluster state or graph state realized in optical lattices.^[10]

Bell inequalities have also been developed for cluster states.^[11]^[12]^[13] All these entanglement conditions and Bell inequalities are based on the stabilizer formalism.^[14]

Related Research Articles

Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from one location to the next, quantum teleportation only transfers quantum information. The sender does not have to know the particular quantum state being transferred. Moreover, the location of the recipient can be unknown, but to complete the quantum teleportation, classical information needs to be sent from sender to receiver. Because classical information needs to be sent, quantum teleportation cannot occur faster than the speed of light.

Quantum entanglement is the phenomenon of a group of particles being generated, interacting, or sharing spatial proximity in such a way that the quantum state of each particle of the group cannot be described independently of the state of the others, including when the particles are separated by a large distance. The topic of quantum entanglement is at the heart of the disparity between classical and quantum physics: entanglement is a primary feature of quantum mechanics not present in classical mechanics.

Bell's theorem is a term encompassing a number of closely related results in physics, all of which determine that quantum mechanics is incompatible with local hidden-variable theories, given some basic assumptions about the nature of measurement. "Local" here refers to the principle of locality, the idea that a particle can only be influenced by its immediate surroundings, and that interactions mediated by physical fields cannot propagate faster than the speed of light. "Hidden variables" are supposed properties of quantum particles that are not included in quantum theory but nevertheless affect the outcome of experiments. In the words of physicist John Stewart Bell, for whom this family of results is named, "If [a hidden-variable theory] is local it will not agree with quantum mechanics, and if it agrees with quantum mechanics it will not be local."

In physics, the CHSH inequality can be used in the proof of Bell's theorem, which states that certain consequences of entanglement in quantum mechanics cannot be reproduced by local hidden-variable theories. Experimental verification of the inequality being violated is seen as confirmation that nature cannot be described by such theories. CHSH stands for John Clauser, Michael Horne, Abner Shimony, and Richard Holt, who described it in a much-cited paper published in 1969. They derived the CHSH inequality, which, as with John Stewart Bell's original inequality, is a constraint—on the statistical occurrence of "coincidences" in a Bell test—which is necessarily true if an underlying local hidden-variable theory exists. In practice, the inequality is routinely violated by modern experiments in quantum mechanics.

In quantum physics, a measurement is the testing or manipulation of a physical system to yield a numerical result. A fundamental feature of quantum theory is that the predictions it makes are probabilistic. The procedure for finding a probability involves combining a quantum state, which mathematically describes a quantum system, with a mathematical representation of the measurement to be performed on that system. The formula for this calculation is known as the Born rule. For example, a quantum particle like an electron can be described by a quantum state that associates to each point in space a complex number called a probability amplitude. Applying the Born rule to these amplitudes gives the probabilities that the electron will be found in one region or another when an experiment is performed to locate it. This is the best the theory can do; it cannot say for certain where the electron will be found. The same quantum state can also be used to make a prediction of how the electron will be moving, if an experiment is performed to measure its momentum instead of its position. The uncertainty principle implies that, whatever the quantum state, the range of predictions for the electron's position and the range of predictions for its momentum cannot both be narrow. Some quantum states imply a near-certain prediction of the result of a position measurement, but the result of a momentum measurement will be highly unpredictable, and vice versa. Furthermore, the fact that nature violates the statistical conditions known as Bell inequalities indicates that the unpredictability of quantum measurement results cannot be explained away as due to ignorance about "local hidden variables" within quantum systems.

<span class="mw-page-title-main">LOCC</span> Method in quantum computation and communication

LOCC, or local operations and classical communication, is a method in quantum information theory where a local (product) operation is performed on part of the system, and where the result of that operation is "communicated" classically to another part where usually another local operation is performed conditioned on the information received.

In physics, in the area of quantum information theory, a Greenberger–Horne–Zeilinger state is a certain type of entangled quantum state that involves at least three subsystems. The four-particle version was first studied by Daniel Greenberger, Michael Horne and Anton Zeilinger in 1989, and the three-particle version was introduced by N. David Mermin in 1990. Extremely non-classical properties of the state have been observed, contradicting intuitive notions of locality and causality. GHZ states for large numbers of qubits are theorized to give enhanced performance for metrology compared to other qubit superposition states.

The W state is an entangled quantum state of three qubits which in the bra-ket notation has the following shape

<span class="mw-page-title-main">One-way quantum computer</span> Method of quantum computing

The one-way quantum computer, also known as measurement-based quantum computer (MBQC), is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

In quantum information and quantum computing, a cluster state is a type of highly entangled state of multiple qubits. Cluster states are generated in lattices of qubits with Ising type interactions. A cluster C is a connected subset of a d-dimensional lattice, and a cluster state is a pure state of the qubits located on C. They are different from other types of entangled states such as GHZ states or W states in that it is more difficult to eliminate quantum entanglement in the case of cluster states. Another way of thinking of cluster states is as a particular instance of graph states, where the underlying graph is a connected subset of a d-dimensional lattice. Cluster states are especially useful in the context of the one-way quantum computer. For a comprehensible introduction to the topic see.

In quantum information science, the concurrence is a state invariant involving qubits.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state $into some number of approximately pure Bell pairs, using only local operations and classical communication.$

Quantum block codes are useful in quantum computing and in quantum communications. The encoding circuit for a large block code typically has a high complexity although those for modern codes do have lower complexity.

In quantum mechanics, a matrix product state (MPS) is a quantum state of many particles, written in the following form:

Quantum complex networks are complex networks whose nodes are quantum computing devices. Quantum mechanics has been used to create secure quantum communications channels that are protected from hacking. Quantum communications offer the potential for secure enterprise-scale solutions.

In quantum mechanics, weak measurement is a type of quantum measurement that results in an observer obtaining very little information about the system on average, but also disturbs the state very little. From Busch's theorem any quantum system is necessarily disturbed by measurement, but the amount of disturbance is described by a parameter called the measurement strength.

In quantum computing, Mølmer–Sørensen gate scheme refers to an implementation procedure for various multi-qubit quantum logic gates used mostly in trapped ion quantum computing. This procedure is based on the original proposition by Klaus Mølmer and Anders Sørensen in 1999-2000.

In quantum physics, the "monogamy" of quantum entanglement refers to the fundamental property that it cannot be freely shared between arbitrarily many parties.

The entanglement of formation is a quantity that measures the entanglement of a bipartite quantum state.

References

M. Hein; J. Eisert; H. J. Briegel (2004). "Multiparty entanglement in graph states". Physical Review A . 69 (6): 062311. arXiv: quant-ph/0307130 . Bibcode:2004PhRvA..69f2311H. doi:10.1103/PhysRevA.69.062311. S2CID 108290803.
S. Anders; H. J. Briegel (2006). "Fast simulation of stabilizer circuits using a graph-state representation". Physical Review A . 73 (2): 022334. arXiv: quant-ph/0504117 . Bibcode:2006PhRvA..73b2334A. doi:10.1103/PhysRevA.73.022334. S2CID 12763101.
M. Van den Nest; J. Dehaene; B. De Moor (2005). "Local unitary versus local Clifford equivalence of stabilizer states". Physical Review A. 71 (6): 062323. arXiv: quant-ph/0411115 . Bibcode:2005PhRvA..71f2323V. doi:10.1103/PhysRevA.71.062323. S2CID 119466090.

1 2 3 Hein M.; Dür W.; Eisert J.; Raussendorf R.; Van den Nest M.; Briegel H.-J. (2006). "Entanglement in graph states and its applications". Proceedings of the International School of Physics "Enrico Fermi". 162 (Quantum Computers, Algorithms and Chaos): 115–218. arXiv: quant-ph/0602096 . Bibcode:2006quant.ph..2096H. doi:10.3254/978-1-61499-018-5-115. ISSN 0074-784X.
↑ Looi, Shiang Yong; Yu, Li; Gheorghiu, Vlad; Griffiths, Robert B. (2008-10-07). "Quantum-error-correcting codes using qudit graph states". Physical Review A. 78 (4). American Physical Society (APS). arXiv: 0712.1979 . doi: 10.1103/physreva.78.042303 . ISSN 1050-2947.
↑ Van den Nest, Maarten; Dehaene, Jeroen; De Moor, Bart (2004-09-17). "Efficient algorithm to recognize the local Clifford equivalence of graph states". Physical Review A. 70 (3): 034302. arXiv: quant-ph/0405023 . Bibcode:2004PhRvA..70c4302V. doi:10.1103/PhysRevA.70.034302. ISSN 1050-2947. S2CID 35190821.
↑ Cabello, Adán; López-Tarrida, Antonio J.; Moreno, Pilar; Portillo, José R. (2009). "Entanglement in eight-qubit graph states". Physics Letters A. 373 (26). Elsevier BV: 2219–2225. arXiv: 0812.4625 . doi: 10.1016/j.physleta.2009.04.055 . ISSN 0375-9601.
↑ Adcock, Jeremy C.; Morley-Short, Sam; Dahlberg, Axel; Silverstone, Joshua W. (2020-08-07). "Mapping graph state orbits under local complementation". Quantum. 4. Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften: 305. arXiv: 1910.03969 . doi: 10.22331/q-2020-08-07-305 . ISSN 2521-327X.
↑ Ji, Z.-F.; Chen, J.-X.; Wei, Z.-H.; Ying, M.-S. (2010). "The LU-LC conjecture is false". Quantum Information and Computation. 10 (1&2). Rinton Press: 97–108. doi:10.26421/qic10.1-2-8. ISSN 1533-7146.
1 2 Tóth, Géza; Gühne, Otfried (17 February 2005). "Detecting Genuine Multipartite Entanglement with Two Local Measurements". Physical Review Letters. 94 (6): 060501. arXiv: quant-ph/0405165 . Bibcode:2005PhRvL..94f0501T. doi:10.1103/PhysRevLett.94.060501. PMID 15783712. S2CID 13371901.
1 2 3 Tóth, Géza; Gühne, Otfried (29 August 2005). "Entanglement detection in the stabilizer formalism". Physical Review A. 72 (2): 022340. arXiv: quant-ph/0501020 . Bibcode:2005PhRvA..72b2340T. doi:10.1103/PhysRevA.72.022340. S2CID 56269409.
↑ Kiesel, Nikolai; Schmid, Christian; Weber, Ulrich; Tóth, Géza; Gühne, Otfried; Ursin, Rupert; Weinfurter, Harald (16 November 2005). "Experimental Analysis of a Four-Qubit Photon Cluster State". Physical Review Letters. 95 (21). arXiv: quant-ph/0508128 . doi:10.1103/PhysRevLett.95.210502.
↑ Alba, Emilio; Tóth, Géza; García-Ripoll, Juan José (21 December 2010). "Mapping the spatial distribution of entanglement in optical lattices". Physical Review A. 82 (6). arXiv: 1007.0985 . doi:10.1103/PhysRevA.82.062321.
↑ Scarani, Valerio; Acín, Antonio; Schenck, Emmanuel; Aspelmeyer, Markus (18 April 2005). "Nonlocality of cluster states of qubits". Physical Review A. 71 (4): 042325. arXiv: quant-ph/0405119 . Bibcode:2005PhRvA..71d2325S. doi:10.1103/PhysRevA.71.042325. S2CID 4805039.
↑ Gühne, Otfried; Tóth, Géza; Hyllus, Philipp; Briegel, Hans J. (14 September 2005). "Bell Inequalities for Graph States". Physical Review Letters. 95 (12): 120405. arXiv: quant-ph/0410059 . Bibcode:2005PhRvL..95l0405G. doi:10.1103/PhysRevLett.95.120405. PMID 16197057. S2CID 5973814.
↑ Tóth, Géza; Gühne, Otfried; Briegel, Hans J. (2 February 2006). "Two-setting Bell inequalities for graph states". Physical Review A. 73 (2): 022303. arXiv: quant-ph/0510007 . Bibcode:2006PhRvA..73b2303T. doi:10.1103/PhysRevA.73.022303. S2CID 108291031.
↑ Gottesman, Daniel (1 September 1996). "Class of quantum error-correcting codes saturating the quantum Hamming bound". Physical Review A. 54 (3): 1862–1868. arXiv: quant-ph/9604038 . Bibcode:1996PhRvA..54.1862G. doi:10.1103/PhysRevA.54.1862. PMID 9913672. S2CID 16407184.

External links

Quantum graph states: two equivalent definitions

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Hein2006-1] 1 2 3 Hein M.; Dür W.; Eisert J.; Raussendorf R.; Van den Nest M.; Briegel H.-J. (2006). "Entanglement in graph states and its applications". Proceedings of the International School of Physics "Enrico Fermi". 162 (Quantum Computers, Algorithms and Chaos): 115–218. arXiv: quant-ph/0602096 . Bibcode:2006quant.ph..2096H. doi:10.3254/978-1-61499-018-5-115. ISSN 0074-784X.

[j552-2] Looi, Shiang Yong; Yu, Li; Gheorghiu, Vlad; Griffiths, Robert B. (2008-10-07). "Quantum-error-correcting codes using qudit graph states". Physical Review A. 78 (4). American Physical Society (APS). arXiv: 0712.1979 . doi: 10.1103/physreva.78.042303 . ISSN 1050-2947.

[3] Van den Nest, Maarten; Dehaene, Jeroen; De Moor, Bart (2004-09-17). "Efficient algorithm to recognize the local Clifford equivalence of graph states". Physical Review A. 70 (3): 034302. arXiv: quant-ph/0405023 . Bibcode:2004PhRvA..70c4302V. doi:10.1103/PhysRevA.70.034302. ISSN 1050-2947. S2CID 35190821.

[e981-4] Cabello, Adán; López-Tarrida, Antonio J.; Moreno, Pilar; Portillo, José R. (2009). "Entanglement in eight-qubit graph states". Physics Letters A. 373 (26). Elsevier BV: 2219–2225. arXiv: 0812.4625 . doi: 10.1016/j.physleta.2009.04.055 . ISSN 0375-9601.

[h272-5] Adcock, Jeremy C.; Morley-Short, Sam; Dahlberg, Axel; Silverstone, Joshua W. (2020-08-07). "Mapping graph state orbits under local complementation". Quantum. 4. Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften: 305. arXiv: 1910.03969 . doi: 10.22331/q-2020-08-07-305 . ISSN 2521-327X.

[l899-6] Ji, Z.-F.; Chen, J.-X.; Wei, Z.-H.; Ying, M.-S. (2010). "The LU-LC conjecture is false". Quantum Information and Computation. 10 (1&2). Rinton Press: 97–108. doi:10.26421/qic10.1-2-8. ISSN 1533-7146.

[PRL2005Detecting-7] 1 2 Tóth, Géza; Gühne, Otfried (17 February 2005). "Detecting Genuine Multipartite Entanglement with Two Local Measurements". Physical Review Letters. 94 (6): 060501. arXiv: quant-ph/0405165 . Bibcode:2005PhRvL..94f0501T. doi:10.1103/PhysRevLett.94.060501. PMID 15783712. S2CID 13371901.

[PRA2005Entanglement-8] 1 2 3 Tóth, Géza; Gühne, Otfried (29 August 2005). "Entanglement detection in the stabilizer formalism". Physical Review A. 72 (2): 022340. arXiv: quant-ph/0501020 . Bibcode:2005PhRvA..72b2340T. doi:10.1103/PhysRevA.72.022340. S2CID 56269409.

[9] Kiesel, Nikolai; Schmid, Christian; Weber, Ulrich; Tóth, Géza; Gühne, Otfried; Ursin, Rupert; Weinfurter, Harald (16 November 2005). "Experimental Analysis of a Four-Qubit Photon Cluster State". Physical Review Letters. 95 (21). arXiv: quant-ph/0508128 . doi:10.1103/PhysRevLett.95.210502.

[10] Alba, Emilio; Tóth, Géza; García-Ripoll, Juan José (21 December 2010). "Mapping the spatial distribution of entanglement in optical lattices". Physical Review A. 82 (6). arXiv: 1007.0985 . doi:10.1103/PhysRevA.82.062321.

[11] Scarani, Valerio; Acín, Antonio; Schenck, Emmanuel; Aspelmeyer, Markus (18 April 2005). "Nonlocality of cluster states of qubits". Physical Review A. 71 (4): 042325. arXiv: quant-ph/0405119 . Bibcode:2005PhRvA..71d2325S. doi:10.1103/PhysRevA.71.042325. S2CID 4805039.

[12] Gühne, Otfried; Tóth, Géza; Hyllus, Philipp; Briegel, Hans J. (14 September 2005). "Bell Inequalities for Graph States". Physical Review Letters. 95 (12): 120405. arXiv: quant-ph/0410059 . Bibcode:2005PhRvL..95l0405G. doi:10.1103/PhysRevLett.95.120405. PMID 16197057. S2CID 5973814.

[13] Tóth, Géza; Gühne, Otfried; Briegel, Hans J. (2 February 2006). "Two-setting Bell inequalities for graph states". Physical Review A. 73 (2): 022303. arXiv: quant-ph/0510007 . Bibcode:2006PhRvA..73b2303T. doi:10.1103/PhysRevA.73.022303. S2CID 108291031.

[14] Gottesman, Daniel (1 September 1996). "Class of quantum error-correcting codes saturating the quantum Hamming bound". Physical Review A. 54 (3): 1862–1868. arXiv: quant-ph/9604038 . Bibcode:1996PhRvA..54.1862G. doi:10.1103/PhysRevA.54.1862. PMID 9913672. S2CID 16407184.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]