--- abstract: 'We introduce a class of mixed multiqubit states, that corresponds to a randomized version of graph states. Such states arise when a graph state is prepared with noisy or imperfect controlled-$Z$ gates. We study the entanglement features of these states by investigating both bipartite and genuine multipartite entanglement. Bipartite entanglement is studied via the concepts of connectedness and persistency, which are related to measurement based quantum computation. The presence of multipartite entanglement is instead revealed by the use of witness operators which are subsequently adapted to study nonlocal properties through the violation of suitable Bell inequalities. We also present results on the entanglement detection of particular randomized graph states, by deriving explicit thresholds for entanglement and nonlocality in terms of the noise parameter that characterizes the controlled-$Z$ gates exploited for their generation. Finally, we propose a method to further improve the detection of genuine multipartite entanglement in this class of states.' author: - 'Jun-Yi Wu$^{1}$, Matteo Rossi$^{2}$, Hermann Kampermann$^{1}$, Simone Severini$^{3}$, Leong Chuan Kwek$^{4}$, Chiara Macchiavello$^{2}$, Dagmar Bruß$^{1}$' bibliography: - 'Random\_Graph\_States\_and\_Their\_Entanglement\_Properties.bib' title: Randomized Graph States and their Entanglement Properties --- Introduction {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069Introduction} ============ Graph states and especially cluster states are at the heart of measurement based quantum computation (MBQC) @RaussBrie2001-5. Given a cluster state, this prominent model of quantum computation provides a way to perform universal computing with only local gates and measurements, by avoiding the use of two-qubit entangling gates. Under this light, the entanglement content of cluster states can then be regarded as a quantum resource that is consumed throughout the process. However, despite the fact that all the operations involved in MBQC can nowadays be easily implemented in various hardware, the hardest task from an experimental point of view is represented by the preparation of the initial cluster state. The preparation of general graph states always starts from a product state of qubits corresponding to the vertices of a graph with no edges, which is then subsequently processed via an Ising-like interaction <span>BriegelRaussendorf2001-01</span>. This interaction is tuned in such a way that its action can be regarded as a series of controlled-$Z$ (CZ) gates, connecting the vertices according to the target graph. In Ref. <span>Cabello2011-04</span> a preparation method involving only one- and two-qubit gates for graph states up to $12$ qubits is proposed. As a matter of fact, the current experimental realization of a CZ gate is far from being perfect, and in practice it is very difficult to create a noiseless graph state <span>Cabello2011-04</span>. A possible way to model a noisy CZ gate is to assume that, with probability $p$ it creates the desired edge between its qubits, while with probability $1-p$ it fails. For heralded entanglement @lim2005repeat, if the gate fails, one could recover the original state, i.e. $|++\rangle$. This has the same effect as an identity operator. A physical realization of this probabilistic CZ gate was suggested in @lim2005repeat [@lim2006repeat; @beige2007repeat]. In this paper, we aim at studying the *randomized graph state* (for short, RG state), that is, states that arise whenever a probabilistic CZ gate is applied for every edge in a graph. Given a graph state, its randomized version is thus a mixture of all the states corresponding to its subgraphs. These are weighted according to a single parameter $p$, which we call *randomness parameter*, physically related to the success probability of the CZ gate. Besides addressing the issue of the unitary equivalence of general RG states, we will mainly focus on the amount of entanglement in RG states, both in the bipartite and the multipartite case @AcinBLSanpera2001-07. Regarding the former, we will especially discuss the concepts of persistency and connectedness, which have a clear application in terms of the usefulness of RG states for MBQC <span>BriegelRaussendorf2001-01</span>. For the quantification of the latter, we will use a genuine multipartite entanglement witness <span>Bourennane2004-02,GuhneHBELMSanpera2002-12,TothGuhne2005-02</span>. We will be able in this way to define a critical value $p_{c}$ for the randomness parameter, above which the state shows genuine multipartite entanglement properties. Finally, nonlocal realistic features of RG states will be discussed with the help of suitable Bell inequalities developed for graph states. Notice that, not only are RG states interesting and highly non trivial *per se*, but they are a useful tool to investigate and understand the presence of noise in MBQC. Furthermore, complete RG states are a plausible quantum counterpart to the classical Erds-R<span>é</span>nyi random graphs introduced in @ErdosRenyi1959 (Ref. @janson2000_randomgraphs is a detailed survey on the topic), and recently studied in the context of complex systems @Newman2003 [@BoccalettiLMCHwange2006]. The present paper is organized as follows. In Sec. \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069Preliminary\] we review some basic definitions about mathematical graphs, random graphs and quantum graph states. We define randomized graph states in Sec. \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069randomized\_graph\_state\]. We then study the rank of RG states to answer the question of unitary equivalence and bipartite and multipartite entanglement in Secs. \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069unit-eq\], \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069bipartite\_entanglement\], and \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069GME\], respectively. In Sec. \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069GME\], an approximation to a witness for multipartite entanglement is introduced, which allows to determine a threshold probability. A further analysis on nonlocal realism is carried out in Sec. \[sec:bell\]. We conclude in Sec. \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069conclusion\] with a summary of the achieved results and future perspectives. Preliminaries {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069Preliminary} ============= In this section, we briefly review the definition of graphs as used in the paper and the mathematical concept of Erds-R<span>é</span>nyi random graphs. We then remind the reader of the well-known class of quantum graph states and introduce the notation that will be used throughout the paper. Graphs {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069graphs} ------ A *graph* $G=(V,E)$ is defined as a pair consisting of a set $V_{G}=\left\{ v_{1},\cdots ,v_{n}\right\} $, whose elements are called *vertices,* and a set $E_{G}=\left\{ e_{1},\cdots ,e_{l}\right\} $, whose elements are called *edges* and consist of unordered pairs of different vertices @Diestel_GraphTheory. A graph $F$ with $V_{F}\subseteq V_{G}$ and $E_{F}\subseteq E_{G}$ is called a *subgraph* of $G$. If $V_{F}=V_{G}$ then $F$ is said to be a *spanning subgraph* of $G$; in such a case, we say that $F$ *spans* $G$. Two vertices are *neighbors* if they are connected by an edge. The *degree* of a vertex $v_{i}$, $d_{v_{i}}$, is the number of its neighbors. A graph is *empty* if it has no edges. The empty graph on $n$ vertices is denoted by $G_{n}^{\emptyset }$. On the other hand, the *complete* (or fully connected) graph on $n$ vertices, $K_{n}$, contains all possible $\binom{n}{2}$ edges. Other relevant types of graphs that will be considered along the paper are the following ones: - *Star graphs*, $S_{n}$: graphs where one vertex has degree $n-1$ and all others have degree $1$. - *Cluster graphs*, $L_{m\times n}$: graphs whose vertices correspond to the points of a discrete two-dimensional lattice with $m$ times $n$. When $m=1$, we simply write $L_{n}$. This is a *linear cluster*, or, equivalently, a path on $n$ vertices. Notice that in the graph-theoretic literature $L_{m\times n}$ is usually called a grid graph or a lattice graph. We use a different terminology given the link with MBQC. - *Cycle graphs*, $C_{n}$: graphs where all vertices have degree $2$. These are closed linear clusters. A very useful concept in the remainder of the paper is the symmetric difference. Letting $F$ and $G$ be two graphs on the same set of vertices $V$, their *symmetric difference* is the graph $F\Delta G$, such that $V_{F\Delta G}=V_{F}=V_{G}$ and $E_{F\Delta G}=E_{F}\cup E_{G} \setminus E_{F}\cap E_{G} $. Erds-R<span>é</span>nyi random graphs ------------------------------------- Random graphs are a well-developed mathematical subject touching both graph theory and probability theory <span>** **</span>@janson2000_randomgraphs. In the Erds-R<span>é</span>nyi (ER) random graph on $n$ vertices, each edge is included with probability $p$ independently of any other edge. Notice that, as $p$ is uniform for all edges, then the probability of a subgraph $G\subseteq K_{n}$ with a number of edges $|E_{G}|$ is given by $P(G)=p^{|E_{G}|}(1-p)^{\binom{n}{2}-|E_{G}|}$. As an illustration, Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069random\_subgraphs\] shows all possible subgraphs of the complete graph $K_{3}$. Graph states {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069graph_state} ------------ We will briefly review here the well known concept of a graph state of $n$ qubits and its connection to graphs @HeinEisertBriegel2004-06 [@hein2006entanglement]. Given a graph $G=(V,E)$ on $n$ vertices, the corresponding graph state is denoted by $|G\rangle $ and defined as follows. First, assign to each vertex a qubit and initialize it as the state $|+\rangle =\frac{1}{\sqrt{2}}(|0\rangle +|1\rangle )$, so that the initial $n$-qubit state is given by $|+\rangle ^{\otimes n}$. Then, perform a CZ operation between any two qubits associated to vertices that are connected by an edge. This operation is defined as $\mathrm{CZ}=\mathrm{diag}(1,1,1,-1)$, in the computational basis $\{|0\rangle ,|1\rangle \}$ for each qubit. By performing the CZ operation on any two connected qubits $i_{1}$ and $i_{2}$, we get the corresponding graph state $$|G\rangle :=\prod_{\{i_{1},i_{2}\}\in E}(\text{CZ})_{i_{1}i_{2}}|+\rangle ^{\otimes n}. \label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069_graphstate}$$Notice that the number of distinct graph states of $n$ qubits is equal to $2^{\binom{n}{2}}$, which is the number of labeled graphs with $n$ vertices. Randomized Graph States {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069randomized_graph_state} ======================= In this section, we will introduce the class of randomized graph (RG) states. The main idea is to start from a graph $G$ and to apply probabilistic gates $\Lambda _{p}$ to the state $|+\rangle ^{\otimes n}$ instead of the perfect CZ gates. $\Lambda _{p}$ is defined as $$\Lambda _{p}(|++\rangle \langle ++|)=p|\vcenter{\hbox{\includegraphics[width=2em]{pics/bell_2}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/bell_2}}}|+(1-p)|++\rangle \langle ++|, \label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069probabilistic_gate_random_graph_model}$$with $|++\rangle $ representing the two-qubit empty graph state, and $|\vcenter{\hbox{\includegraphics[width=2em]{pics/bell_2}}}\rangle $ denoting the two-qubit connected graph state. In other words, we consider a noisy implementation of the gate CZ, where one realizes the desired CZ gate with probability $p$, but one fails and does nothing with probability $1-p$ <span>lim2005repeat,lim2006repeat,beige2007repeat</span>. Notice that all gates $\Lambda _{p}$ acting on any pair of qubits commute and therefore we do not have to specify the order of application. As an illustration, suppose we want to generate the GHZ state $|\vcenter{\hbox{\includegraphics[width=2em]{pics/GHZ_3}}}\rangle $ by employing the aforementioned procedure, namely by applying the probabilistic gates $\Lambda _{p}$ to create edges. It is easy to see that the resulting state is a mixture of subgraph states of $|\vcenter{\hbox{\includegraphics[width=2em]{pics/GHZ_3}}}\rangle $, namely $$\begin{aligned} R_{p}(|\vcenter{\hbox{\includegraphics[width=2em]{pics/GHZ_3}}}\rangle) & =\Lambda _{p}^{\{1,2\}}\circ \Lambda _{p}^{\{2,3\}}\left( |+++\rangle \langle +++|\right) \nonumber\\ & =p^{2}|\vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_4_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_4_no_label}}}| \notag \\ & +p(1-p)|\vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_3_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_3_no_label}}}|+p(1-p)|\vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_2_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_2_no_label}}}| \notag \\ & +(1-p)^{2}|\vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_1_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/Star3_subgraph_1_no_label}}}|. \label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069RS3_state}\end{aligned}$$The above state is then said to be the RG state associated to the graph $\vcenter{\hbox{\includegraphics[width=2em]{pics/GHZ_3}}}$. The above example shows that the RG state $\rho _{G}^{p}$ associated to a graph $G$, or equivalently to a pure graph state $|G\rangle $, can be derived by applying the randomization operation $R_{p}$ in agreement with the following definition. \[Randomized graph state\] \[def.8b7c:f320:99b9:690f:4595:cd17:293a:c069randomization\_operator\_random\_graph\_state\]Let $|G\rangle $ be a graph state. A *randomization operator* $R_{p}$ is defined via$$R_{p}(|G\rangle ):=\sum_{F \emph{spans} G}p^{|E_{F}|}\left( 1-p\right) ^{\left\vert E_{G}\backslash E_{F}\right\vert }|F\rangle \langle F|, \label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069_randomization_operator_random_graph_state}$$where $F$ are spanning subgraphs of $G$, $E_{F}$ and $E_{G}$ are the sets of edges of $F$ and $G$, and $p$ is the randomness parameter corresponding to the success probability of the CZ gate in Eq. . The resulting state $\rho _{G}^{p}:=R_{p}(|G\rangle )$ is the randomized version of $|G\rangle $ with randomness parameter $p$, or, shortly, a $p$*-randomization* of $|G\rangle $. This randomization operator corresponds to the preparation of graph states showed in the probabilistic gate model of Eq. . It maps a pure graph state $|G\rangle $ into a mixture of all its spanning subgraph states. Since the two extreme cases $p=0,1$ correspond to the empty graph and the pure graph state, respectively, the parameter $p$ plays a fundamental role to determine the entanglement features of RG states. In addition, it is useful to remark a difference between mathematical ER random graphs and RG states: in ER random graphs all possible edges among the vertices are considered; in RG states the randomization is restricted to the edges of a given graph. In other words, ER random graphs are always related to the fully connected graph, while RG states can be generated by the randomization process on any graph. From this viewpoint, we can say that RG states are more general than random graphs, since only in the case of $G=K_{n}$ does the corresponding RG state $\rho _{K_{n}}^{p}$ have the same combinatorial properties as the ER random graph of $n$ vertices. It is then evident that our model is in close analogy with bond percolation. Of course, the questions that we ask are not directly related to the main question in percolation theory, which is traditionally concerned with the global behavior of infinite graphs as a function of the randomness parameter (see @Grimmett1999-percolation). In this paper we will denote the $p$ randomization of the important graph states $|K_{n}\rangle $, $|S_{n}\rangle $, $|L_{n}\rangle $, and $|C_{n}\rangle $ by $\rho _{K_{n}}^{p}$, $\rho _{S_{n}}^{p}$, $\rho _{L_{n}}^{p}$, and $\rho _{C_{n}}^{p}$, respectively. Notice that a different definition of random graph states is also given in @CollinsNechitaZyczkowski2010. In that model, a vertex with degree $d$ is represented by a $d$-qubit system and two vertices $a$ and $b$ are said to be connected by an edge if one qubit in $a$ is maximally entangled with one qubit in $b$. A random unitary matrix describes the coupling between subsystems of a vertex. The random graph states considered in <span>CollinsNechitaZyczkowski2010</span> are then an ensemble of pure states. In contrast, in our definition each vertex is a single-qubit system, and a randomized graph state is always a mixed state for any value of the randomness parameter $0<p<1$. Notice that other ways to define mixed quantum states from graphs have been studied in the literature (see e.g. Ref. @braunstein2006laplacian). Rank of randomized graph states and unitary equivalence {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069unit-eq} ======================================================= In this section, we investigate the question of *local unitary* (LU) equivalence of RG states. Two $n$-qubit quantum states $\rho $ and $\sigma $ are *LU equivalent* if and only if there exist local unitaries $U^{(1)},...,U^{(n)}$ such that $\rho =U^{(1)}\otimes \cdots \otimes U^{(n)}\sigma U^{(1)\dagger }\otimes \cdots \otimes U^{(n)\dagger }$. LU equivalent states have identical entanglement properties. The LU equivalence classes of graph states have been intensively studied in Ref. @HeinEisertBriegel2004-06. Pure graph states up to six qubits can be classified in $19$ different LU classes. Graph states in the same class can be transformed into each other via local unitaries, and hence share the same entanglement properties. However, in most cases the RG states derived from two LU equivalent graph states, say $|G_{1}\rangle $ and $|G_{2}\rangle $, are not LU equivalent and, in general, not even equivalent under *global unitaries* (GU). In order to see this, consider for instance the graph states $|G_{1}\rangle =|\vcenter{\hbox{\includegraphics[width=2em]{pics/GHZ_3}}}\rangle $ and $|G_{2}\rangle =|\vcenter{\hbox{\includegraphics[width=2em]{pics/K_3}}}\rangle $, that are known to be LU equivalent. The corresponding RG states are given by $\rho _{G_{1}}^{p}=R_{p}(|\vcenter{\hbox{\includegraphics[width=2em]{pics/GHZ_3}}}\rangle )$, see Eq. , and $$\begin{aligned} \rho _{G_{2}}^{p}& =p^{3}|\vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_3_edges_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_3_edges_no_label}}}| \notag \label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069RC3_state} \\ & +p^{2}\left( 1-p\right) |\vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_2_edges_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_2_edges_no_label}}}|+\cdots \notag \\ & +p\left( 1-p\right) ^{2}|\vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_1_edges_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_1_edges_no_label}}}|+\cdots \notag \\ & +\left( 1-p\right) ^{3}|\vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_0_edges_no_label}}}\rangle \langle \vcenter{\hbox{\includegraphics[width=2em]{pics/K3_subgraph_0_edges_no_label}}}|\;.\end{aligned}$$For any value of $p\neq 0,1$ the above two states can be shown by direct calculation to have different ranks, namely rank$(\rho _{G_{1}}^{p}) = 4$, and rank$(\rho _{G_{2}}^{p})=5$. Therefore, the RG states $\rho_{G_{1}}^{p}$ and $\rho _{G_{2}}^{p}$, defined starting from LU equivalent graph states, cannot even be transformed into each other by a GU operation. In other words, these are not unitary equivalent and, in particular, not LU equivalent. This reasoning can be generalized to an arbitrary number of qubits by introducing the following concepts: \[$G$-subgraphs state space\] Let $G$ be a graph and $F$ a spanning subgraph of $G$. The space spanned by the states $|F\rangle $ is called $G$*-subgraphs state space* and is denoted as$$\Sigma _{G}:=\text{ \emph{span}}\left( \{|F\rangle \}_{F\subseteq G,V_{F}=V_{G}}\right) .$$ This definition prompts to two observations concerned with the complete graph. The respective proofs are in Appendix <span>s8b7c:f320:99b9:690f:4595:cd17:293a:c069proof\_of\_theorems\_in\_unitary\_equivalence</span>. \[Dimension of $\Sigma _{K_{n}}$\] \[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069imension\_of\_complete\_subgraphs\_state\_space\] The $K_{n}$-subgraphs state space $\Sigma _{K_{n}}$ has dimension $2^{n}-n$. \[Rank of randomized graph states\] \[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069rank\_of\_random\_graph\_states\]The rank of the randomized graph state $\rho^p_{K_{n}}$ is $2^{n}-n$, for all $0<p<1$. A direct consequence of Theorem \[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069rank\_of\_random\_graph\_states\] is that the rank of $\rho^p_{K_{n}}$ is maximum over all RG states of $n$ qubits, as long as $p\neq 0,1$. An interesting question is whether there exists any other randomized graph state $\rho _{G_{n}}$ with maximum rank. The answer is in the negative. This can be explained by the following argument. Suppose we have a graph $G_{n}$ given by the complete graph $K_{n}$ where, without loss of generality, we delete a single edge between vertices $1$ and $2$. It can be easily seen that the state $|1100...00\rangle $ appears with a plus sign in the graph state $|G_{n}\rangle $ and all the corresponding subgraph states. Therefore, the state $|0000...00\rangle -|1100...00\rangle $ cannot be obtained as a superposition of the subgraphs of $G_{n}$ (see the proof of Theorem \[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069imension\_of\_complete\_subgraphs\_state\_space\] in Appendix \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069proof\_of\_theorems\_in\_unitary\_equivalence\] for an explanation). Thus, the rank of $\rho _{G_{n}}$ is always strictly smaller than $2^{n}-n$. The above argument also holds for the case of states that correspond to graphs $G_{n}^{\lnot m}$ with $m$ edges missing with respect to the complete graph, i.e., with $\binom{n}{2}-m$ edges. The rank of the corresponding RG states is then bounded as $$\text{rank}(\rho _{G_{n}^{\lnot m}})\leq 2^{n}-n-m.$$To prove this, the above argument about the state $|1100...00\rangle $ corresponding to $1$'s for the qubits that are not connected by an edge can be repeated for all the other $m$ pairs of qubits where the edges are missing, and the above upper bound then follows. From the above reasoning we can thus infer that the randomized graph state $\rho_{G^{\neg m}_n}$ can never be GU equivalent to $\rho_{K_n}$. An interesting example in this sense is provided by the two graph states ${| K_n \rangle}$ and ${| S_n \rangle}$, which are known to be LU equivalent. As we have observed, rank$(K_n) = 2^n-n$, while, since the star graph $S_n$ can be obtained from the complete graph $K_n$ by deleting $\binom{n-1}{2}$ edges, the rank of $\rho_{S_n}$ can be bounded as $$\text{rank}(\rho _{S_{n}})\leq 2^{n}-n-\binom{n-1}{2}. \label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069rank_of_RS_graph_state}$$This proves that, although the star graph state ${| S_n \rangle}$ and the complete graph state ${| K_n \rangle}$ are LU equivalent, their corresponding RG states $\rho_{S_n}$ and $\rho_{K_n}$ are not even GU equivalent. Bipartite Entanglement {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069bipartite_entanglement} ====================== In this section, we analyze the bipartite entanglement properties of RG states. We show that RG states exhibit some properties which are analogous to bipartite entanglement of pure graph states, while others are different. A pure graph state is entangled regarding a bipartition if there exists at least one edge across the partition. The following proposition shows that the same result holds for RG states. \[prop8b7c:f320:99b9:690f:4595:cd17:293a:c069ipartite\_entanglement\_of\_random\_graph\_states\] Given a graph $G$, let $A$ and $B$ be disjoint subsets such that $A\cup B=V_{G}$. A RG state $\rho_{G}^{p}$ is entangled regarding the bipartition $A|B$, if there exists at least one randomized edge between $A$ and $B$ with randomness $p>0$. Let us first consider the graph state composed of two qubits, namely the Bell state $|\text{Bell}\rangle =|\vcenter{\hbox{\includegraphics[width=2em]{pics/bell_2}}}\rangle$. The RG state $\rho_{\text{Bell}}^{p}$ associated to it is thus given by $$\rho_{\text{Bell}}^{p}=\frac{1}{4}\left( \begin{array} [c]{cccc}1 & 1 & 1 & 1-2p\\ 1 & 1 & 1 & 1-2p\\ 1 & 1 & 1 & 1-2p\\ 1-2p & 1-2p & 1-2p & 1 \end{array} \right) .$$ Since the partial transpose of $\rho_{\text{Bell}}^{p}$ has one negative eigenvalue for $p>0$, $\rho_{\text{Bell}}^{p}$ is entangled whenever $p>0$ @Horodecki1996-11. Let us now move to the general case and show that there is always a nonzero probability to project a given RG state $\rho _{G}^{p}$ onto a randomized Bell state of vertices $a\in A$ and $b\in B$, by using local $\sigma_{z}$ measurements. Notice that this is never possible if $\rho_{G}^{p}$ is separable across the bipartition $A|B$. Recall that a $\sigma_{z}$ measurement on the vertex $v_{i}$ of $|G\rangle$ results in the graph state $|G-v_{i}\rangle\otimes|+\rangle_{v_{i}}$, where all the edges touching the vertex $v_{i}$ have been deleted, whenever the outcome $+1 $ occurs @HeinEisertBriegel2004-06. Therefore, if we now measure all the vertices except $a$ and $b$, i.e., $V\backslash\{a,b\}$, there is a nonvanishing probability that all the outcomes are $+1$, and thus a nonzero probability to delete all the randomized edges of $\rho_{G}^{p}$ except the one between $a\in A$ and $b\in B$. As a result, there is a nonzero probability to obtain a randomized Bell state $\rho_{\text{Bell}}^{p}$ between the vertices $a$ and $b$, which finally shows that the state $\rho_{G}^{p}$ is entangled with respect to $A|B$ for any $p>0$. This shows that, for $p > 0$, RG states show entanglement across any bipartition connected by at least one randomized edge, thus even the action of an imperfect probabilistic CZ gate creates entanglement between the two connected parties. We now consider two different bipartite entanglement properties, namely maximal connectedness and persistency, specifically introduced in @BriegelRaussendorf2001-01 for cluster states, and of particular interest with regard to MBQC. A state is said to be *maximally connected* if we can project any pair of vertices onto a Bell state with certainty, by using only local measurements. The following proposition shows that RG states never enjoy this property. A randomized graph state is never maximally connected for $p<1$. Since for any pair of vertices $\{i,j\}$ there is a nonzero probability that either vertex $i$ or $j$ is isolated, the state cannot be projected onto a Bell state $|\text{Bell}\rangle_{i,j}$ with certainty. The *persistency* $\mathcal{P}$ of a state is instead the minimal number of local measurements needed to completely disentangle the state. In Ref. @BriegelRaussendorf2001-01, it was shown that, while every cluster state is maximally connected, the persistency depends on its specific structure. Results are known for one-dimensional (1D) cluster states $|L_{n}\rangle$, where the persistency $\mathcal{P}$ equals the Schmidt rank $n/2$, and for two- or three-dimensional cluster states where $\mathcal{P}$ approaches $n/2$ only asymptotically. The following proposition shows that the RG state $\rho _{G}^{p}$ is less robust than the graph state $|G\rangle$. The persistency of a randomized graph state $\mathcal{P}(\rho_{G}^{p})$ is always smaller or equal than $\mathcal{P}(|G\rangle)$: $$\mathcal{P}(\rho_{G}^{p})\leq\mathcal{P}(|G\rangle).$$ Let $\mathcal{P}(|G\rangle)=m$, and $\{M_{1},\cdots,M_{m}\}$ be the measurements that totally disentangle $|G\rangle$. Then the same set of measurements $\{M_{1},\cdots,M_{m}\}$ totally disentangles $\rho_{G}^{p}$ too, as it disentangles each spanning subgraph state of $|G\rangle$. Therefore the inequality $\mathcal{P}(\rho_{G}^{p})\leq m$ follows. The two propositions above show that the bipartite entanglement of a given RG state is never as robust as the one of the corresponding pure graph state. This observation is expected, due to the method of construction, and is of particular interest with regard to MBQC. We finally quantify the amount of bipartite entanglement by considering the negativity, evaluated with respect to all possible bipartitions of the qubits. The *negativity* of a bipartite state $\rho_{AB}$ is defined @VidalWerner2002-02 as $$N(\rho_{AB})=\frac{||\rho_{AB}^{\Gamma_{A}}||-1}{2},$$ where $\Gamma_{A}$ represents the partial transposition with respect to the subsystem $A$, and $||X||=\text{Tr}[\sqrt{X^{\dagger}X}]$ is the trace norm. Notice that this is one of the few computable measures of entanglement when mixed states are concerned. We have evaluated the negativity numerically for some RG states composed of a small number of qubits. The results for the negativity of states corresponding to the complete graph $K_{n}$ and the star graph $S_{n}$ up to $n=4 $ vertices are reported in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069monotomicity\_of\_negativity\]. As can be seen, in the studied cases the negativity exhibits a monotonic behaviour in terms of the randomness parameter $p$. This suggests that the entanglement content might increase monotonically in $p$ with respect to any bipartition. Actually, since for the extreme cases $p=0$ and $p=1$ we have a fully separable state and an entangled state, respectively, one might expect that, as the weight of entangled subgraph states in $\rho^{p}_{G}$ increases with increasing $p$, a corresponding growth of the entanglement content of the RG state $\rho^{p}_{G}$. However, even though this conjecture is supported by numerical evidence, it is an open question whether the monotonic behavior of the negativity in terms of the randomness $p$ is a common feature to all RG states. Genuine Multipartite Entanglement {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069GME} ================================= In this section, we consider genuine multipartite entanglement (GME) properties of RG states. We remind the reader that a state which cannot be written as a convex combination of biseparable states is called *genuinely multipartite entangled* (GME) @AcinBLSanpera2001-07. For example, in the case of three qubits, a state $\rho$ is genuinely multipartite entangled, if it can not be expanded in the following decomposition: $$\rho=c_{1}\rho_{1|23}+c_{2}\rho_{2|13}+c_{3}\rho_{3|12},$$ where $\rho_{i|jk}$ is a biseparable state regarding the bipartition $\{i\}|\{jk\}$, and $\sum_{i=1}^{3}c_i=1$, with $c_i \geq 0$. The condition of being genuine multipartite entangled is thus stronger than showing bipartite entanglement. As a direct consequence, the recognition and evaluation of GME becomes much harder, especially for mixed states. Nonetheless some investigations can be still made for RG states. As was the case for bipartite entanglement in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069monotomicity\_of\_negativity\], we expect the randomness parameter $p$ to tune the amount of GME of a connected RG state from zero to its maximum value. Since the two extreme cases $p=0,1$ correspond to a fully separable and a genuine multipartite entangled state, respectively, we wonder whether the GME content of a general RG state $\rho_{G}^{p}$ might still follow a monotonically increasing behavior in terms of $p$. In order to support this intuition, we have followed the PPT mixer approach developed in Ref. @JungnitschMGuhne2011-05. In this approach one uses a semidefinite program to make an optimization over all fully decomposable witnesses. An entanglement witness is a Hermitian operator $W$ such that there exists a $\rho$ with $\text{Tr}[W\rho]<0$ and $\text{Tr}[W\rho_{\mathrm{sep}}]\geq0$ for all separable states $\rho_{\mathrm{sep}}$. A fully decomposable witness $W$ is a witness operator that can be decomposed into two positive semidefinite operators $P_\gamma$ and $Q_\gamma$ for all bipartitions $\gamma$, such that $$W=P_\gamma+Q_\gamma^{\Gamma_\gamma},$$ with Tr$(W)=1$, $P_{\gamma}\geq0$, $Q_{\gamma}\geq0$ and $\Gamma_{\gamma}$ being the partial transpose regarding bipartition $\gamma$. Such a witness is a GME witness, if there exists a GME state $\rho$ with $\text{Tr}[W\rho]<0$, and $\text{Tr}[W\rho']\geq0$ for all non-GME states $\rho'$. With a semi-definite program one can minimize the expectation value Tr($W\rho$) over all fully decomposable witnesses, such that one can numerically calculate the quantity $$E_{\text{pptmixer}}(\rho)=\left\vert \min\left( 0,\min_{W\text{ fully decomp. }}\text{Tr}(W\rho)\right) \right\vert\label{eq.PPT_mixer_ent_monotone}.$$ Since $E_{\text{pptmixer}}$ is an entanglement monotone, it cannot solely detect the presence of GME but also bound the amount of GME @JungnitschMGuhne2011-05. Moreover it turns out to be necessary and sufficient for entanglement detection in permutationally invariant states up to three qubits @NovoMoroderGuhne2013-07, thus leading to a well defined measure of GME. Notice that, for graph states and their randomization, only the ones which are generated by complete graphs are permutationally invariant. Hence we can solely use this PPT mixer approach as GME measure for the three-qubit RG state $\rho_{K_{3}}^{p}$, while as a GME monotone for the other RG states. With the help of the online program @ppt_mixer_online_program, we obtain the numerical results for RG states with three, four and five qubits. These are shown in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pptmixer\_ent\_monotone\]. The behavior of the monotone of GME derived from the PPT mixer is monotonic in $p$, supporting our intuition. Whether the multipartite entanglement of RG states is generally increasing with $p$ remains an open question. ![(Color online) Multipartite entanglement monotone derived from the PPT mixer as a function of the randomness $p$ for RG states up to five qubits; see Eq. ](pics/pptmixer_ent_monotone){width="0.9\linewidth"} ![(Color online) Multipartite entanglement monotone derived from the PPT mixer as a function of the randomness $p$ for RG states up to five qubits; see Eq. ](pics/pptmixer_ent_monotone_1){width="0.9\linewidth"} ![(Color online) Multipartite entanglement monotone derived from the PPT mixer as a function of the randomness $p$ for RG states up to five qubits; see Eq. ](pics/pptmixer_ent_monotone_2){width="0.9\linewidth"} .\[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pptmixer\_ent\_monotone\] If the quantity $\text{Tr}[W\rho_G^p]$ is monotonically decreasing with respect to $p$, then it allows to us find a critical value of the randomness parameter, $p_{w}$, such that whenever $p>p_{w}$ the state is guaranteed to show GME. A depiction of what could happen is illustrated in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069ritical\_probability\_and\_its\_upper\_bound\]. There, the expectation value of a GME witness on the RG state $\rho_{G}^{p}$ is plotted as a function of $p$, and compared with the expected behavior of a general measure of GME. By assuming the existence of a threshold $p_{c}$ above which the state shows GME (according to the GME measure), it is clear that $p_{w}$ is an upper bound for $p_{c}$, i.e., $p_{c}\leq p_{w}$. Note that the presence of a threshold $p_c$ is supported by results shown in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pptmixer\_ent\_monotone\], and that any negative expectation value for a witness leads to a lower bound for a corresponding entanglement measure @brandao2005quantifying. ![(Color online) Relation between a measure of GME and the expectation value of the witness $W$. The critical probability $p_{c}$ is upper bounded by $p_{w}$, i.e. the value of $p$ where the expectation value becomes negative. Notice that the existence of $p_{c}$ and the monotonically increasing behavior of the GME measure are not guaranteed. The same considerations apply to the monotonic decreasing behavior of the expectation value. The dashed line depicts an $l$-level approximated GME witness introduced in Sec. \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069upper bound of critical randomness for general graphs\]. In contrast with the non-approximated witness, it is monotonically decreasing for level $l\leq|E_{G}|/2$ and randomness $1/2\leq p\leq1$. The value of the non-approximated GME witness $\text{Tr}(W_{G}\rho_{G}^{p})$ is always smaller or equal than the $l$-approximated GME witness $I_{\mathcal{F}^{(\leq l)}}(\rho_{G}^{p})$. <span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069ritical_probability_and_its_upper_bound"></span>](pics/critical_probability_and_its_upper_bound){width="0.9\linewidth"} A suitable witness to detect GME in a RG state $\rho_{G}^{p}$ turns out to be the projector-based witness @AcinBLSanpera2001-07 [@GuhneHBELMSanpera2002-12; @Bourennane2004-02; @TothGuhne2005-02], $$W_{G}=\frac{1}{2}\mathbbm{1}-|G\rangle\langle G|.\label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069projector_witness}$$ Notice that the operator above involves only the projector onto the pure graph state $|G\rangle$ that generates $\rho_{G}^{p}$, disregarding all its subgraphs. In order to see whether $W_{G}$ of Eq. provides a negative expectation value for the state $\rho_{G}^{p}$, one has to compute the overlap $\text{Tr}[|G\rangle\langle G|\rho_{G}^{p}]$. Therefore we introduce the next definition: \[Randomization overlap\]The overlap of a graph state $|G\rangle$ and its randomization $\rho_{G}^{p}$ is the randomization overlap of $\rho_{G}^{p}$, *i.e.* $$\begin{aligned} L(\rho_{G}^{p}):= & \emph{Tr}[|G\rangle\langle G|\rho_{G}^{p}]\label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069randomization_overlap}\\ & =\sum_{F\emph{\ spans}\text{ }G}p^{|E_{F}|}(1-p)^{|E_{G}\backslash E_{F}|}\emph{Tr}[|G\rangle\langle G|F\rangle\langle F|].\nonumber\end{aligned}$$ Due to the linearity of the trace, the calculation of the randomization overlap $L(\rho_{G}^{p})$ of Eq. thus reduces to the calculation of the scalar product of the graph state $|G\rangle$ with all its possible subgraph states $|F\rangle$. Furthermore, exploiting the symmetric difference defined in section \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069graphs\] and the definition of a graph state in Eq. , each contribution $\text{Tr}[|G\rangle\langle G|F\rangle\langle F|]$ can be rewritten as $$\text{Tr}[|G\rangle\langle G|F\rangle\langle F|]=\text{Tr}[|G^{\emptyset }\rangle\langle G^{\emptyset}|G\Delta F\rangle\langle G\Delta F|],$$ where $|G^{\emptyset}\rangle$ is associated with the empty graph. Therefore, the overlap of any two graph states can be recast as the overlap of the graph defined by the symmetric difference and the empty one. However, even in this form the scalar product remains highly nontrivial to compute. By the help of a specifically developed algorithm @XchainsRef, some special cases can be computed efficiently and even an analytical formula can be given (see Table \[tabl8b7c:f320:99b9:690f:4595:cd17:293a:c069results\_of\_scalar\_product\_of\_example\_graphs\]), especially when a small number of edges is concerned. However, in the general case the overlap can be given only via some iterative formula @NiekampKGuehne2012, which unfortunately scales exponentially in the number of vertices. Besides the difficulty to compute each single overlap, another problem that inevitably affects the computation of the randomization overlap $L(\rho _{G}^{p})$ consists of the large number of contributions we have to account for. As a matter of fact, since a RG state contains $2^{\binom{|E_{G}|}{2}}$ possible subgraphs, that is exponentially increasing in the number of edges, the number of overlaps contributing to $L(\rho_{G}^{p})$ increases exponentially fast as well. Nonetheless there exist some special cases that can be treated explicitly and where an analytical solution can be found. These cases will be treated in the following, before moving to a possible efficient approximation of the randomization overlap $L(\rho_{G}^{p})$. Calculation of the witness for special RG states {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069upper_bound_of_critical_randomness_of_simple_RG_states} ------------------------------------------------ In Appendix \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069randomization\_overlap\_of\_some\_special\_RG\_states\], we derive the randomization overlap of both the RG state $\rho_{S_{n}}^{p}$, corresponding to the star graph $S_{n}$, and the randomized 1D cluster $\rho_{L_{n}}^{p}$. The expectation value of the witness $W_{S_{n}}$ on the state $\rho_{S_{n}}^{p}$ takes the form $$\text{Tr}[W_{S_{n}} \rho_{S_{n}}^{p}]=\frac{1}{4}-\frac{3}{4}p^{n-1},$$ which is monotonically decreasing with respect to $p$. Therefore the threshold probability turns out to be $p_{w}=3^{-1/(n-1)}$, and upper bounds the critical randomness $p_{c}$. For the randomized 1D cluster state $\rho_{L_{n}}^{p}$ the witness gives instead the following expectation value: $$\begin{aligned} \text{Tr} & [W_{L_{n}} \rho_{L_{n}}^{p} ]\nonumber\\ = & \frac{1}{2}-\frac{1}{\sqrt{\lambda_{p}}}\left( 1-\frac{p}{2}+\frac {\sqrt{\lambda_{p}}}{2}\right) \left( \frac{p}{2}+\frac{\sqrt{\lambda_{p}}}{2}\right) ^{n}\nonumber\\ & +\frac{1}{\sqrt{\lambda_{p}}}\left( 1+\frac{p}{2}+\frac{\sqrt{\lambda_{p}}}{2}\right) \left( \frac{p}{2}-\frac{\sqrt{\lambda_{p}}}{2}\right) ^{n},\label{eq.8b7c:f320:99b9:690f:4595:cd17:293a:c069witness_1D_RC_state_without_extra_term}$$ where $\lambda_{p}=1-p+ p^{2}$ (see Appendix \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069randomization\_overlap\_of\_some\_special\_RG\_states\] for details). Notice that this function is also monotonically decreasing with respect to $p$. Solving the above polynomial in $p$ thus provides an upper bound $p_{w}$ on $p_c$ for the RG state $\rho_{L_{n}}^{p}$. Both the expectation values above are plotted in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pw\_of\_simple\_RG\_graphs\]. ![(Color online) Probability $p_{w}$ for the randomized star graph state $\rho_{S_{n}}^{p}$ and the randomized 1-$d$ cluster state $\rho_{L_{n}}^{p}$.<span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pw_of_simple_RG_graphs"></span>](pics/pw_of_simple_RG_graphs){width="\linewidth"} The nonapproximated values $p_{w}$ of the RG cycle state $\rho_{C_{n}}^{p}$ can also be computed numerically by the use of the algorithm developed in Ref. @XchainsRef, which will be compared with approximated values in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_approximation\_accuracy\] in the next section. It is worth mentioning that, as expected, $p_{w}$ increases rapidly as the number of vertices increases. From an experimental point of view, this means that the more edges one creates, the higher gate quality is required to guarantee the presence of GME in the final state. In the following we will follow a different approach, namely we will approximate the witness neglecting all contributions of subgraphs too "different" from the generating one. This approximation holds whenever the randomness parameter $p$ is high enough. Approximated witness {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069upper bound of critical randomness for general graphs} -------------------- Due to the structure of a general RG state, the computation of the scalar product of the pure graph state with all spanning subgraph states turns out to be too complex. Therefore, we introduce an approximation of the randomization overlap $L(\rho_{G}^{p})$, that defines the expectation value $W_{G}$. Here we define the $l$*-level approximation* of a randomization overlap by dropping its subgraph components $F^{(>l)}$ which differ from $G$ by more than $l$ edges, i.e., $$L_{\mathcal{F}^{(\leq l)}}\left( \rho_{G}^{p}\right) :=\text{Tr}(|G\rangle \langle G|\rho_{\mathcal{F}^{(\leq l)}}),$$ where $\rho_{\mathcal{F}^{(\leq l)}}$ is defined as $$\rho_{\mathcal{F}^{(\leq l)}}=\sum_{F\text{ s.t. } |E_{F\Delta G}|\leq l}p^{|E_{F}|}(1-p)^{|E_{G}\backslash E_{F}|}|F\rangle\langle F|.$$ The $l$-level approximated witness then reads $$I_{\mathcal{F}^{(\leq l)}}(\rho_{G}^{p}):=\frac{1}{2}-L_{\mathcal{F}^{(\leq l)}}\left( \rho_{G}^{p}\right) .\label{eq8b7c:f320:99b9:690f:4595:cd17:293a:c069witness_for_RG_state_low_edges_l}$$ The proof of the next statement is in Appendix \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069proof\_of\_approximation\_of\_GME\_witness\]. \[prop8b7c:f320:99b9:690f:4595:cd17:293a:c069monotonicity\_of\_approximated\_witness\] The $l$-level approximated randomization overlap $L_{\mathcal{F}^{(\leq l)}}(\rho_{G}^{p})$ is monotonically increasing with respect to the randomness $p\geq1/2$ for all $l\leq|E_{G}|/2$. A good approximation, when $p$ is close enough to $1$, consists in neglecting the subgraphs $\mathcal{F}^{(>2)}$ that differ from $G$ by more than two edges. This corresponds to a reduced RG state of $|G\rangle$ where only the most relevant subgraphs appear. The following theorem states that instead of using the full randomization overlap $L(\rho_{G}^{p})$ in the GME witness, we can focus just on $L_{\mathcal{F}^{(\leq2)}}\left( \rho _{G}^{p}\right) $ with the advantage to make the calculation easier. \[Approximated GME witness\]\[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069pproximated\_GME\_witness\] Let $G$ be a graph and $d_{v}$ be the degree of a vertex $v$. The quantity $L_{\mathcal{F}^{(\leq2)}}\left( \rho_{G}^{p}\right) $ is a lower bound for the randomization overlap $L\left( \rho_{G}^{p}\right) $, namely $$\begin{aligned} L\left( \rho_{G}^{p}\right) \geq & L_{\mathcal{F}^{(\leq2)}}\left( \rho_{G}^{p}\right) \label{eq8b7c:f320:99b9:690f:4595:cd17:293a:c069-level_approximated_randomization_overlap}\\ = & p^{\left\vert E_{G}\right\vert }+\frac{1}{4}\left( 1-p\right) p^{\left\vert E_{G}\right\vert -1}\left\vert E_{G}\right\vert \nonumber\\ & +\frac{1}{2^{4}}\left( 1-p\right) ^{2}p^{\left\vert E_{G}\right\vert -2}\left[ \binom{\left\vert E_{G}\right\vert }{2}+3\sum_{v\in V_{G}}\binom{d_{v}}{2}\right] .\nonumber\end{aligned}$$ For $p\gg1/2$, $L\left( \rho_{G}^{p}\right) \simeq L_{\mathcal{F}^{(\leq2)}}\left( \rho_{G}^{p}\right) $. The following quantity can be regarded as a GME witness for $\rho_{G}^{p}$. $$I_{\mathcal{F}^{(\leq2)}}(\rho_{G}^{p}):=\frac{1}{2}-L_{\mathcal{F}^{(\leq2)}}\left( \rho_{G}^{p}\right) \label{eq8b7c:f320:99b9:690f:4595:cd17:293a:c069witness_for_RG_state_low_edges_2}$$ If $I_{\mathcal{F}^{(\leq2)}}\left( \rho_{G}^{p}\right) < 0$, it is then guaranteed that the RG state $\rho_{G}^{p}$ is genuinely multipartite entangled. See Appendix \[s8b7c:f320:99b9:690f:4595:cd17:293a:c069proof\_of\_approximation\_of\_GME\_witness\] for a proof. Notice that the value of the randomness parameter $p_{\mathcal{F}}$ that makes $I_{\mathcal{F}^{(\leq2)}}(\rho_{G}^{p})$ vanishing is still an upper bound of the critical randomness $p_{c}$ for the RG state $\rho_{G}^{p}$. Notice that by construction the following chain of inequalities holds $p_{c}\leq p_{w}\leq p_{\mathcal{F}}$. Furthermore, according to Proposition \[prop8b7c:f320:99b9:690f:4595:cd17:293a:c069monotonicity\_of\_approximated\_witness\], the witness $I_{\mathcal{F}^{(\leq2)}}(\rho_{G}^{p})$ is monotonically decreasing as a function of $p$. Hence whenever $p>p_{\mathcal{F}}$ the RG state $\rho _{G}^{p}$ shows GME. ![(Color online) Accuracy of the approximated GME witness $L_{\mathcal{F}^{(\leq2)}}( \rho_{C_{n}}^{p}) $ for the cycle RG graph $\rho_{C_{n}}^{p}$. The parameter for comparison is the threshold probability $p_{w}$, calculated according to algorithm explained in Ref. @XchainsRef.<span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF_approximation_accuracy"></span>](pics/pF_pw_RCYC "fig:"){width="0.8\columnwidth"}\ ![(Color online) Accuracy of the approximated GME witness $L_{\mathcal{F}^{(\leq2)}}( \rho_{C_{n}}^{p}) $ for the cycle RG graph $\rho_{C_{n}}^{p}$. The parameter for comparison is the threshold probability $p_{w}$, calculated according to algorithm explained in Ref. @XchainsRef.<span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF_approximation_accuracy"></span>](pics/pF_approximation_accuracy "fig:"){width="0.8\columnwidth"}\ By employing this theorem one can detect GME even for a graph with relatively many edges, however a study about how well the approximated witness performs is now needed. In order to check the accuracy of our approximation, we consider as an example the cycle RG graph $\rho_{C_{n}}^{p}$ and plot the relative difference between $p_{\mathcal{F}}$ and $p_{w}$. As we can see in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_approximation\_accuracy\], for $n=3$ the value of $p_{\mathcal{F}}$ equals $p_{w}$, while for higher $n$ the approximation becomes more and more accurate as the number of vertices increases. Note that the equality for $n=3$ results from the fact that the single neglected contribution $\mathrm{Tr}[|G^{\emptyset}\rangle\langle G^{\emptyset}|C_{3}\rangle\langle C_{3}|]$ in $L_{\mathcal{F}^{(\leq2)}}(\rho_{C_{3}}^{p})$ is equal to zero. ![Threshold probability $p_{\mathcal{F}}$ for randomized 2D cluster states $\rho_{L_{{n\times m}}^{p}}=R_{p}(|L_{n\times m}\rangle)$. Here, $m$ and $n$ represent the number of vertices along the $x$ and $y$ axes of the 2D cluster, respectively. The quantity $p_{\mathcal{F}}$ is depicted as a map in a $(m,n)$ grid.<span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF_2d_cl_2edges"></span>](pics/pF_2d_cl_2edges_matrix){width="\columnwidth"} ![Threshold probability $p_{\mathcal{F}}$ for randomized 3D cluster states $\rho_{L_{i\times j\times k}}^{p}=R_{p}(|L_{i\times j \times k}\rangle)$. The indices $i$, $j$ and $k$ represent the number of vertices along the $x$, $y$, and $z$ axes of the 3D cluster, respectively. The quantity $p_{\mathcal{F}}$ is depicted in grayscale in a $(i,j,k)$ grid.<span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF_3d_cl_2edges"></span>](pics/pF_3d_cl_2edges){width=".9\columnwidth"} In order to show the quality of our approximation we consider here other relevant RG states, that is randomized 2D and 3D cluster states. For these states we plot the approximated $p_{\mathcal{F}}$ in Figs. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_2d\_cl\_2edges\] and \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_3d\_cl\_2edges\], as a function of the number of vertices along each direction of the cluster. As we can see in Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_2d\_cl\_2edges\], $p_{\mathcal{F}}$ for the two-dimensional RG state $\rho_{L_{m\times n}}^{p}$ increases as the sum $m+n$ grows, where $m$ and $n$ are the number of vertices along the $x$ and $y$ axes, respectively. It also turns out that the values of $p_{\mathcal{F}}$ for two RG cluster states $\rho_{L_{m_{1}\times n_{1}}}^{p}$ and $\rho_{L_{m_{2}\times n_{2}}}^{p}$ are very close to each other whenever $m_{1}+n_{1}=m_{2}+n_{2}$ . The same arguments hold also for the three-dimensional randomized cluster state (see Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_3d\_cl\_2edges\]). Notice that the approximated witness given in Eq. can be exploited to obtain a value of the randomness parameter $p$ above which the RG state shows GME. Vice versa, if we have at disposal only CZ gates with a fixed parameter $p$, we can then use the estimates given by the witness to find out possible multipartite entangled RG states one could create (see Figs. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pw\_of\_simple\_RG\_graphs\] and \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_approximation\_accuracy\]). Bell inequalities {#sec:bell} ================= In this section, we investigate when RG states cannot be described in terms of *local hidden variable* (LHV) models @bell1964einstein [@mermin1990extreme; @greenberger1990bell]. Any LHV model has to fulfill the constraints of realism and locality. These two facts result in bounds on the strength of correlations, which can be formally captured in terms of Bell pdavis@example.com. A violation of such an inequality excludes the description of the correlations in terms of an LHV model @mermin1990extreme [@greenberger1990bell]. We will show that RG states violate Bell inequalities developed for pure graph states, whenever the randomization parameter $p$ is high enough. In order to do so we review the stabilizer description of graph states @hein2006entanglement. Given a graph $G$, we can associate to each vertex $i$ a *stabilizing operator* $g_{i}$ as follows $$g_{i}=X^{(i)}\bigotimes_{j\in N(i)}Z^{(j)}.$$ where $N(i)$ is the neighborhood of the vertex $i$, i.e., the set of vertices connected to $i$. Here, $X^{(i)},Y^{(i)},Z^{(i)}$ denote the Pauli matrices $\sigma_{x},\sigma_{y},\sigma_{z},$ acting on the $i$-th qubit. The graph state $|G\rangle$ associated with the graph $G$ is the unique $n$-qubit state fulfilling $$g_{i}|G\rangle=|G\rangle,\mbox{ for }i=1,...,n.$$ The $n$ operators $g_{i}$ turn out to be the generators of a group, called stabilizer and denoted by $S(G)$. The group $S(G)$ can be shown to be Abelian and is composed of $2^{n}$ elements $s_{j}$. By this definition it straightforwardly follows that $\langle G|s_{j}|G\rangle=1$ for any $j=1,...,2^{n}$. As any $s_{j}$ can be expressed as a product of $n$ dichotomic local observables, we can thus define the following Bell operator @guhne2005bell: $$\mathcal{B}(G)=\frac{1}{2^{n}}\sum_{j=1}^{2^{n}}s_{j}.$$ Furthermore since a graph state is a product of projectors of its stabilizer generators, i.e., $|G\rangle\langle G|=\prod _{i}(\mathbbm{1}+g_{i})/2=\mathcal{B}(G)$, the expectation value of $\langle\mathcal{B}(G)\rangle$ reaches its maximum value $1$ only for the state $|G\rangle$. By defining the quantity $$\mathcal{D}(G)=\max_{\text{LHV}}|\langle\mathcal{B}(G)\rangle|,$$ where the maximum is taken over all LHV models, equivalently taken over all possible expectation values of local observables $\langle X^{(i)}\rangle$, $\langle Y^{(i)}\rangle$, $\langle Z^{(i)}\rangle$ within $\{-1,+1\}$, we then have the following Bell inequality @guhne2005bell $$\langle\mathcal{B}(G)\rangle\leq\mathcal{D}(G).\label{bell_in}$$ As a straightforward consequence, given the graph state $|G\rangle$, we are guaranteed that it cannot be described by a LHV model whenever $\mathcal{D}(G)<1$. For our purpose it is more convenient to rephrase the Bell inequality in terms of a detection operator. Keeping in mind that the Bell operator $\mathcal{B}(G)$ is exactly the projector $|G\rangle\langle G| $, the following witness operator can be found @guhne2005bell [@HyllusGBLewenstein2005-07] $$W_{\text{LHV}}=\mathcal{D}(G)\mathbbm{1}-|G\rangle\langle G|.$$ Hence, whenever $\operatorname{Tr}[W_{\text{LHV}}\rho]<0$, i.e., the expectation value of $W_{\text{LHV}}$ on the quantum state $\rho$ is negative, the state $\rho$ violates local realism, and thus cannot be described by LHV models. Note that the witness $W_{\text{LHV}}$ is similar to the witness for GME of Eq. . They indeed differ only in the value of the coefficient of the identity operator. Notice furthermore that the approximation techniques developed so far apply here too, allowing us to proceed as in Eq. in the previous section, i.e., $$I^{(\leq l)}_{\mathrm{LHV}}(\rho_{G}^{p}):=\mathcal{D}(G)-L_{\mathcal{F}^{(\leq l)}}\left( \rho_{G}^{p}\right) .\label{eq8b7c:f320:99b9:690f:4595:cd17:293a:c069ll_ineq_for_RG_state_low_edges_l}$$ In @guhne2005bell, the quantity $\mathcal{D}(G)$ has been calculated for different graphs with number of qubits $n$ up to $10$. Our analysis consists of calculating the approximated threshold $p_{\text{LHV}}^{l\leq2}$ for a given graph state $|G\rangle$, such that $I_{\mathrm{LHV}}^{(\leq2)}(\rho_{G}^{p_{\text{LHV}}})=0$. Since $I_{\mathrm{LHV}}^{(\leq 2)}(\rho_{G}^{p})$ is monotonically decreasing with respect to $p$ for $p>1/2$ (see Proposition \[prop8b7c:f320:99b9:690f:4595:cd17:293a:c069monotonicity\_of\_approximated\_witness\]), any randomness parameter $p>p_{\text{LHV}}^{(l\leq2)}$ will then lead to a RG state that cannot be described in terms of a LHV model. In Fig. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069p\_LHV\_Bell\_ineq\], we show the achieved result for several important RG states. In this figure one can see that the classical bounds $\mathcal{D}(G)$ are crucial for the behavior of $p_{\text{LHV}}$. For a given type of graph, since the classical bound $\mathcal{D}(G)$ is decreasing with respect to the number of vertices $n$, the threshold $p_{\text{LHV}}$ is not monotonically increasing with respect to $n$. The ordering of $p_{\text{LHV}}$ among different types of graphs can be explained via the ordering of $\mathcal{D}(G)$. For $n\leq5$, $\mathcal{D}(C_n)=\mathcal{D}(L_n)=\mathcal{D}(S_n)$ holds. Therefore $p_{\text{LHV}}(C_n)>p_{\text{LHV}}(L_n)>p_{\text{LHV}}(S_n)$ has the same ordering as the threshold $p_{\text{GME}}$ for GME; see Figs. \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pw\_of\_simple\_RG\_graphs\] and \[fig8b7c:f320:99b9:690f:4595:cd17:293a:c069pF\_approximation\_accuracy\]. For $n>5$, the ordering of the threshold values $p_{\text{LHV}}(S_n)>p_{\text{LHV}}(L_n)>p_{\text{LHV}}(C_n)$ reflects the ordering of the classical bounds for the different types of graphs, i.e., $\mathcal{D}(S_n)>\mathcal{D}(L_n)>\mathcal{D}(C_n)$. For larger $n$, we observe that the nonlocality of the randomized star graph states is fragile with respect to our noise model. This is analogous to the noise resistance of GME for star graph states. The fragility of GME states for other noise models has been investigated in @AliGuhne2014-02. Similar to the previous section, we can use the results provided by $I_{LHV}$ of Eq. in order to generate nonlocal multiqubit states by using only CZ gates with a given success probability $p$. For instance, if we have CZ gates with success probability $p=0.84$, we can then create a nonlocal six-qubit system via generating a six-qubit randomized cycle graph state by subsequently connecting the six qubits using solely the CZ pdavis@example.com. ![(Color online) The probability thresholds $p^{(l \leq2)}_{\mathrm{LHV}}$ for some important RG states. These thresholds are the zero-crossings of Eq. . Due to the complexity of the calculation of the classical bounds $\mathcal{D}(G)$, only the thresholds for the states up to $10$ qubits are analyzed . The behavior of $p_{\text{LHV}}^{(l\leq2)}$ is explained at the end of the section \[sec:bell\]. <span data-label="fig8b7c:f320:99b9:690f:4595:cd17:293a:c069p_LHV_Bell_ineq"></span>](pics/p_LHV_Bell_ineq){width="0.9\linewidth"} Conclusions {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069conclusion} =========== In this paper, we introduced a class of $n$-qubit mixed states that we called randomized graph (RG) states because they can be derived from pure graph states by applying a randomization procedure. They represent a quantum analog of random graphs. These states can also be regarded as the resulting states in an imperfect graph state generation procedure @lim2005repeat [@lim2006repeat; @beige2007repeat]. We studied in particular the entanglement properties of such states and it turned out that their entanglement classification is quite different from the one for graph states. We investigated whether local unitary (LU)equivalence of pure graph states implies LU equivalence of their randomized version, and answered this question in a negative way. Although the presence of a randomized edge guarantees bipartite entanglement between the two parties that are linked by the edge, the bipartite entanglement of RG states is more fragile under the action of local measurements with respect to the one of their corresponding graph states. We investigated this aspect by evaluating the connectedness and persistency of RG states. We then studied the multipartite entanglement properties of RG states. Due to the fact that these multi-qubit states are mixed, we could evaluate the multipartite entanglement content only in some particular cases, namely for states up to four qubits. In such cases we could show that multipartite entanglement exhibits a monotonic behavior as a function of the randomness parameter $p$, while it is still an open problem whether the entanglement of a general RG state grows monotonically with $p$. In the general case we could define a critical value $p_c$ for the randomness parameter above which the RG states are guaranteed to be multipartite entangled by employing suitable multipartite entanglement witnesses. The threshold $p_c$ also provides an estimate of how much noise the CZ gates can be in order to guarantee GME in the generated state. Furthermore, the same approach was exploited to study the possibility to describe such RG states in terms of local hidden variable (LHV) models. Again, we could find a critical probability $p_\text{LHV}$ above which the quantum state surely violates a Bell inequality. The threshold $p_{LHV}$ also gives a hint regarding which kind of nonlocal multi-qubit states can be created by using solely controlled-Z gates with a given success probability. We point out that RG states have possible applications in measurement based quantum computation, quantum key distribution, quantum networks, etc. Since RG states are derived by the use of imperfect controlled-Z gates, which is unavoidable in a laboratory, it is more natural to consider these states instead of pure graph states in the quantum information processing task one wants to pursue. As an outlook, the emergence of giant components of RG states and the properties of RG states in the asymptotic limit $n\rightarrow\infty$ are interesting theoretical topics that deserve further investigation. Other interesting questions that still need to be addressed are for example the possibility of identifying a Hamiltonian which has a RG state as eigenstate, or the possibility of designing a protocol to herald the components of a RG state, such that one can perform a preselection of the RG state to extract certain subgraph states from it. We thank O.Gühne for useful discussions. J.W., D.B. and H.K. were financially supported by DFG and SFF of Heinrich-Heine-University Düsseldorf. K.L.C. was supported by the National Research Foundation & Ministry of Education, Singapore. S.S. was supported by the Royal Society. Proofs of theorems <span>theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069imension\_of\_complete\_subgraphs\_state\_space</span> and <span>theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069rank\_of\_random\_graph\_states</span> {#s8b7c:f320:99b9:690f:4595:cd17:293a:c069proof_of_theorems_in_unitary_equivalence} =================================================================================================================================================== The proofs of Theorems \[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069imension\_of\_complete\_subgraphs\_state\_space\] and <span>theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069rank\_of\_random\_graph\_states</span> are given below. Notice that for Theorem \[theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069imension\_of\_complete\_subgraphs\_state\_space\] two proofs are provided, the former being more intuitive, the latter being more formal. \[Proof of Theorem <span>theorem8b7c:f320:99b9:690f:4595:cd17:293a:c069imension\_of\_complete\_subgraphs\_state\_space</span>\] Let us denote the $n$-qubit state with a single qubit in state 1 at position $i$ as $|1_{i}\rangle $. Then, from the definition of graph states in terms of CZ operations (Eq. ) it follows that the $n$ linearly independent (but not mutually orthogonal) states given by $$|00...0\rangle -|1_{i}\rangle \text{ for every }i=1,...,n$$are orthogonal to any subgraph state $|G_{i}\rangle $ of $K_{n}$. Thus it follows that $\dim (\Sigma _{K_{n}})\leq 2^{n}-n$, where $\Sigma _{K_{n}}$ is the subspace spanned by all possible subgraph states of $K_{n}$, *i.e.* all possible graph states with $n$ vertices. To prove that the equality holds, we have to show that the state $|D_{n}\rangle =|00...0\rangle +\sum_{i=1}^{n}|1_{i}\rangle $ and any state with a number of qubits in state $1$ (excitations) larger than $2$, denoted by $|\text{exc}_{n}\geq 2\rangle $, can be expressed as a linear combination of graph states. This is clearly true in the simplest case of two qubits, as $|D_{2}\rangle \propto |++\rangle +|\vcenter{\hbox{\includegraphics[width=2em]{pics/bell_2}}}\rangle $ and $|11\rangle \propto |++\rangle -|\vcenter{\hbox{\includegraphics[width=2em]{pics/bell_2}}}\rangle $. In order to show that it holds for generic $n$ we proceed by induction. Suppose that for $n$ qubits it is always possible to express both $|D_{n}\rangle $ and the states $|\text{exc}_{n}\geq 2\rangle $ as $\sum_{i}\alpha _{i}|G_{i}\rangle $. Then, it can be easily proved that one can achieve both $|D_{n+1}\rangle $ and $|\text{exc}_{n+1}\geq 2\rangle $ as follows. Start from the state $| \text{exc}_n\ge 2 \rangle| + \rangle$, that by hypothesis can be written as $\sum_i\alpha_i| G_i \rangle| + \rangle$. Apply then a CZ on the qubit $n+1$ and on one of the qubits that correspond to state $1$ in $| \text{exc}_n\ge 2 \rangle$ so that the resulting state is $\text{CZ}| \text{exc}_n\ge 2 \rangle| + \rangle$. Then, take the following linear combination of the two states $| \text{exc}_n\ge 2 \rangle| + \rangle$ and $\text{CZ}| \text{exc}_n\ge 2 \rangle| + \rangle$ such that $| \text{exc}_{n+1}\ge 2 \rangle\propto| \text{exc}_n\ge 2 \rangle| + \rangle \pm\text{CZ}| \text{exc}_n\ge 2 \rangle| + \rangle$. It can be easily seen that in this way almost all states of $n+1$ qubits with more than two excitations $| \text{exc}_{n+1}\ge 2 \rangle$ can be created (apart from some with two excitations that will be discussed in the following). Actually $2(2^n-n-1)$ states of the computational basis can be derived from the procedure above. In order to generate the $n+1$ missing states (to achieve all the $2^{n+1}-(n+1)$ desired states)
{'source': 'arXiv_out/1403'}