Local equivalence of graph states – Open Quantum Problems

Cite this problem as Problem 28.

Problem

Decide whether two graph states, which can be mapped into each other by a local unitary, can also be mapped into each other by a local unitary from the Clifford group.

Background

Graph states [1] are multiparticle states which are associated with graphs. Each vertex of the graph corresponds to a qubit. The links describe contributions to the phase of the vector components in computational basis:

$\langle q_1,q_2,\cdots,q_n|\psi\rangle=2^{-n/2} \prod_{\text{edges}\, i,j} (-1)^{q_i q_j},$

where each $q_i\!\,=0,1$ . They can also be characterized [2] by eigenvalue equations of stabilizer form

$X^{(i)} \prod_{j:\,\text{edge}\, i,j} Z^{(j)}\quad\psi=\psi,$

where $X^{\!\,(i)}$ and $Z^{(\!\,i)}$ stand for the x- and z-Pauli matrices at vertex $i\!\,$ . The Pauli operators which leave the vector $\psi\!\,$ invariant generate the ”stabilizer group” of the graph state.

*The ”Clifford group” consists of those unitary operators $U\!\,$ , such that $UP\!\,U^*$ is a multiple of a Pauli matrix, whenever $P\!\,$ is a Pauli matrix. This group is generated by the Hadamard matrix $\!\,H$ , the phase gate $\!\,K$

$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1 & 1 \\1 & -1\end{array}\right)\quad,\quad K=\left(\begin{array}{cc}1 & 0 \\0 & i\end{array}\right)$

and the Pauli matrices themselves.

The notion of graph states and the Clifford group can be generalized in a natural way to non-binary systems [1].

Partial Results

A complete set of invariants for locally unitary equivalent qubit graph states isgiven by Van den Nest et al. [3]. A complete set of invariants of the local Clifford group is also known [4][5]. However, the relation between these two invariants is still unclear. At least for the qubit case it is conjectured that a complete family of local Clifford invariants exists which is contained in the class of local unitary invariants.

It has been shown by Van den Nest et al. [6] that for a particular class of qubit graph states local unitary equivalence implies local Clifford equivalence. This class consists of graph states for which stabilizer group S has a particular structure. For instance, all stabilizer states that can be derived from a GL(4)-linear code belong to this class.

Examples which do not belong to this class are generalized GHZ states that correspond to star shaped graphs, i. e. one of the qubits is connected with each of the remaining qubits. Nevertheless it has been shown in [6] that local unitary equivalence implies local Clifford equivalence also in this case.

As outlined by Hein et al. [2], numerical results show that local Clifford equivalence coincides with local unitary equivalence for qubit graph states associated with connected graphs up to 7 vertices.

In his diploma thesis [7], Gross showed that every local unitary which maps some graph state to some other graph state is necessarily semi-Clifford. A unitary is semi-Clifford if it maps at least one Pauli matrix to another Pauli matrix. The result is detailed in [8]. It follows that when trying to decide the LU-LC problem, one can restrict attention to diagonal local unitaries.

Also, in [8] Gross and Van den Nest showed that LU equivalence would coincide with LC equivalence if a certain statement about quadratic forms over GF(2) were true. The converse holds up to an extra assumption below. Indeed, if the statement about quadratic forms were wrong, then there would be graph states which can be mapped onto each other by diagonal local unitaries, but not by diagonal local Clifford operations. The extra assumptions now amounts to saying that if two graph states are related under the action of a diagonal local unitary, then they can be mapped onto each other either by a diagonal local Clifford or by no local Clifford at all.

Solution

The problem was all but decided in [9], where Ji et al disproved the mentioned conjecture about quadratic forms by providing an explicit counter-example. It is associated with a stabilizer on 27 qubit and has been found by a systematic computer search.

References

[1] D.-M. Schlingemann, Cluster states, graphs and algorithms, Quant. Inf. Comp. 4, 287 (2004) and [1] quant-ph/0305170 (2003).

[2] M. Hein, J. Eisert and H. J. Briegel, Multi-party entanglement in graph states, Phys. Rev. A 69, 062311 (2004) and [2] quant-ph/0307130 (2003).

[3] M. Van den Nest, J. Dehaene and B. De Moor, Local invariants of stabilizer codes, Phys. Rev. A 70, 032323 (2004) and [3] quant-ph/0404106 (2004).

[4] M. Van den Nest, J. Dehaene and B. De Moor, Finite set of invariants to characterize local Clifford equivalence of stabilizer states, Phys. Rev. A 72, 014307 (2005) and [4] quant-ph/0410165 (2004).

[5] M. Van den Nest, J. Dehaene and B. De Moor, An efficient algorithm to recognize local Clifford equivalence of graph states, Phys. Rev. A 70, 034302 (2004) and [5] quant-ph/0405023 (2004).

[6] M. Van den Nest, J. Dehaene and B. De Moor, On local unitary versus local Clifford equivalence of stabilizer states, Phys. Rev. A 71, 062323 (2005) and [6] quant-ph/0411115 (2004).

[7] D. Gross, Finite phase space methods in quantum information, diploma thesis supervised by J. Eisert, University of Potsdam, 2005. Available online at http://gross.qipc.org/] http://gross.qipc.org/.

[8] D. Gross and M. Van den Nest, The LU-LC conjecture, diagonal local operations and quadratic forms over GF(2), Quant. Inf. Comp. 8, 263 (2008) and [7] quant-ph/0707.4000 (2007).

[9] Z. Ji, J. Chen, Z. Wei, and M. Ying, The LU-LC conjecture is false, Quant. Inf. Comp. 10, 1 & 2 (2010) and [8] quant-ph/0709.1266 (2007).