# Graph state

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_state
> Markdown URL: https://mediated.wiki/source/Graph_state.md
> Source: https://en.wikipedia.org/wiki/Graph_state
> Source revision: 1322172993
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Concept in quantum computing}}
{{more footnotes needed|date=October 2015}}
In [quantum computing](/source/quantum_computing), a '''graph state''' is a special type of multi-[qubit](/source/qubit) state that can be represented by a [graph](/source/Graph_(discrete_mathematics)). Each qubit is represented by a [vertex](/source/Vertex_(graph_theory)) 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](/source/Entanglement_(graph_measure)) states.

Graph states are useful in [quantum error-correcting code](/source/quantum_error-correcting_code)s, 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](/source/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 <math>G = (V, E)</math>, with the set of [vertices](/source/vertex_(graph_theory)) <math>V</math> and the set of [edges](/source/Glossary_of_graph_theory) <math>E</math>, the corresponding graph state is defined as

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

where <math>{\left| + \right\rangle} = \frac{1}{\sqrt{2}}({\left| 0 \right\rangle} +{\left| 1 \right\rangle} )</math> and the operator <math>U^{\{ a,b\} }</math> is the [controlled-''Z''](/source/Quantum_gate) interaction between the two vertices (corresponding to two qubits) <math>a</math> and <math>b</math>

:<math>  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]</math>

=== Stabilizer formalism definition ===

An alternative and equivalent definition is the following, which makes use of the [stabilizer formalism](/source/stabilizer_formalism).

Define an operator <math>S_v</math> for each vertex <math>v</math> of <math>G</math>:

:<math>S_v =\sigma _{x}^{(v)} \prod _{u \in N(v)} \sigma _{z}^{(u)}    </math>

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

:<math>S_v {\left| G \right\rangle} = {\left| G \right\rangle}</math>

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.<ref name="Hein2006">{{Cite journal|last1=Hein M.|last2=Dür W.|last3=Eisert J.|last4=Raussendorf R.|last5=Van den Nest M.|last6=Briegel H.-J.|date=2006|title=Entanglement in graph states and its applications|journal=Proceedings of the International School of Physics "Enrico Fermi"|volume=162|issue=Quantum Computers, Algorithms and Chaos|pages=115–218|doi=10.3254/978-1-61499-018-5-115|arxiv=quant-ph/0602096|bibcode=2006quant.ph..2096H|issn=0074-784X}}</ref><ref name="j552">{{cite journal | last1=Looi | first1=Shiang Yong | last2=Yu | first2=Li | last3=Gheorghiu | first3=Vlad | last4=Griffiths | first4=Robert B. | title=Quantum-error-correcting codes using qudit graph states | journal=Physical Review A | publisher=American Physical Society (APS) | volume=78 | issue=4 | date=2008-10-07 | issn=1050-2947 | doi=10.1103/physreva.78.042303 | doi-access=free | article-number=042303| arxiv=0712.1979 }}</ref>

== Examples ==

* If <math>G = P_3</math> is a three-vertex [path](/source/Path_graph), then the <math>S_v</math> stabilizers are

:<math>
\begin{align}
\sigma_x \otimes {}&\sigma_z \otimes I, \\
\sigma_z \otimes {}&\sigma_x \otimes \sigma_z, \\
       I \otimes {}&\sigma_z \otimes \sigma_x
\end{align}
</math>

The corresponding quantum state is

: <math>{\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}
)</math>

* If <math>G = K_3</math> is a [triangle](/source/Triangle_graph) on three vertices, then the <math>S_v</math> stabilizers are

:<math>
\begin{align}
\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{align}
</math>

The corresponding quantum state is

: <math>{\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} 
)</math>

Observe that <math>{\left| P_3 \right\rangle}</math> and <math>{\left| K_3 \right\rangle}</math> are locally equivalent to each other, i.e., can be mapped to each other by applying one-qubit unitary transformations.  Indeed, switching <math>\sigma_x</math> and <math>\sigma_y</math> on the first and last qubits, while switching <math>\sigma_y</math> and <math>\sigma_z</math> 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](/source/Clifford_group), the two states are called locally Clifford equivalent. [If and only if](/source/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".<ref>{{Cite journal|last1=Van den Nest|first1=Maarten|last2=Dehaene|first2=Jeroen|last3=De Moor|first3=Bart|date=2004-09-17|title=Efficient algorithm to recognize the local Clifford equivalence of graph states|url=https://link.aps.org/doi/10.1103/PhysRevA.70.034302|journal=Physical Review A|language=en|volume=70|issue=3|article-number=034302|doi=10.1103/PhysRevA.70.034302|arxiv=quant-ph/0405023|bibcode=2004PhRvA..70c4302V|s2cid=35190821|issn=1050-2947}}</ref> 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.<ref name="Hein2006"/><ref name="e981">{{cite journal | last1=Cabello | first1=Adán | last2=López-Tarrida | first2=Antonio J. | last3=Moreno | first3=Pilar | last4=Portillo | first4=José R. | title=Entanglement in eight-qubit graph states | journal=Physics Letters A | publisher=Elsevier BV | volume=373 | issue=26 | year=2009 | issn=0375-9601 | doi=10.1016/j.physleta.2009.04.055 | doi-access=free | pages=2219–2225| arxiv=0812.4625 }}</ref><ref name="h272">{{cite journal | last1=Adcock | first1=Jeremy C. | last2=Morley-Short | first2=Sam | last3=Dahlberg | first3=Axel | last4=Silverstone | first4=Joshua W. | title=Mapping graph state orbits under local complementation | journal=Quantum | publisher=Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften | volume=4 | date=2020-08-07 | issn=2521-327X | doi=10.22331/q-2020-08-07-305 | doi-access=free | page=305| arxiv=1910.03969 }}</ref> However, local Clifford equivalence of graph states only coincides with local unitary equivalence for small graph states<ref name="Hein2006"/> and is generally not identical.<ref name="l899">{{cite journal | last1=Ji | first1=Z.-F. | last2=Chen | first2=J.-X. | last3=Wei | first3=Z.-H. | last4=Ying | first4=M.-S. | title=The LU-LC conjecture is false | journal=Quantum Information and Computation | publisher=Rinton Press | volume=10 | issue=1&2 | year=2010 | issn=1533-7146 | doi=10.26421/qic10.1-2-8 | pages=97–108}}</ref>

== 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](/source/Fidelity_of_quantum_states) with respect to a <math>N</math>-qubit graph state <math>|G_N\rangle</math> is given by 

<math> F_{GN}={\rm Tr}(\rho |G_N\rangle\langle G_N|), </math>

It has been shown that if <math>F_{GN}>1/2</math> for a nontrivial graph state corresponding to a connected graph, then the state <math>\rho</math> has genuine multiparticle entanglement.<ref name="PRL2005Detecting">{{cite journal |last1=Tóth |first1=Géza |last2=Gühne |first2=Otfried |title=Detecting Genuine Multipartite Entanglement with Two Local Measurements |journal=Physical Review Letters |date=17 February 2005 |volume=94 |issue=6 |article-number=060501 |doi=10.1103/PhysRevLett.94.060501|pmid=15783712 |arxiv=quant-ph/0405165 |bibcode=2005PhRvL..94f0501T |s2cid=13371901 }}
</ref><ref name="PRA2005Entanglement">{{cite journal |last1=Tóth |first1=Géza |last2=Gühne |first2=Otfried |title=Entanglement detection in the stabilizer formalism |journal=Physical Review A |date=29 August 2005 |volume=72 |issue=2 |article-number=022340 |doi=10.1103/PhysRevA.72.022340|arxiv=quant-ph/0501020 |bibcode=2005PhRvA..72b2340T |s2cid=56269409 }}</ref> 
Thus, one can obtain an [entanglement witness](/source/entanglement_witness) detecting entanglement close the graph states as

<math> W_{GN}=\frac1 2 {\rm Identity}- |G_N\rangle\langle G_N|. </math>

where <math> \langle W_{GN} \rangle <0 </math> 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](/source/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.<ref name="PRL2005Detecting" /><ref name="PRA2005Entanglement" /> Similar conditions can also be used to put a lower bound on the fidelity with respect to an ideal graph state.<ref name="PRA2005Entanglement" /> 
These criteria have been used first in an experiment realizing four-qubit cluster states with photons.<ref>{{cite journal |last1=Kiesel |first1=Nikolai |last2=Schmid |first2=Christian |last3=Weber |first3=Ulrich |last4=Tóth |first4=Géza |last5=Gühne |first5=Otfried |last6=Ursin |first6=Rupert |last7=Weinfurter |first7=Harald |title=Experimental Analysis of a Four-Qubit Photon Cluster State |journal=Physical Review Letters |date=16 November 2005 |volume=95 |issue=21 |article-number=210502 |doi=10.1103/PhysRevLett.95.210502|pmid=16384122 |arxiv=quant-ph/0508128 }}</ref> 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.<ref>{{cite journal |last1=Alba |first1=Emilio |last2=Tóth |first2=Géza |last3=García-Ripoll |first3=Juan José |title=Mapping the spatial distribution of entanglement in optical lattices |journal=Physical Review A |date=21 December 2010 |volume=82 |issue=6 |article-number=062321 |doi=10.1103/PhysRevA.82.062321|arxiv=1007.0985 }}</ref>

Bell inequalities have also been developed for cluster states and graph states.<ref>{{cite journal |last1=Scarani |first1=Valerio |last2=Acín |first2=Antonio |last3=Schenck |first3=Emmanuel |last4=Aspelmeyer |first4=Markus |title=Nonlocality of cluster states of qubits |journal=Physical Review A |date=18 April 2005 |volume=71 |issue=4 |article-number=042325 |arxiv=quant-ph/0405119| doi=10.1103/PhysRevA.71.042325|bibcode=2005PhRvA..71d2325S |s2cid=4805039 |url=https://archive-ouverte.unige.ch/unige:47355 }}</ref><ref>{{cite journal |last1=Gühne |first1=Otfried |last2=Tóth |first2=Géza |last3=Hyllus |first3=Philipp |last4=Briegel |first4=Hans J. |title=Bell Inequalities for Graph States |journal=Physical Review Letters |date=14 September 2005 |volume=95 |issue=12 |article-number=120405 |doi=10.1103/PhysRevLett.95.120405|pmid=16197057 |arxiv=quant-ph/0410059 |bibcode=2005PhRvL..95l0405G |s2cid=5973814 }}</ref><ref>{{cite journal |last1=Tóth |first1=Géza |last2=Gühne |first2=Otfried |last3=Briegel |first3=Hans J. |title=Two-setting Bell inequalities for graph states |journal=Physical Review A |date=2 February 2006 |volume=73 |issue=2 |article-number=022303 |doi=10.1103/PhysRevA.73.022303|arxiv=quant-ph/0510007 |bibcode=2006PhRvA..73b2303T |s2cid=108291031 }}</ref> All these entanglement conditions and Bell inequalities are based on the stabilizer formalism.<ref>{{cite journal |last1=Gottesman |first1=Daniel |title=Class of quantum error-correcting codes saturating the quantum Hamming bound |journal=Physical Review A |date=1 September 1996 |volume=54 |issue=3 |pages=1862–1868 |doi=10.1103/PhysRevA.54.1862|pmid=9913672 |arxiv=quant-ph/9604038 |bibcode=1996PhRvA..54.1862G |s2cid=16407184 }}</ref>

== See also ==
* [Entanglement](/source/Entanglement_(graph_measure))
* [Cluster state](/source/Cluster_state)
* [One-way quantum computer](/source/One-way_quantum_computer)

==References==
* {{cite journal |author1=M. Hein |author2=J. Eisert |author3=H. J. Briegel | title=Multiparty entanglement in graph states| journal=[Physical Review A](/source/Physical_Review_A) | year=2004| volume=69 |issue=6 | article-number=062311 | doi=10.1103/PhysRevA.69.062311|arxiv=quant-ph/0307130|bibcode=2004PhRvA..69f2311H|s2cid=108290803 }}
* {{cite journal |author1=S. Anders |author2=H. J. Briegel | title=Fast simulation of stabilizer circuits using a graph-state representation| journal=[Physical Review A](/source/Physical_Review_A) | year=2006| volume=73 |issue=2 | article-number=022334 | doi=10.1103/PhysRevA.73.022334  | arxiv=quant-ph/0504117| bibcode=2006PhRvA..73b2334A|s2cid=12763101 }}
* {{cite journal |author1=M. Van den Nest|author2=J. Dehaene|author3=B. De Moor | title=Local unitary versus local Clifford equivalence of stabilizer states| journal=Physical Review A | year=2005| volume=71 |issue=6| article-number=062323 | doi=10.1103/PhysRevA.71.062323  | arxiv=quant-ph/0411115| bibcode=2005PhRvA..71f2323V|s2cid=119466090}}

<references />

==External links==
*[https://www.hashpi.com/quantum-graph-states-two-equivalent-definitions Quantum graph states: two equivalent definitions]

Category:Quantum information science
Category:Quantum states

---
Adapted from the Wikipedia article [Graph state](https://en.wikipedia.org/wiki/Graph_state) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_state?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.