PaperlayerView exact revision on arXiv

Source-linked AI summary

A Tale of Two Walks: Kipnis, Marchioro and Presutti Meet Kac in a Quantum World

Qian Chen, Jingcheng Liu, Minglong Qin, Leonard Schulman, Fang Song, Penghui Yao, Mingnan Zhao

arXiv:2609.38044v1quant-phcs.DSmath.PR

TL;DR

The paper asks whether parallel Kac can achieve rapid Haar twirling and whether KMP mixing stays close to single-particle mixing. It links symmetric-subspace twirling to partition and KMP dynamics, proves mixing results uniform in particle number, and leaves extension beyond the symmetric subspace open.

  • Problem

    The paper asks whether parallel Kac can rapidly mix toward Haar behavior and whether KMP mixing can match single-particle mixing up to a logarithmic factor in the number of vertices.

    Source: §1 · pp. 3–4

  • Method

    It identifies symmetric-subspace twirling with partition resampling and lifts that chain to parallel KMP, using conditional product structure and exact coupling to bound mixing uniformly in particle number.

    Source: §1.1 · p. 5, §1.3 · p. 9

  • Results

    k≥C(log d+log(1/ε)) repetitions suffice for ε-close trace-norm Haar twirling uniformly over t, while t-particle KMP mixing is at most O(log d) times single-particle mixing uniformly over t.

    Source: §1.1 · p. 5

  • Takeaways & Limitations

    Conditional product structure yields near-tight mixing bounds for standard and parallel KMP and supports scalable non-adaptive pseudorandom unitaries over symmetric subspaces.

    Source: §1.3 · p. 9

    The twirling result is confined to the symmetric subspace; extending it to the antisymmetric subspace requires a more complex Schur–Weyl analysis.

    Source: §1.3 · p. 10

Abstract

from arXiv · show

We reveal an unexpected connection between the parallel Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. The twirling channel induced by the parallel Kac's walk on the symmetric subspace is exactly encoded by a classical Markov chain on partitions, which lifts to a parallel KMP process on complete graphs. This correspondence reduces the analysis of the twirling channel to the mixing of the parallel KMP process. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb C^d)^{\otimes t}$ to error $\varepsilon$, uniformly in the number of copies $t$. For the standard KMP process on general graphs, we prove a mixing-time analogue of Aldous's conjecture: at fixed accuracy, the mixing time of the $t$-particle process is at most a constant times the single-particle mixing time multiplied by the logarithm of the number of vertices, uniformly in $t$. As an application, we improve the total variation mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde O(n^3)$ (Kook and Vempala, 2026) to $\widetilde O(n)$, while removing the dependence on the initial distribution. Our main technical contribution is conditional product structure for both parallel and standard KMP processes. Conditioned on suitable auxiliary randomness, the labeled particles evolve independently. Combining this structure with an exact coupling yields mixing bounds uniform in the number of particles for both unlabeled KMP models. These bounds are sharp up to logarithmic factors and imply rapid convergence of the parallel Kac twirling channel on the symmetric subspace.

1 Introduction

The section develops the connection between parallel Kac’s walk and KMP, using conditional product structure and a reduction to establish mixing bounds uniform in the number of particles. It covers symmetric-subspace twirling, KMP mixing on general graphs, and coordinate hit-and-run on the simplex, and discusses a pseudorandom-unitary construction, extensions, and open problems.

1.1 Main Results

  • O(log d + log(1/ε)) repetitions suffice for ε-close Haar twirling on the symmetric subspace, uniformly over all positive integers t.The bound is in trace norm for inputs supported on the symmetric subspace.Source: §1.1 · p. 5
  • O(log d) times the single-particle mixing time bounds the t-particle KMP mixing time on any connected d-vertex graph, uniformly over t.This mixing-time analogue of Aldous’s conjecture applies to the standard KMP chain on general graphs.Source: §1.1 · p. 5
  • O(n(log n + log(1/ε))) bounds coordinate hit-and-run’s total variation mixing time on the n-dimensional standard simplex from any initial distribution.This improves the bound from Kook and Vempala from ˜O(n^3) to ˜O(n), while removing the initial-distribution assumption.Source: §1.1 · p. 6

From parallel Kac’s walk to parallel KMP chain

  • The symmetric-subspace Kac twirling channel is exactly represented by a partition resampling chain that redistributes paired coordinate multiplicities and then sorts them.The chain’s transition matrix matches the twirling channel’s update on coefficients of the type-subspace states.Source: From parallel Kac’s walk to parallel… · p. 7

Conditional product structure and Removal of Dependence on t

1.3 Discussion and Future Work

  • Conditional product structure yields near-tight mixing bounds for standard and parallel KMP, while reduction from parallel Kac’s walk gives a scalable, non-adaptive pseudorandom-unitary construction on symmetric subspaces.Source: §1.3 · p. 9
  • The KMP analysis reduces many-particle mixing to a 2-particle system, raising the question of whether this phenomenon holds for general interacting particle systems; related behavior appears in exclusion processes.Source: §1.3 · p. 9
  • Pillai and Smith established an O(n2 log n) total variation mixing-time bound for Kac’s walk on SO(n), leaving a logarithmic-factor gap above the known Ω(n2) lower bound.The authors ask whether the Kac–KMP connection and conditional product structure can close that gap.Source: §1.3 · p. 9
  • The authors identify extending the symmetric-subspace twirling result to the full space as a next step, which could enable scalable pseudorandom unitaries for quantum cryptography and many-body physics.The antisymmetric subspace lacks the symmetric subspace’s simple orthogonal-state decomposition and induced classical Markov chain, so the extension requires further Schur-Weyl analysis.Source: §1.3 · p. 10

2 Preliminaries

The preliminaries establish notation for probability distributions, Markov chains, partitions, and the symmetric subspace. They also define the Dicke-state basis and multiplicity types used in the paper.

Probability and linear algebra

  • The paper uses the Haar measure on U(d), the unique probability measure invariant under left and right multiplication by unitaries.It also defines Schatten norms and total-variation distance.Source: §2 · p. 11

Probability and Markov chains

  • A finite-state Markov chain is specified by a stochastic transition matrix; stationarity, reversibility, and total-variation mixing time are defined for these chains.The preliminaries also state standard mixing and coupling facts used later.Source: §2 · pp. 12–13

Symmetric subspace

  • The symmetric subspace has generalized Dicke states as an orthonormal basis, indexed by multiplicity vectors whose entries sum to t.The dimension equals the number of distinct multiplicity vectors.Source: §2 · p. 13

Partitions and types

  • A multiplicity vector’s type is the partition obtained by sorting its entries in non-increasing order and removing zeros.The set of multiplicity vectors of a given type defines the associated type class.Source: §2 · p. 14

3 Parallel Kac Converges to Haar in the Symmetric Subspace

The paper studies repeated parallel Kac twirling on the symmetric subspace, where each step combines independent block-Haar randomness with a random permutation. It proves that logarithmically many repetitions in dimension and inverse error suffice, uniformly in the number of copies.

Walk construction

  • Each parallel Kac step multiplies a random permutation matrix by a block-diagonal unitary with independent Haar-random U(2) blocks.The permutation is uniformly random, and the block unitaries act on two-dimensional coordinate pairs.Source: §3 · p. 14

Twirling channels

  • The channel Φt,k_Kac averages the action of k independent parallel Kac steps on the input, while Φt_Haar is the t-fold twirling channel for Haar-distributed unitaries.The Kac channel is formed by iterating the one-step transformation.Source: §3 · pp. 14–15

Main convergence bound

  • O(log d + log(1/ε)) repetitions suffice to approximate Haar twirling on the symmetric subspace to error ε, uniformly over t.The stated threshold is k ≥ c^-1(2 log d + log(2/ε)) for an absolute constant c > 0.Source: §3 · p. 15

4 A Classical Interpretation of Φt

This section represents the symmetric-subspace action of Φt,Kac as a classical Markov chain on partitions, whose mixing governs convergence of the Kac twirling channel to the maximally mixed state on that subspace.

4 A Classical Interpretation of Φt

  • The classical-chain viewpoint reduces analysis of Φt,Kac convergence to mixing of the corresponding partition chain.Source: §4 · p. 16

4.1 Decomposition of Symmetric States under Φt

  • Φt,Kac maps symmetric-subspace states to linear combinations of maximally mixed states ρλ, one for each type λ.BlockHaar diagonalizes in the generalized Dicke basis, and Φt,Perm merges basis states sharing a type.Source: §4.1 · p. 18

4.2 Transition Matrix Interpretation

  • The transition matrix M(t,d) updates the coefficients of the partition-indexed state decomposition and is stochastic, with nonnegative entries and rows summing to 1.Its entries are given by the formula in Lemma 4.5.Source: §4.2 · pp. 18–19

4.3 Markov Chain Interpretation

  • The partition resampling chain has transition matrix M(t,d), exactly encoding the action of Φt,Kac on partition-indexed coefficients.Each update lifts a partition to a multiplicity vector, resamples paired coordinates while preserving their sums, then projects back to a partition.Source: §4.2 · p. 18, §4.3 · p. 20
  • The partition resampling chain is irreducible, aperiodic, and reversible, with a unique stationary distribution.Source: §4.3 · p. 23
  • Detailed balance makes π stationary, and irreducibility and aperiodicity on the finite state space ensure that π is unique.The chain is reversible with respect to π.Source: §4.3 · p. 24

4.4 From Chain Mixing to Channel Mixing

  • Uniform mixing of the partition resampling chain to π controls convergence of repeated Kac twirling to the maximally mixed symmetric-subspace state.Proposition 4.10 relates the chain's mixing after k steps to the channel's convergence.Source: §4.4 · p. 24

5 From Partition Resampling Chain to Parallel KMP Chain

The section connects partition resampling to the parallel KMP chain through successive lifts, using conditional product structure and exact couplings to analyze mixing. It establishes particle-count-uniform mixing bounds for the parallel KMP and partition resampling chains and applies them to convergence of the parallel Kac channel on the symmetric subspace.

5 From Partition Resampling Chain to Parallel KMP Chain

  • A labeled-chain bound for small particle counts and coupling for larger counts yield t-independent mixing bounds for the unlabeled parallel KMP and partition-resampling chains.The section outline identifies these as the route to the mixing-time bound.Source: §5 · p. 25

5.1 The Lifted Chain: Parallel KMP Process

  • The lifted parallel KMP chain tracks full coordinate multiplicities rather than sorted types, has a uniform stationary law, and lumps to partition resampling, which mixes at least as fast.The lifted chain redistributes mass across randomly matched coordinate pairs while preserving total mass.Source: §5.1 · pp. 25–26

5.2 The Labeled Parallel KMP Chain

  • The labeled parallel KMP chain tracks each particle’s site and is irreducible, aperiodic, and reversible with a unique stationary law; forgetting labels recovers a chain that can only converge faster.Its stationary distribution weights labeled configurations according to the multiplicity vectors they induce.Source: §5.2 · pp. 29–30

5.3 Conditional Product Structure of the Labeled Parallel KMP Chain

  • Conditioned on the full sequence of matchings and pair-specific uniform random variables, the labeled configuration has a product structure, so particles evolve independently.The auxiliary randomness reformulates each pair update as independent particle choices using a shared uniform probability.Source: §5.3 · p. 32
  • Conditioned on the matchings and split variables, labeled particles evolve independently; the stationary distribution also has a conditional product representation based on Dirichlet weights.The product structure reduces total-variation analysis to single-particle marginals, while the Dirichlet(1, . . . , 1) distribution is invariant under the random update.Source: §5.3 · pp. 32–34

5.4 Mixing Time of the Labeled Parallel KMP Chain

  • Theorem 5.13 establishes a mixing bound for the labeled parallel KMP chain from any initial state.The supplied theorem passage does not include the bound’s numerical expression.Source: §5.4 · p. 35

5.5 Exact Coupling for the Parallel KMP Chain

  • When |A − C| ≤ h, |B − D| ≤ h, and B, D ≥ L, an exact coupling of uniform updates has mismatch probability at most 3h/(L + 1).The update counts are coupled so that each marginal remains uniform on its respective range.Source: §5.5 · p. 37
  • For t > d^1000, a connected sequence of pair updates and sufficiently close initial states supports a coupling intended to make the chains’ final states agree with high probability.The method addresses particle counts beyond the polynomial-in-d regime where the labeled-chain mixing result already gives O(log d) mixing for the unlabeled chain.Source: §5.5 · pp. 37–38
  • For even d≥4 and t>d^1000, Lemma 5.16 constructs a coupling over T=24 log d rounds from an arbitrary initial pair whose second state is uniform on the simplex.It uses independent uniform perfect matchings; the probability their union graph is disconnected is at most 1/(2d^2).Source: §5.5 · pp. 41–42

5.6 Mixing Time of the Parallel KMP Chain and the Partition Resampling Chain

  • O(log d + log(1/ε)) steps suffice for both the parallel KMP chain and the partition resampling chain to reach total variation distance ε, for every positive integer t.The mixing-time conclusion follows from a bound independent of t.Source: §5.6 · pp. 42, 44

5.7 Convergence of the Parallel Kac Channel

  • Theorem 3.1 gives an absolute-constant bound for channels Φt,k and ΦHaar on any state σ satisfying Tr[(ΠSym ⊗ 1) · σ] = 1, with ΠSym projecting onto ∨tCd and d = 2n.Source: §5.7 · p. 44

6 KMP on General Graphs

This section develops particle-count-uniform mixing bounds for KMP on connected general graphs using labeled-chain and spectral comparisons, and applies them to sharpen the coordinate hit-and-run bound on the standard simplex while removing dependence on the initial point.

6 KMP on General Graphs

  • At fixed accuracy, the KMP mixing time on a connected graph is at most a constant times the single-particle mixing time multiplied by log d, uniformly over particle counts t.The main theorem is stated for connected graphs with d ≥ 2 and every positive integer t.Source: §6 · p. 46

6.1 Labeled KMP Mixing via the Two-Particle Chain

  • The labeled KMP chain has conditional product structure, yielding a mixing bound controlled by the second-largest eigenvalue in absolute value of the two-particle labeled chain.The bound applies to every initial state and uses the two-particle chain's contraction ratio.Source: §6.1 · pp. 47–48

6.2 Spectral Reduction to the Single-Particle KMP Chain

  • The two-particle labeled chain splits into invariant symmetric and antisymmetric subspaces; on the symmetric subspace, its restriction has the same eigenvalues as the unlabeled two-particle KMP chain.The antisymmetric subspace is governed by a Markov chain induced by the single-particle random walk, enabling spectral comparison with the unlabeled chain.Source: §6.2 · pp. 49, 51
  • The two-particle KMP spectrum splits into symmetric and antisymmetric blocks, with the symmetric block matching the standard KMP spectrum and the antisymmetric block matching C.The restrictions to the antisymmetric subspace and C have the same eigenvalues.Source: §6.2 · pp. 52–53
  • The two-particle KMP spectral gap is bounded below by a constant multiple of the single-particle KMP gap, and the antisymmetric block’s top eigenvalue equals the single-particle second eigenvalue.These comparisons connect both spectral blocks to the single-particle chain.Source: §6.2 · p. 54

6.3 Mixing Time of the KMP Chain

  • O(γ^-1(log d + log(1/ε))) steps suffice to mix the KMP chain on any connected d-vertex graph, uniformly over particle counts t.Here γ is the spectral gap of the single-particle random walk.Source: §6.3 · p. 56
  • As an application, the result gives a sharper total-variation mixing-time bound for coordinate hit-and-run on the standard simplex, uniformly over all initial points.Source: §6.3 · p. 57

7 Scalable Non-Adaptive PRU in the Symmetric Subspace

The paper constructs a non-adaptive scalable pseudorandom-unitary family restricted to the symmetric subspace, using parallel Kac steps and pseudorandom primitives. Its security guarantee relies on quantum-secure one-way functions and remains limited to that setting.

7 Scalable Non-Adaptive PRU in the Symmetric Subspace

  • The scalable PRU notion treats security parameter and qubit count independently, with pseudorandomness error negligible in the security parameter alone.This paper considers the non-adaptive variant restricted to the symmetric subspace.Source: §7 · pp. 57–58
  • Assuming quantum-secure one-way functions exist, the paper constructs a non-adaptive scalable PRU family on the symmetric subspace.The construction applies parallel Kac’s walk in this restricted setting.Source: §7 · pp. 57–58
  • The construction approximates parallel Kac steps with polynomial-size circuits using random functions and permutations, then replaces them with quantum-secure pseudorandom primitives.The security argument uses a hybrid argument to transfer pseudorandomness from those primitives to the constructed family.Source: §7 · pp. 58–59
  • Each constructed unitary is efficiently computable because the underlying pseudorandom functions and permutations are efficiently computable.The construction composes r + 1 independently sampled approximate Kac steps.Source: §7 · p. 59

A Continuous KMP Chain

The appendix introduces continuous KMP on general connected graphs and relates it to the discrete KMP chain through moment duality. This relationship supports a continuous-chain mixing bound and applications to the paper’s theorem and corollary.

A Continuous KMP Chain

  • The appendix introduces the continuous KMP chain on a general connected graph.It studies the relationship between this chain and the discrete KMP chain.Source: A Continuous KMP Chain · p. 65
  • Standard KMP moment duality is used to relate the continuous and discrete chains.The appendix derives an upper bound on the continuous chain’s mixing time from this connection.Source: A Continuous KMP Chain · p. 65
  • The continuous-chain connection is used to prove Theorem 6.13 and Corollary 6.17.Source: A Continuous KMP Chain · p. 65

A.1 Moment Duality

The appendix relates continuous and discrete KMP through moment duality, establishing an operator intertwining and equality of eigenvalues. It also analyzes the continuous chain on invariant low-degree polynomial spaces.

A.1 Moment Duality

  • The continuous KMP chain on a general graph has a Markov operator whose polynomial degree is preserved by updates.The spaces of polynomials of degree at most k are invariant under the operator.Source: §A.1 · p. 65
  • The appendix considers spectral gaps of the continuous operator restricted to low-degree polynomial spaces under its stationary distribution.Source: §A.1 · p. 65
  • For fixed r, the moment-duality function F(r, ·) is a polynomial of total degree t, and the duality identity relates continuous- and discrete-chain operators.Source: §A.1 · p. 66
  • The discrete and continuous KMP operators are intertwined by a linear isomorphism, so their spectra are equal.The proof establishes that the functions F(r, ·) span the polynomial space and form a basis.Source: §A.1 · pp. 67–68

A.2 Mixing Time of the Continuous KMP Chain on a General Graph

This section transfers a discrete KMP mixing estimate to the continuous KMP chain on a general graph. The argument approximates continuous-state functions using randomly placed particles and takes the particle count to infinity.

A.2 Mixing Time of the Continuous KMP Chain on a General Graph

  • Lemma A.6 gives an absolute-constant total-variation mixing bound for the continuous KMP chain for every ε in (0, 1).Source: §A.2 · p. 68
  • Placing t particles independently according to v produces counts R, which are used to transfer the discrete-chain estimate to the continuous chain as t tends to infinity.Source: §A.2 · pp. 68–69
  • The transfer uses uniform convergence of the approximating functions ft to f on the continuous simplex to obtain total-variation control.Source: §A.2 · pp. 69–70

A.3 Proof of Theorem 6.13

The proof completes a spectral comparison between the one- and two-particle KMP chains using Lemma A.5. It relates the restrictions of the continuous-chain operator to the corresponding KMP spectral quantities.

A.3 Proof of Theorem 6.13

  • Lemma A.5 relates the restrictions of N(G) to the one- and two-particle KMP chains through their eigenvalues.Source: §A.3 · pp. 70–71

A.4 Proof of Corollary 6.17

The proof identifies coordinate hit-and-run on the standard simplex with continuous KMP on a star graph. A simplex-to-KMP mapping then transfers the continuous-chain mixing bound to hit-and-run.

A.4 Proof of Corollary 6.17

  • Corollary 6.17 states a total-variation mixing-time upper bound for coordinate hit-and-run on Sn for every n ≥ 2 and ε in (0, 1).Source: §A.4 · p. 71
  • Coordinate hit-and-run on Sn is equivalent to continuous KMP on a star graph with n edges, one of which is selected uniformly at each step.Source: §A.4 · p. 71
  • The mapping from the uniform distribution on Sn to µG preserves total variation distance, so the continuous KMP mixing bound also holds for coordinate hit-and-run.Source: §A.4 · pp. 71–72

B Spectrum of C on the Antisymmetric Subspace

The proof characterizes the spectrum of C on the antisymmetric subspace using an eigenbasis of the single-particle KMP transition matrix. The largest value in the stated spectral family occurs for the first two eigenvectors.

B Spectrum of C on the Antisymmetric Subspace

C.1 Proof of Lemma 6.8

The proof computes the edge-averaged operator by separating cases according to whether neither, one, or both particle locations lie on the edge. When both particles are updated, their conditional independence gives four outcomes whose probabilities are averaged over p.

C.1 Proof of Lemma 6.8

  • When neither location lies on the edge, neither particle is affected and the function value is unchanged.This is the no-update case for the edge operator.Source: §C.1 · p. 73
  • When one location lies on the edge, only that particle is updated; conditioned on p, it moves to a or b with probabilities p and 1 − p.The other particle stays at its original location.Source: §C.1 · p. 73
  • When both locations lie on the edge, the particles are reassigned independently given p, producing four outcomes with probabilities p², p(1 − p), p(1 − p), and (1 − p)².Averaging uses E[p²] = E[(1 − p)²] = 1/3 and E[p(1 − p)] = 1/6.Source: §C.1 · p. 74

C.2 Proof of Lemma 6.9

The proof identifies functions on V × V with a tensor product and uses the swap operator to characterize the symmetric and antisymmetric subspaces. Since the averaged operators commute with the swap, both subspaces remain invariant under M(2,G).

C.2 Proof of Lemma 6.9

  • The function space on V × V is identified with R^V ⊗ R^V, and the proof introduces a swap operator on that space.The swap operator is used to distinguish symmetric from antisymmetric vectors.Source: §C.2 · p. 74
  • HSym and HAsym are the +1 and −1 eigenspaces of the swap operator, respectively.Source: §C.2 · p. 74
  • Averaging over p and then over edges gives commutation with the swap, so both eigenspaces are invariant under M(2,G).Source: §C.2 · p. 74
Loading 2609.38044v1…