The negativity of randomized graph states is not monotone

Abstract

Wu, Rossi, Kampermann, Severini, Kwek, Macchiavello and Bruss (arXiv:1403.3828, Section V) ask whether the negativity of a randomized graph state, across any bipartition, increases monotonically with the probability p that each edge is present. It does not: for the complete bipartite graph K_(3,3) and the bipartition into its two parts, the negativity is larger than 1/2 at p = 97/100 and at most 1/2 at p = 1.

Definition 1.1 (Controlled-Z phases).

$$\forall n:\mathbb{N},\forall a:\mathrm{Fin}\left(n\right),\forall b:\mathrm{Fin}\left(n\right),\forall x:\mathrm{Qubits}\left(n\right),\mathrm{czPhase}\left(s\left(a,b\right),x\right)=(-1{)}^{x\left(a\right)\cdot x\left(b\right)}$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.czPhase (✓ std3).

Citation. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The n qubits are indexed by Fin(n) and the computational basis by the maps x from Fin(n) to Bool, with true read as 1 and false as 0. The controlled-Z gate on the edge {a, b} is diagonal in this basis, with entry (-1)^(x(a) x(b)) at the basis state x.

Definition 1.2 (The product state).

$$\forall n:\mathbb{N},\forall x:\mathrm{Qubits}\left(n\right),\mathrm{plusState}\left(n,x\right)=(\frac{1}{\sqrt{2}}{)}^n$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.plusState (✓ std3).

Citation. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The state |+>^n has every computational-basis amplitude equal to 2^(-n/2).

Definition 1.3 (Graph states).

$$\forall n:\mathbb{N},\forall F:\mathrm{Finset}\left(Sym2\left(\mathrm{Fin}\left(n\right)\right)\right),\forall x:\mathrm{Qubits}\left(n\right),\mathrm{graphState}\left(F,x\right)=(\prod _{e\in F}\mathrm{czPhase}\left(e,x\right))\cdot \mathrm{plusState}\left(n,x\right)$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.graphState (✓ std3).

Citation. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The graph state of an edge set F is the product of the controlled-Z gates of its edges applied to |+>^n. These gates are diagonal, so the amplitude at x is the product of their phases at x times the amplitude of |+>^n.

Definition 1.4 (Randomized graph states).

$$\forall n:\mathbb{N},\forall G:\mathrm{SimpleGraph}\left(\mathrm{Fin}\left(n\right)\right),\forall p:\mathbb{R},\mathrm{rgState}\left(G,p\right)=\sum _{F\subseteq \mathrm{edgeFinset}\left(G\right)}{p}^{\mathrm{card}\left(F\right)}\cdot (1-p{)}^{\mathrm{card}\left(\mathrm{edgeFinset}\left(G\right)\setminus F\right)}\cdot \mathrm{vecMulVec}\left(\mathrm{graphState}\left(F\right),\mathrm{star}\left(\mathrm{graphState}\left(F\right)\right)\right)$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.rgState (✓ std3).

Citation. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

Each edge of G is present independently with probability p. The randomized graph state is the mixture, over the subsets F of the edge set of G, of the projections onto the graph states of F, with weights p^|F| (1 - p)^(|E(G)| - |F|).

Definition 1.5 (Negativity).

$$\forall n:\mathbb{N},\forall A:\mathrm{Finset}\left(\mathrm{Fin}\left(n\right)\right),\forall \rho :{\mathbb{C}}^{\mathrm{Qubits}\left(n\right)\times \mathrm{Qubits}\left(n\right)},\mathrm{negativity}\left(A,\rho \right)=\frac{\mathrm{traceNorm}\left(\mathrm{transposePart}\left(A,\rho \right)\right)-1}{2}$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.negativity (✓ std3).

Citation. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The negativity across the bipartition A versus its complement is (||rho^Gamma_A|| - 1)/2. The partial transposition rho^Gamma_A is the existing transposePart: its entry at (x, y) is the entry of rho at the row label with A part from y and remaining part from x, and the column label with A part from x and remaining part from y. The trace norm ||X|| = Re Tr sqrt(X^* X) is that of the existing finite trace-distance module.

Definition 1.6 (The question).

$$(claim)\iff (\forall n:\mathbb{N},\forall G:\mathrm{SimpleGraph}\left(\mathrm{Fin}\left(n\right)\right),\forall A:\mathrm{Finset}\left(\mathrm{Fin}\left(n\right)\right),\forall p:\mathbb{R},\forall q:\mathbb{R},(0\le p)\Rightarrow ((p\le q)\Rightarrow ((q\le 1)\Rightarrow (\mathrm{negativity}\left(A,\mathrm{rgState}\left(G,p\right)\right)\le \mathrm{negativity}\left(A,\mathrm{rgState}\left(G,q\right)\right)))))$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.claim (✓ std3).

Citation. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The paper reports monotone negativity for the complete graphs and the star graphs with at most 4 vertices and states that it is an open question whether the monotonic behaviour of the negativity in p is a common feature of all randomized graph states, the negativity being evaluated with respect to all bipartitions. The displayed statement reads the question as a universal statement over finite simple graphs on Fin(n), subsets A of the vertices and 0 <= p <= q <= 1.

Definition 1.7 (The graph K_(3,3)).

$$\forall a:\mathrm{Fin}\left(6\right),\forall b:\mathrm{Fin}\left(6\right),(\mathrm{Adj}\left(k33,a,b\right))\iff (\neg (a\equiv b(\mathrm{mod}2)))$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.k33 (✓ std3).

Source. Repository-derived.

Acknowledgement. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The complete bipartite graph on Fin(6) whose parts are the even and the odd vertices.

Definition 1.8 (One part of K_(3,3)).

$$partA=\{0,2,4\}$$

Formalization. D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.partA (✓ std3).

Source. Repository-derived.

Acknowledgement. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

The part A is the set of even vertices.

Theorem 1.9 (The answer is negative).

$$\neg claim$$

Proof. Machine-checked in Lean as D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.result (✓ std3). ∎

Resolves. Problems/wu-2014-randomized-graph-negativity-monotonicity (refuted) by D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.result.

Source. Repository-derived.

Acknowledgement. Jun-Yi Wu; Matteo Rossi; Hermann Kampermann; Simone Severini; Leong Chuan Kwek; Chiara Macchiavello; Dagmar Bruß (2014). Randomized Graph States and their Entanglement Properties. DOI: 10.1103/PhysRevA.89.052335. URL: https://arxiv.org/abs/1403.3828v3.

Commentary.

Expanding the product over the edges, the entry of the randomized state of a graph at (x, y) is 2^(-n) times the product over its edges of p c + (1 - p), where c = 1 if x and y have equal products x(a) x(b) on the edge and c = -1 otherwise. For K_(3,3) with the bipartition into its parts A = {0, 2, 4} and B = {1, 3, 5}, the entries of the partial transpose X_p are therefore (1 - 2p)^d / 64, with d the number of edges on which the two exchanged labels disagree. At p = 1 let u_00 and u_11 be the indicators of even and odd parity on A, times 1 and times the sign (-1)^|x_B| on B respectively, and let w and v be the difference and the sum of the indicator of even parity on A times (-1)^|x_B| and the indicator of odd parity on A. Entry by entry, X_1 + (1/128) w w^T equals (1/64)(u_00 u_00^T + u_11 u_11^T) + (1/128) v v^T. Both sides are sums of positive semidefinite rank-one terms, so by the triangle inequality ||X_1|| is at most the trace of the right side plus the trace of (1/128) w w^T, that is 3/2 + 1/2 = 2, and the negativity at p = 1 is at most 1/2. At p = 97/100, fourteen pairwise orthogonal integer vectors u_j of length 64 give the projection P = sum_j u_j u_j^T / |u_j|^2 and the unitary I - 2P; the trace norm is at least Re Tr((I - 2P) X_(97/100)) = 1 - 2 sum_j u_j^T X u_j / |u_j|^2, and this exact rational number is larger than 2. So the negativity at p = 97/100 exceeds 1/2, which contradicts monotonicity between p = 97/100 and q = 1.

References

• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.claim
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.czPhase
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.graphState
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.k33
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.negativity
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.partA
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.plusState
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.result
• Truth anchor: D5/S3/Quantum/Entanglement/RandomizedGraphNegativityRefutation.rgState
• Dependency: D5/S3/Quantum/Entanglement/CycleFiveStrongOneResistance
• Dependency: D5/S3/Quantum/Foundation/FiniteTraceDistance