Lattice quadrupling for percolation in quantum networks

John Kerl

Department of Mathematics, University of Arizona

June 10, 2009

University of Arizona FRG Workshop

Quantum spin systems, theory, and applications in quantum computation June 8-12, 2009

Goals

Warning … in contrast to much of the discussion in this workshop, I will not mention Lieb-Robinson bounds!

The current work was mostly done in an independent-study project, under Jan Wehr, a year ago. At the time, I lacked the necessary knowledge of finite-size scaling to complete the project, but the semester was over … and it wasn’t my dissertation project so I left it aside.

Having since learned some things about finite-size scaling in my dissertation research, I realized I can now finish this project. I am interested in any advice you may have as I prepare it for publication.

This work extends Entanglement Distribution in Pure-State Quantum Networks, Perseguers, Cirac, Acín, Lewenstein, and Wehr, arXiv:0708.1025v2. I will recapitulate some points about quantum networking (see also Nielsen and Chuang for reference) as well as 2D results from the Perseguers et al. paper. Then I will present my 3D work.

My goals with respect to you: (1) Show you a surprising connection between quantum networking and classical percolation. (2) Give you a flavor of where those “numerical results” come from: in particular, how we use finite-size computations to draw conclusions about infinite systems.

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  2 / 31

Outline

1 Review of quantum teleportation and entanglement swapping

2 Review of the 2D square lattice

3 Quadrupling the 3D rectangular lattice

4 Monte Carlo simulations

5 Finite-size scaling

Review of quantum teleportation and entanglement swapping

Review of quantum teleportation and entanglement swapping

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  4 / 31

Review of quantum teleportation and entanglement swapping

Quantum teleportation: perfect case

Quantum computation involves manipulation of qubits: ψ = c |0⟩ + d |1⟩ with |c|^{2} + |d|^{2} = 1. Quantum devices require quantum wires: devices to move qubits from point A to point B.

Alice, in possession of qubit ψ at point A, can’t measure her qubit; this would collapse (modify) its state. Using local operations and classical communication (LOCC), though, Alice can communicate her qubit to Bob.

PSfrag replacements

A
B
A′
ψ

Before After A′′

ψ

Ingredients: An entangled pair (Bell state) of qubits A and B, e.g. \frac{1}{\sqrt{2}} |00⟩ + \frac{1}{\sqrt{2}} |11⟩, a classical wire, and the message qubit ψ.

Review of quantum teleportation and entanglement swapping

Quantum teleportation: imperfect case

This can be done even with a non-maximally entangled pair of qubits, i.e. a |00⟩ + b |11⟩ with |a|^{2} + |b|^{2} = 1. But now the message qubit ψ is successfully moved from point A to point B only with singlet conversion probability (SCP) which depends on a and b. First one converts the pair a |00⟩ + b |11⟩ into the perfect singlet \frac{1}{\sqrt{2}} |00⟩ + \frac{1}{\sqrt{2}} |11⟩. This succeeds with probability p which is 2(1 − |a|^{2}) if |a| ≤ |b|, else 2(1 − |b|^{2}). Then, one does quantum teleportation as in the perfect case.

Entanglement swapping: perfect case

The next step toward constructing a quantum network is to chain a pair of links. There are two options.

(1) Simply teleport ψ from A to B, then from B to C.

(2) Entanglement swapping changes A-B and B-C links into a B-B link (which is discarded) and an A-C link. Using quantum teleportation, a message qubit ψ may then be moved from point A to point C. Here we discuss only step 1, since step 2 is just as before. Thus, ψ doesn’t appear in the figures here.

PSfrag replacements

A
B

Before C

A

B After C β_{00}^{(12)} β_{00}^{(34)} β_{00}^{(14)} β_{00}^{(23)}

Which approach is better? That is the key point under discussion today.

Entanglement swapping: perfect and imperfect cases

Alice and Charlie may then do quantum teleportation using the (14) states. Any of the four Bell basis states may be used for teleportation.

Since the measurement outcome at (23) specifies the states at (1) and (4), one could apply quantum gates to put β_{kℓ}^{(14)} into the state β_{00}^{(14)}. However, this would require non-local quantum operations, and the paradigm under consideration is LOCC.

In density-matrix terminology, one says that after entanglement swapping, the (14) state is mixed: it has a 4-point classical probability distribution.

* * *

As with quantum teleportation, this can again be done if the A-B and B-C links start off non-maximally entangled. It is shown in Perseguers et al., section III, that the average SCP p does not change.

Review of the 2D square lattice

Review of the 2D square lattice

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  9 / 31

Review of the 2D square lattice

Quantum communication on the 2D square lattice; doubling

One may form a 1D chain of links. The probability of successful end-to-end communication over N links is p^{N}, which goes to zero in the infinite limit. One may instead leverage the well-known results of percolation to attempt to achieve higher teleportation probability on a 2D lattice. Perseguers et al. consider many lattice geometries; I confine my discussion to the square lattice.

On the left is a square lattice formed of quantum-teleportation links. One may ask for the probability of communicating a qubit ψ (not shown) from point A to point B.

In the middle figure, we isolate Bob nodes and perform entanglement swapping twice per circle. The Bob nodes are discarded; what remains, in the right-hand figure, is a doubled lattice.

PSfrag replacements

A
A
A′
B
B′
B

Doubling the 2D square lattice

In both cases, suppose that A is far from B, as are A′ and B′. On the other hand, A and A′, as well as B and B’, occupy adjacent corners of a square. One may communicate along the black lattice from point A to point B, or along the grey lattice from point A′ to point B′. Zoom out for a clearer look: PSfrag replacements

A
A′
B
B′
B
B′
A
A′

Recall that the percolation probability p is the same for the original lattice as for each of the doubled lattices.

Question: Which technique gives higher end-to-end teleportation probability — the original lattice or the doubled lattice?

Doubling the 2D square lattice

For the doubled lattice: If p > p_{c} = 0.5, there are infinite clusters C, C′ (black and grey, respectively) with probability 1. Successful communication from A to B requires A, B ∈ C. These two events are (asymptotically) independent, so we have

P (A ∈ C) = θ(p),  P (B ∈ C) = θ(p),  P (A, B ∈ C) = θ^{2}(p).

Likewise, P (A′, B′ ∈ C′) = θ^{2}(p).

Taking advantage of both lattices, we can communicate from A’s area to B’s area if either path is open. We want to find P (A, B ∈ C or A′, B′ ∈ C′).

Note that if events U and V are independent, P (U ∪ V) does not factor but P (U ∩ V) does. The inclusion-exclusion formula allows us to replace a union with an alternating sum of intersections, which factor. We find

P (A, B ∈ C or A′, B′ ∈ C′)
= P (A, B ∈ C) + P (A′, B′ ∈ C′) − P (A, B ∈ C and A′, B′ ∈ C′)
= 2θ^{2}(p) − θ^{4}(p) = θ^{2}(p)(2 − θ^{2}(p)) := g(θ(p)).

Doubling the 2D square lattice

For the non-doubled lattice, by comparison, there is a single infinite cluster C. We want

P (A, B ∈ C or A, B′ ∈ C or A′, B ∈ C or A′, B′ ∈ C).

Perseguers et al. claim (but omit the proof) that this is asymptotically π^{2}(p) where

π(p) = P (A or A′ ∈ C).

This may be proved using inclusion-exclusion.

To estimate π^{2}(p), Perseguers et al. use the FKG inequality and another Greek-lettered event probability; their resulting analysis of Monte Carlo simulations only applies for p = p_{c}. This is unnecessary: one may consider π^{2}(p) directly in Monte Carlo simulations, and one may obtain results which apply for p away from p_{c}.

In summary, the probabilities of successful communication on the non-doubled and doubled lattices are

P_{double} = θ^{2}(p)(2 − θ^{2}(p)) and P_{single} = π^{2}(p).

The doubled lattice is better if

π^{2}(p) < θ^{2}(p)(2 − θ^{2}(p)).

Perseguers et al. find that this is indeed true for p = p_{c}.

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  13 / 31

Quadrupling the 3D rectangular lattice

Quadrupling the 3D rectangular lattice

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  14 / 31

Quadrupling the 3D rectangular lattice

Quadrupling the 3D rectangular lattice

The first part of the figure shows the non-quadrupled lattice. The second part of the figure shows that each node actually has 6 qubits, although this detail is omitted from the rest of the figure for simplicity.

The third part shows the quadrupled lattice. In a manner analogous to the 2D case, center nodes do measurements onto the Bell basis and Bob themselves out of pariticipation. Four interlocking lattices — red, green, blue, and black — remain.

The fourth part shows the labeling of A_{1}, A_{2}, A_{3}, and A_{4} which are analogs of A and A′ in the 2D case.

PSfrag replacements A_{1}

A_{2}
A_{3}
A_{4}

As before, we ask whether successful communication on the quadrupled lattice is more likely than on the non-quadrupled lattice.

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  15 / 31

Quadrupling the 3D rectangular lattice

For the quadrupled lattice: If p > p_{c} ≈ 0.2488126, there are infinite clusters C_{1}, C_{2}, C_{3}, and C_{4} (red, green, blue, and black, respectively) with probability 1. Successful communication from A_{i} to B_{i} requires A_{i}, B_{i} ∈ C_{i} for i = 1, 2, 3, 4. These two events are (asymptotically) independent, so we have

P (A_{i} ∈ C_{i}) = θ(p),  P (B_{i} ∈ C_{i}) = θ(p),  P (A_{i}, B_{i} ∈ C_{i}) = θ^{2}(p).

Taking advantage of all four lattices, we can communicate from A_{1}’s area to B_{1}’s area if any of the four paths are open. Using inclusion-exclusion, we find

P (∪_{i=1}^{4}(A_{i}, B_{i} ∈ C_{i})) = ∑_{i=1}^{4} P (A_{i}, B_{i} ∈ C_{i}) − ∑_{i} ∑_{j≠i} P (A_{i}, B_{i} ∈ C_{i} and A_{j}, B_{j} ∈ C_{j})

+ ∑_{i} ∑_{j≠i} ∑_{k≠j} P (A_{i}, B_{i} ∈ C_{i} and A_{j}, B_{j} ∈ C_{j} and A_{k}, B_{k} ∈ C_{k})

− P (∩_{i=1}^{4}(A_{i}, B_{i} ∈ C_{i}))

= 4θ^{2}(p) − 6θ^{4}(p) + 4θ^{6}(p) − θ^{8}(p)

= θ^{2}(p)(4 − 6θ^{2}(p) + 4θ^{4}(p) − θ^{6}(p)) := h(θ(p)).

Quadrupling the 3D rectangular lattice

Quadrupling the 3D rectangular lattice

For the non-quadrupled lattice, there is a single infinite cluster C. One can show that

P (∪_{i=1}^{4} ∪_{j=1}^{4} (A_{i}, B_{j} ∈ C))

reduces, as in the 2D case, asymptotically to σ^{2}(p) where

σ(p) := P (∪_{i=1}^{4}A_{i} ∈ C).

Proof: Inclusion-exclusion. Analogously to the 2D case, the quadrupled lattice is better if

σ^{2}(p) < h(θ(p)).

Monte Carlo simulations

Monte Carlo simulations

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  18 / 31

Monte Carlo simulations

Monte Carlo simulations

Overview: For L = 20, 25, 30, 35, 40, 45, … as far as patience and CPU time hold out, and for various values of p above p_{c}, estimate

σ_{L}(p) := P_{L} (∪_{i=1}^{4}(A_{i} ∈ C))

and

θ_{L}(p) := P_{L} (A ∈ C)

for L × L × L lattices. (Note that this is now strictly a percolation question: quantum information is encapsulated in the singlet conversion probability p.)

It will be helpful to do this also for 2D — π(p) and θ(p) — to recover and extend the results from Perseguers et al.

Monte Carlo simulations for fixed L and p

The algorithms for fixed L and p are simple.

To estimate a single value of σ_{L}(p) or θ_{L}(p), do N trials detecting the event ∪_{i=1}^{4}(A_{i} ∈ C) or A ∈ C, respectively. Average these over the N trials to estimate P_{L} of that event. When choosing N, recall that the sample mean tends centrally toward a normal distribution and that the normal’s standard deviation goes as 1/\sqrt{N}. (I.e. to get another decimal place in the estimate of P_{L}(E) for some event E, one needs to run 100 times as many experiments.)

For each trial:

• Populate the bonds of the lattice. Each is open with probability p.

• To compute θ_{L}(p) or σ_{L}(p), mark all clusters and identify the largest one (as described below). Once the largest cluster is marked, it is easy to find if one point (for θ) or any of a specified four (for σ) are in that cluster.

Cluster marking and sizing

Cluster marking:

• Again keep a matrix of site marks, now serving as cluster numbers, all initially set to zero.

• Set cluster number = 1.

• For each site A:

• If A’s cluster number is non-zero (site A has already been visited), continue to the next site.

• In the site-marks matrix, mark A with the current cluster number.

• For each bonded neighbor of A, recursively call the subroutine.

• After the recursion, increment the cluster number by 1.

Cluster sizing:

• Walk through the sites of the lattice, counting the size of each cluster.

• Remember the cluster number of the largest cluster. Call this C.

Lattice before and after cluster numbering: L = 14, p = 0.6

ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo  ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
o                                                           o  o                                                           o
o . - .   . - . - . - .   . - .   . - . - . - .   .   .   . o  o 1 - 1   2 - 2 - 2 - 2   2 - 2   2 - 2 - 2 - 2   .   .   3 o
o |       |       |   |   |       |       |   |           | o  o |       |       |   |   |       |       |   |           | o
o .   .   . - . - .   . - . - . - .   . - . - . - .   .   . o  o 1   2   2 - 2 - 2   2 - 2 - 2 - 2   2 - 2 - 2 - 2   4   3 o
o     |                           |   |       |   |   |     o  o     |                           |   |       |   |   |     o
o . - . - . - . - .   . - . - .   . - . - .   . - .   . - . o  o 2 - 2 - 2 - 2 - 2   2 - 2 - 2   2 - 2 - 2   2 - 2   4 - 4 o
o     |   |       |           |   |   |               |   | o  o     |   |       |           |   |   |               |   | o
o .   .   . - . - .   .   . - .   . - .   .   . - .   . - . o  o .   2   2 - 2 - 2   2   2 - 2   2 - 2   5   4 - 4   4 - 4 o
o         |       |   |   |       |   |   |   |   |   |   | o  o         |       |   |   |       |   |   |   |   |   |   | o
o .   . - .   . - .   . - . - . - .   .   .   . - . - . - . o  o 2   2 - 2   2 - 2   2 - 2 - 2 - 2   2   5   4 - 4 - 4 - 4 o
o |   |   |   |               |   |   |                     o  o |   |   |   |               |   |   |                     o
o . - .   . - . - . - .   . - .   .   .   . - . - .   . - . o  o 2 - 2   2 - 2 - 2 - 2   2 - 2   2   2   2 - 2 - 2   2 - 2 o
o     |   |   |   |   |           |   |   |       |   |   | o  o     |   |   |   |   |           |   |   |       |   |   | o
o .   . - . - . - .   .   . - . - . - .   . - . - . - . - . o  o 6   2 - 2 - 2 - 2   2   2 - 2 - 2 - 2   2 - 2 - 2 - 2 - 2 o
o |       |   |                   |   |   |           |     o  o |       |   |                   |   |   |           |     o
o .   . - .   .   . - .   . - . - . - .   .   . - . - . - . o  o 6   2 - 2   2   2 - 2   2 - 2 - 2 - 2   2   2 - 2 - 2 - 2 o
o     |   |   |   |   |   |   |   |   |   |   |       |     o  o     |   |   |   |   |   |   |   |   |   |   |       |     o
o .   .   .   . - . - . - . - .   .   .   . - . - .   . - . o  o .   2   2   2 - 2 - 2 - 2 - 2   2   2   2 - 2 - 2   2 - 2 o
o             |           |   |   |   |   |   |       |   | o  o             |           |   |   |   |   |   |       |   | o
o . - . - . - .   .   .   . - . - . - . - . - .   .   . - . o  o 2 - 2 - 2 - 2   7   8   2 - 2 - 2 - 2 - 2 - 2   2   2 - 2 o
o |       |       |   |   |   |   |   |   |   |   |         o  o |       |       |   |   |   |   |   |   |   |   |         o
o . - .   .   . - .   .   . - .   .   .   . - . - . - .   . o  o 2 - 2   2   7 - 7   8   2 - 2   2   2   2 - 2 - 2 - 2   2 o
o         |               |   |   |   |   |   |       |   | o  o         |               |   |   |   |   |   |       |   | o
o .   . - .   . - . - . - .   . - .   .   . - . - . - .   . o  o 2   2 - 2   2 - 2 - 2 - 2   2 - 2   2   2 - 2 - 2 - 2   2 o
o |   |       |   |           |       |       |   |   |   | o  o |   |       |   |           |       |       |   |   |   | o
o . - . - .   .   . - . - .   .   . - . - . - .   .   . - . o  o 2 - 2 - 2   2   2 - 2 - 2   2   2 - 2 - 2 - 2   2   2 - 2 o
o |   |   |   |           |       |       |   |       |   | o  o |   |   |   |           |       |       |   |       |   | o
o . - .   .   . - . - . - . - . - .   . - . - .   .   .   . o  o 2 - 2   2   2 - 2 - 2 - 2 - 2 - 2   2 - 2 - 2   9   2   2 o
o     |   |       |                   |   |   |   |         o  o     |   |       |                   |   |   |   |         o
o .   . - . - .   .   .   . - . - . - . - . - .   .   .   . o  o .   2 - 2 - 2   2   .   2 - 2 - 2 - 2 - 2 - 2   9   .   . o
o                                                           o  o                                                           o
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo  ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

Finite-size scaling

Finite-size scaling

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  23 / 31

Finite-size scaling

Finite-size scaling

We want to know for which p’s we have σ_{∞}^{2}(p) ≤ h(θ_{∞}(p))^{2}. What we have is σ_{L}(p)’s and θ_{L}(p)’s for finite L, with error bars from Monte Carlo sampling. How do we connect the two? What is finite-size scaling — what can (and can’t) it do for us?

FSS hypothesis (Fisher 1971, Cardy 1998, …):

σ_{L}(p) = σ_{∞}(p)F (L/ξ(p)),

where the correlation length behaves as ξ(p) ∼ |p − p_{c}|^{−ν} as p → p_{c}. Also, σ_{∞}(p) ∼ (p − p_{c})^{ρ} as p ↘ p_{c}. (Similar scaling applies for θ as well as σ.) That is, corrections enter only through the ratio L/ξ. There are two regimes: L ≫ ξ (infinite-system values are approached), or not (finite-size effects are apparent).

Known properties of the scaling function F: (1) it goes to 1 as L → ∞, i.e. σ_{L} approaches σ_{∞} … eventually. (2) As p ↘ p_{c}, F (x) ∼ x^{−ρ/ν}.

For this project, I don’t want to use property (2) — I want to know more about σ and θ than merely their near-critical behavior. Can I use property (1) — when is L big enough that finite-size effects are overcome?

This L ≫ ξ case is in contrast to my disseration work (on a different model, the spatial-permutation model of Ueltschi and Betz), where L ≪ ξ for most feasible L’s and the critical behavior (near T_{c}) is in fact the principal object of interest.

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  24 / 31

Finite-size scaling: Clusters

Here are 200 × 200 2D lattices with p = 0.2, 0.3, 0.4, 0.5, 0.6, 0.7. Singleton clusters are marked grey; clusters of size bigger than 1 are marked with randomly selected colors. The correlation length ξ(p) is the average diameter of non-infinite clusters. It diverges to infinity as p approaches p_{c} from either side.

Intuition: When L ≫ ξ, if you find the largest cluster in the L-box, you can be sure you’ve found the unique infinite cluster within the infinite lattice. When L ≪ ξ, you may have mistakenly found a large but finite cluster (finite-size effects).

J. Kerl (Arizona)  Lattice quadrupling  June 10, 2009  25 / 31

Finite-size scaling

Finite-size scaling: raw data

See the next slide for some data, obtained as follows.

2D: For p from 0.450 up to 0.550 in steps of 0.002:

For L from 20 to 100 in steps of 10:

For each of three trials: Plot π_{L}^{2}(p) or g(θ_{L}(p)).

3D: For p from 0.241 up to 0.279 in steps of 0.001:

For L from 20 to 75 in steps of 5:

For each of three trials: Plot σ_{L}^{2}(p) or h(θ_{L}(p)).

Finite-size scaling

Finite-size scaling: raw data

As L increases, the curves approach the expected infinite-lattice shapes … but how quickly?

Finite-size scaling: raw data transposed

The key to visualizing the scaling behavior is to plot the growth of the data as a function of L, with p values as data series. For p outside [0.252,0,261] (3D), σ^{2} and h(θ) have reached their infinite-lattice values, as L has passed ξ. For intermediate p, finite-size effects apply.

Finite-size scaling: 2D comparison

Here we select out L = 100 for 2D and treat it as the infinite limit. (For p from 0.460 to 0.506, we do not have L ≫ ξ.) It is intuitively clear that g(θ) beats σ^{2} by a wide margin — not only at p = p_{c} = 0.5 (Perseguers et al.) but for all p reliably far from p_{c} (L ≫ ξ). I do not doubt that an FSS analysis for p near p_{c} (L ≪ ξ) will reach the same conclusion.

Finite-size scaling: 3D comparison

Next we select out L = 65 for 3D and treat it as the infinite limit. (For p from 0.252 to 0.261, we do not have L ≫ ξ.) Here, h(θ) and σ^{2} are quite close. There is a region (p = 0.253 to 0.257) where it appears that h(θ) beats σ^{2}, and a region (p = 0.258 to 0.274) where it appears that the opposite is true.

Improved data accuracy (more CPU time) will reduce the error bars. Regardless, though, when error bars nearly overlap, one must use statistical confidence levels to quantify the apparent inequality σ^{2} < h(θ) or σ^{2} > h(θ).

Conclusions and next steps

Conclusions thus far: In 2D, the doubled lattice beats the non-doubled lattice. In 3D, there is a range of p’s for which the quadrupled lattice appears to beat the non-quadrupled lattice by a narrow but statistically significant margin.

Next steps:

• Re-run the simulations with periodic rather than free boundary conditions. This gives faster convergence in L of σ_{L}(p) and θ_{L}(p) to σ(p) and θ(p), respectively. Also use larger values of N in order to reduce the sample variance of σ and θ.

• Consider broader ranges of p; use larger values of L for 2D to confidently reach L ≫ ξ.

• Obtain a numerical estimate of ξ for 2D and 3D.

• Do finite-scaling for p near p_{c} (L ≪ ξ) to determine critical exponents and obtain values for π, σ, θ.

• In the computations done thus far, three runs were done for each value of L and p. This gives a rough visual error bar. For selected values of p, one should do k ≫ 3 trials. Treat those k trials of σ_{L}(p) and θ_{L}(p) as normally distributed about their respective sample means. The statistical question becomes, at what confidence level can we state that the sample mean of g(θ) exceeds that of σ^{2}?