Optimal quantum (tensor product) expanders from unitary designs

1. Problem Statement and Motivation

The Core Problem:
The paper addresses the construction of quantum expanders. A quantum expander is a quantum channel (a completely positive, trace-preserving map) with a small number of Kraus operators (low "Kraus rank" $d$) but a large spectral gap. The spectral gap determines the rate of convergence to equilibrium and the decay of correlations.

• Optimality: A channel is considered an "optimal expander" if its second-largest singular value, $s(\Phi)$, scales as $O(1/\sqrt{d})$. This matches the theoretical lower bound for such channels.
• The Challenge: While random constructions using Haar-distributed unitaries are known to produce optimal expanders with high probability, sampling from the Haar measure is computationally expensive and requires a large amount of randomness.
• The Question: Can optimal expanders be constructed by sampling Kraus operators from Unitary Designs (finite sets of unitaries that mimic the statistical moments of the Haar measure up to order $k$), which are more efficient to generate and implement?

Specific Goals:

1. Determine if sampling Kraus operators from a 2-design yields an optimal expander for standard quantum channels ($k=1$).
2. Determine if sampling Kraus operators of the form $U^{\otimes k}$ from a $2k$-design yields an optimal $k$-copy tensor product expander.

2. Methodology and Technical Tools

The author employs a probabilistic approach combined with advanced random matrix theory to bound the operator norm of the difference between a random channel and its expectation.

Key Definitions:

• Quantum Channel: $\Phi(X) = \frac{1}{d} \sum_{s=1}^d K_s X K_s^*$.
• Tensor Product Expander: A channel where the Kraus operators are $K_s = U_s^{\otimes k} / \sqrt{d}$. The goal is to approximate the "twirling" channel $\Pi^{(k)}$, which averages over the Haar measure.
• Unitary $t$-Design: A probability measure $\mu$ on $U(n)$ such that the $t$-th moment matches the Haar measure: $\mathbb{E}_{U \sim \mu}[U^{\otimes t} \otimes \bar{U}^{\otimes t}] = \mathbb{E}_{U \sim \mu_H}[U^{\otimes t} \otimes \bar{U}^{\otimes t}]$.

The Proof Strategy:

1. Matrix Representation: The quantum channel $\Phi$ is mapped to a matrix $M_\Phi$ acting on the tensor product space. The expansion property is equivalent to bounding the operator norm $\|M_\Phi - \mathbb{E}[M_\Phi]\|_\infty$.
2. Centered Random Matrix: Define $X = M_\Phi - \mathbb{E}[M_\Phi]$. The goal is to show $\|X\|_\infty \leq \frac{2}{\sqrt{d}}(1 + \delta)$.
3. Application of Recent Random Matrix Bounds: The paper utilizes Theorem 1.5, a result from Bandeira, van Handel, and Vershynin (specifically [6, Corollary 2.17]), which provides bounds on the operator norm of sums of independent, non-homogeneous random matrices with dependence.
   • The bound depends on three parameters:
     • $\sigma(X)$: Related to the variance of the matrix.
     • $\upsilon(X)$: Related to the covariance structure.
     • $R(X)$: The maximum norm of individual summands.
4. Moment Calculations:
   • To compute these parameters, the author calculates expectations of products of unitaries.
   • Crucial Step: The calculation of the covariance parameter $\upsilon(X)$ requires evaluating moments of order $2k$ (specifically $\mathbb{E}[U^{\otimes 2k} \otimes \bar{U}^{\otimes 2k}]$). This is why the paper requires $2k$-designs (for $k$-copy expanders) rather than just $k$-designs. The author uses Weingarten calculus to explicitly compute these moments for the Haar measure and argues that a $2k$-design suffices to replicate these values.

3. Key Contributions and Results

The paper establishes two main theorems regarding the optimality of expanders constructed from unitary designs.

A. Case $k=1$ (Standard Quantum Expanders)

• Setup: Kraus operators are $K_s = U_s / \sqrt{d}$ where $U_s$ are sampled independently from a 2-design.
• Result (Theorem 2.4 & Corollary 2.5):
  • If the number of Kraus operators $d$ satisfies $d \gg (\log n)^4$, then with high probability ($1 - 1/n$), the random channel is an optimal expander.
  • Specifically, the second singular value satisfies:
    $$s(\Phi) \leq \frac{2}{\sqrt{d}} \left(1 + O\left(\frac{1}{(\log n)^{\epsilon/6}}\right)\right)$$
  • This matches the theoretical lower bound $2/\sqrt{d}$ asymptotically.
• Significance: This proves that 2-designs (which can be finite and efficiently implemented, e.g., the Clifford group) are sufficient to generate optimal expanders, removing the need for full Haar randomness.

B. Case $k \geq 1$ (Tensor Product Expanders)

• Setup: Kraus operators are $K_s = U_s^{\otimes k} / \sqrt{d}$ where $U_s$ are sampled independently from a $2k$-design.
• Result (Theorem 3.4 & Corollary 3.5):
  • Under the same regime ($d \gg (\log n)^4$), the random channel is an optimal $k$-copy tensor product expander.
  • The bound holds with high probability ($1 - 1/n^k$):
    $$\|\Phi - \Pi^{(k)}\|_\infty \leq \frac{2}{\sqrt{d}} \left(1 + O\left(\frac{k^C}{(\log n)^{\epsilon/6}}\right)\right)$$
  • Here, $C$ is a constant depending on $k$.
• Comparison: This improves upon recent work by Fukuda (2024), which achieved a bound of $O(\sqrt{k \log n}/\sqrt{d})$. Lancien's result achieves the optimal $O(1/\sqrt{d})$ scaling, though it requires sampling from a $2k$-design (vs. $k$-design in Fukuda's work) and a slightly larger $d$.

4. Significance and Implications

1. Derandomization: The work is a significant step toward derandomization in quantum information. It demonstrates that complex properties (optimal expansion) achievable with Haar-random unitaries can be replicated using Unitary Designs, which are finite, structured, and efficiently simulatable.
2. Practical Implementation: Since explicit constructions of 2-designs (like the Clifford group) and approximate $2k$-designs (via short-depth random quantum circuits) exist, these results imply that optimal expanders can be efficiently constructed in practice.
   • Example: A random channel using Kraus operators from the $N$-qubit Clifford group is likely an optimal expander.
3. Theoretical Insight: The paper clarifies the necessity of the design order. It shows that to control the covariance (and thus the spectral gap) of the random matrix, one needs moments up to order $2k$. This suggests that $k$-designs might be insufficient for optimal expansion in the tensor product setting, a question left open for future investigation.
4. Robustness: The results hold for approximate designs (e.g., random circuits of depth $\text{poly}(\log n)$), making the findings highly relevant for near-term quantum devices where exact designs are hard to implement.

5. Limitations and Future Directions

• Regime of Validity: The results assume the local dimension $n$ grows while $k$ is fixed (or grows very slowly, $k \ll \log \log n$). The constants $C_k$ in the bounds scale poorly with $k$ (roughly $k^k$), limiting the immediate applicability for very large $k$.
• Design Order: The paper leaves open whether a $k$-design is sufficient for $k$-copy expanders, or if the $2k$-design requirement is an artifact of the proof technique (controlling the covariance matrix).
• Explicit Constructions: While the paper proves the existence of optimal expanders within random subsets of designs, finding a deterministic explicit construction remains an open problem.

In summary, Lancien's paper provides a rigorous mathematical proof that Unitary Designs are a powerful and efficient resource for constructing optimal quantum expanders, bridging the gap between theoretical random constructions and practical, implementable quantum protocols.