Graph state

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 2-uniform hypergraph state, a generalization where the edges have N cardinality.

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 ${\displaystyle G=(V,E)}$, with the set of vertices ${\displaystyle V}$ and the set of edges ${\displaystyle E}$, the corresponding graph state is defined as

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

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

${\displaystyle 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 ${\displaystyle S_{v}}$ for each vertex ${\displaystyle v}$ of ${\displaystyle G}$:

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

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

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

Equivalence between the two definitions

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

Examples

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

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle G=K_{3}}$ is a triangle on three vertices, then the ${\displaystyle S_{v}}$ stabilizers are

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle {\left|P_{3}\right\rangle }}$ and ${\displaystyle {\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 ${\displaystyle \sigma _{x}}$ and ${\displaystyle \sigma _{y}}$ on the first and last qubits, while switching ${\displaystyle \sigma _{y}}$ and ${\displaystyle \sigma _{z}}$ on the middle qubit, maps the stabilizer group of one into that of the other.

More generally, two graph states are locally equivalent if and only if the corresponding graphs are related by a sequence of so-called "local complementation" steps, as shown by Van den Nest et al. (2005). ^[2]

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 ${\displaystyle N}$-qubit graph state ${\displaystyle |G_{N}\rangle }$ is given by

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

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

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

where ${\displaystyle \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. ^{[3] [4]} Similar conditions can also be used to put a lower bound on the fidelity with respect to an ideal graph state. ^[4] These criteria have been used first in an experiment realizing four-qubit cluster states with photons. ^[5] 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. ^[6]

Bell inequalities have also been developed for cluster states. ^{[7] [8] [9]} All these entanglement conditions and Bell inequalities are based on the stabilizer formalism. ^[10]

See also

• Entanglement
• Cluster 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. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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). doi:10.1103/PhysRevA.82.062321.
7. 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.
8. 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.
9. 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.
10. 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