Emergence of typical entanglement in two-party random processes

1. Introduction

• Typical pure states under the Haar measure are nearly maximally entangled for large systems, motivating generic entanglement as a way to simplify multipartite classifications.The introduction notes that multipartite entanglement has many locally inequivalent classes.Source: §1 · p. 2
• The paper proves that generic entanglement properties can be obtained in polynomially many steps in a two-party random process.It also aims to explain the approach to the regime of generic behavior.Source: §1 · p. 2
• The work also presents a classical simulation approach, examines the rapid-spread and stationary phases, and investigates mixed-state and multipartite settings.It reports numerical similarities between classical and quantum correlations and describes a simpler tripartite entanglement description based on typical entanglement.Source: §1 · p. 2
• The paper connects abstract results about typical entanglement under an unbiased pure-state distribution with entanglement distributions produced by random local interactions.Source: §1 · p. 3

2. Random two-party interactions

• Random two-qubit interactions are motivated by local interactions in nature and modeled as randomly selected gates on pairs of qubits.The process is described as generating a distribution of pure states that approaches the flat distribution over time.Source: §2 · p. 3

2.1. The random walk

• Each random-walk step selects a distinct qubit pair, applies independently Haar-chosen single-qubit unitaries, then applies a CNOT between them.The CNOT target is the second selected qubit and its control is the first.Source: §2.1 · pp. 3–4

2.2. Converges to uniform distribution

• The process converges to the uniform distribution on pure states, but convergence of the full distribution is exponentially slow in the number of qubits.The slow rate raises the question of whether statements based on the unitarily invariant distribution are physically relevant on feasible timescales.Source: §2.2 · p. 4

2.3. Asymptotic Entanglement Distributions

• For large systems, the average Haar-measure entanglement is nearly min(N_A, N_B), and deviations from the mean become exponentially less likely as δ² increases.The subsystem sizes are taken with N_A ≤ N_B and N_A + N_B = N.Source: §2.3 · p. 4

3. Theorem 1: Maximal average is achieved efficiently

• Generic entanglement distributions can be achieved to any precision with a number of steps polynomial in system size.The argument uses the fact that many states share an entanglement value, allowing a coarser state space to be sampled.Source: §3 · p. 5
• The theorem's maximal-entanglement statement is most relevant when the subsystem-size difference t is large; for t=O(1), maximal entanglement N_A is not exactly achieved.Source: §3 · p. 5

3.1. Guide to the proof of Theorem 1

• The proof bounds entanglement using reduced-state purity, then tracks squared Pauli-expansion coefficients through a small Markov chain and analyzes its spectral gap.The spectral gap controls the slowest-decaying contribution to convergence.Source: §3.1 · p. 5

3.2.1. Linear algebra in the space of Hermitian operators

• The linear-algebra setup expands Hermitian operators in an orthonormal Pauli-product basis and expresses tracing out a subset of qubits in that representation.Source: §3.2.1 · pp. 6–7

3.2.2. Back to our problem

• The relevant positive coefficients ξ_n(p)^2 are mapped to a classical Markov chain, whose rapid mixing is used to determine their evolution.Source: §3.2.2 · p. 7

3.3. Evolution of the coefficients

• The random gate evolution of squared coefficients can be represented by a Markov chain on strings in {0, x, y, z}^N.The argument assumes independent single-qubit gates satisfying Requirement 1, which holds for both Haar-random gates and stabilizer gates.Source: §3.3 · pp. 7–8

3.3.1. Basic aspects

• Averaging over the independent gates makes the coefficient update Markovian, despite its apparent dependence on non-positive coefficients.The resulting update replaces the selected pair's symbols according to the gate-induced map.Source: §3.3.1 · pp. 8–9, Table 1 · p. 9

3.3.2. The mapping to a Markov Chain

• To sample a transition, choose two distinct qubits uniformly and independently replace each nonzero symbol with a uniformly chosen x, y, or z.A zero symbol remains zero; symbols at all other positions are unchanged.Source: §3.3.2 · p. 9
• Starting the chain from the initial squared coefficients reproduces their expected distribution after n steps, enabling subsystem-purity probabilities to be obtained from states supported within the subsystem.The relevant event is that the set of nonzero positions is contained in A.Source: §3.3.2 · pp. 9–10

3.4.1. Reduction of the chain

• Tracking only the nonzero positions gives a Markov chain because transitions depend on the current subset, with additions and removals determined by the selected pair.For a missing element, the stated addition probability is 2/3 when paired with an element already in the subset; an existing element can be removed when paired with another existing element.Source: §3.4.1 · pp. 10–11

3.4.2. Dealing with the isolated state

• The empty subset is isolated and retains its initial probability, so the analysis can restrict to nonempty subsets while accounting for that contribution separately.The probability of the empty state remains equal to its value at time zero.Source: §3.4.2 · p. 11
• On the nonempty state space, irreducibility and positive self-transition probabilities establish ergodicity and convergence to a unique stationary distribution.The chain is also shown to be reversible, which supports identifying that stationary distribution.Source: §3.4.2 · p. 11, §3.4.3 · p. 12

3.4.4. Limits

• The stationary-chain limit gives the long-time value of the expected purity-related quantity used to evaluate subsystem entanglement.The section connects this limit to the reduced-chain probability that the subset is contained in A.Source: §3.4.4 · p. 12

3.4.5. Mixing of the reduced Markov Chain

• The reduced chain has spectral gap at least 4/9N(N −1), and its statistical distance contracts exponentially at rate at most 1 −1/3N.The eigenvalue bounds then control convergence from any initial distribution.Source: §3.4.5 · pp. 13–14, §3.4.6 · p. 15
• Path coupling compares adjacent subsets through shared updates, with their distance sometimes increasing or decreasing by one and otherwise unchanged.This comparison leads to exponential contraction and the spectral-gap bound.Source: §3.4.5 · pp. 13–14

3.4.6. End of proof of the main theorem

• The proof of the main theorem combines the nonempty-chain convergence with the separately accounted-for empty-state contribution.The final argument uses the statistical distance between the evolving chain and its stationary distribution.Source: §3.4.6 · pp. 14–15

4. Efficient simulation of process on classical computer

• The process can be simulated on a classical computer with polynomial effort in N using efficiently parameterized stabilizer states.The stated equivalence concerns obtaining the same statistics, not reproducing every general quantum state.Source: §4 · pp. 15–16
• For random pure stabilizer states, entanglement takes integer values, and its distribution concentrates around a nearly maximal average as N increases.The paper notes that the integer-valued entanglement produces dramatic jumps in a single realization.Source: §4 · p. 16, Figure 2 · p. 17
• The average-behavior correspondence is explained by the shared expected purity of the flat stabilizer-state distribution and the unitarily invariant measure.The paper presents this as the reason averaged stabilizer evolutions reproduce the general-state behavior.Source: §4 · p. 16
• The stabilizer random walk reproduces the average purity evolution of the general-state process.The average over 20 realizations is reported to behave like that of general states.Source: §4 · p. 16, Figure 3 · p. 17

5. Two phases in approach to typical entanglement

• The approach has two phases: entanglement first increases and spreads rapidly, then is spread throughout the system.The transition between them can be marked by τsat, τcutoff, or τvol.Source: §5 · p. 17

5.1. Saturation moment

• Average block entanglement grows essentially linearly with time before becoming nearly maximal and practically constant after τsat.The saturation time can be specified by when the average-entanglement gradient is within a fixed accuracy ε of 1.Source: §5.1 · p. 17, Figure 4 · p. 18

5.2. Cut off moment

• For general states, total variation distance to the asymptotic entanglement distribution stays near 1 before falling to 0, with a sharper fall as system size increases.The curves are rescaled to meet where TV ≃ 0.5; the authors also observe an apparent cutoff in the stabilizer process.Source: Figure 5 · p. 19, §5.2 · pp. 19–20
• For larger N, the cutoff becomes increasingly pronounced in stabilizer-state simulations, and the authors conjecture a step-function limit as N → ∞.Stabilizer states are used to evaluate entanglement efficiently at larger sizes.Source: §5.2 · p. 19, Figure 6 · p. 20

5.3. The area to volume scaling transition

• With nearest-neighbour interactions, entanglement scales as the area at small times and as the smaller block's volume at large times.At longer times, the two-qubit unitaries combine into global unitaries; τvol marks the transition between the scaling regimes.Source: §5.3 · p. 21, Figure 7 · p. 21

6. Multipartite and mixed states

• The unitarily invariant measure does not uniquely specify a mixed-state distribution; increasing the purification environment concentrates it around the maximally mixed state.The ambiguity concerns the radial distribution inside the Bloch sphere and depends on environment size.Source: §6 · p. 22
• As the environment grows, the reduced AB state becomes more mixed and its entanglement becomes negligible and ultimately disappears.The paper measures mixed-state entanglement using logarithmic negativity.Source: §6 · p. 22
• Mutual information behaves similarly to quantum correlations in the two-particle-interaction random-walk simulations.The simulations quantify quantum correlations with logarithmic negativity and combined classical and quantum correlations with mutual information.Source: §6 · p. 23, Figure 9 · p. 23
• The phase-space diagram shows average flow toward an attractor, whose coordinates are the entanglement across A+B|C and the average entanglement across A|B.For the illustrated system, N=10, NA=3, NB=3, and NC=4; the upper-right region is physically unrealizable.Source: §6 · p. 23, Figure 10 · p. 24

6.1. Simplified multipartite description

• For tripartite systems, the paper conjectures that the six bipartite entanglement averages are determined by E(A|B) and E(A+B|C).The proposed uniqueness argument relies on determining party sizes from these averages, including a monotonicity condition that the paper describes as reasonable to expect.Source: §6.1 · pp. 24–25
• The proposed simplification may extend beyond three parties, potentially reducing the number of parameters needed to describe multipartite entanglement.This extension is presented as a possibility, not an established result.Source: §6.1 · p. 25

7. Discussion and Conclusion

• Average entanglement approaches its unitarily invariant value within O(N^3) steps, and the proof tracks reduced-subsystem purity in a smaller state space.The process can also be simulated efficiently on a classical computer using stabilizer states.Source: §7 · p. 25
• The observed phases are rapid entanglement spreading followed by entanglement suffused throughout the system; the cutoff is favored as a practical boundary between them.It marks the time when the entanglement distribution is, for practical purposes, that of unbiased pure states; for nearest-neighbor interactions, the later phase exhibits volume scaling.Source: §7 · p. 25
• Efficient generation of generic entanglement from two-qubit gates supports the relevance of protocols relying on typical entanglement [25].The paper presents this as a relevance claim, not a demonstration of those protocols.Source: §7 · p. 25
• Average-purity-based multipartite entanglement measures can be addressed with the established results, whereas entanglement of formation requires extensions beyond this paper’s scope.Source: §7 · p. 25
• The analysis concerns infinite temperatures, while adapting it to finite temperatures would require analyzing a more complicated Markov process.The authors state that basic ideas carry over and may enable rigorous convergence-rate results.Source: §7 · p. 26
• Further study is needed to establish how the saturation, cutoff, and volume-scaling moments relate to one another.The paper suggests analyzing these relations using tools for studying cutoff effects.Source: §7 · p. 26

8. Appendix A: Uniform (Haar) measure on the unitary group

• The unitarily invariant measure is a Haar measure and serves as the pure-state analogue of a flat, unbiased distribution.A flat distribution reflects no bias with respect to the objects being sampled.Source: §8 · p. 29
• Invariance under unitary transformations uniquely specifies the distribution on pure states; for one qubit it is uniform over the Bloch sphere.Source: §8 · p. 29, Figure 11 · p. 29
• To sample from the measure, apply a randomly drawn unitary to an arbitrary fixed pure state.The appendix points to for an explicit procedure.Source: §8 · p. 29

9. Appendix B: Randomizing properties of Haar measure

• The appendix states a bilinear-function lemma for two Pauli operators and a unitary drawn from Haar measure on U(2).Its proof uses the conjugation trick and the coefficient identities established for randomly transformed Pauli operators.Source: §9 · pp. 30–31
• The random vector (rx, ry, rz) has a distribution invariant under permutations, and for u,u′ ∈ {x, y, z}, E[ru ru′] = δu,u′/3.The coefficients are defined by ru = Tr(σu TσaT†)/2 for u ∈ {0, x, y, z}.Source: §9 · p. 30
• Haar invariance under conjugation preserves the distribution of a randomly transformed Pauli operator, enabling the appendix’s symmetry arguments.The appendix applies this conjugation trick to relate transformed Pauli coefficients under coordinate permutations and sign changes.Source: §9 · p. 30

• Stabilizer operators are tensor products of Pauli operators and the identity, while stabilizer states admit polynomially many parameters in the number of qubits [29].Source: §10 · pp. 31–32
• A generator set of N mutually commuting, independent stabilizer operators on N qubits uniquely determines a stabilizer state.The state satisfies g_k|ψ⟩ = |ψ⟩ for every generator.Source: §10 · p. 32
• The GHZ state is given as an example of a state defined by a generator set.Source: §10 · p. 32
• Bipartite entanglement of a stabilizer state takes only integer values [31, 32].Source: §10 · p. 32
• A stabilizer group defines a non-trivial stabilizer state exactly when its elements commute and none equals −I.Source: §10 · p. 32