Mixed symmetries of S_n: immanants in the sampling of U(d) submatrices

This paper presents results on the mean and higher moments of immanants of submatrices from Haar-distributed unitary matrix ensembles, based on a talk given by Trevor Welsh at ISQS29 in Prague in July 2025.

The Gist

Imagine you have a giant, perfectly shuffled deck of cards, but instead of 52 cards, it has $d$ cards, and they are arranged in a complex, multi-dimensional grid called a "unitary matrix." This grid represents a quantum system where everything is perfectly mixed according to the rules of chance (the "Haar measure").

Now, imagine you reach in and pull out a small square piece of this grid, say a $n \times n$ section. The paper asks a very specific question: If you calculate a special number (called an "immanant") for this small piece, how big is that number likely to be, on average, if you keep pulling out new random pieces?

Here is a breakdown of the paper's findings using simple analogies:

1. The Three Types of "Numbers" (Determinants, Permanents, and Immanants)

To understand the paper, you first need to understand the three types of numbers the authors are measuring. Think of these as different ways to score a game played with the numbers in your $n \times n$ grid:

• The Determinant (The "Anti-Social" Score): This is a classic math formula where you add up products of numbers, but you subtract some of them based on a strict rule. It's like a game where players cancel each other out. In physics, this describes fermions (particles like electrons that hate being in the same spot).
• The Permanent (The "Social" Score): This is similar to the determinant, but you never subtract. You just add everything up. It's like a game where everyone gets a point regardless of who they are. In physics, this describes bosons (particles like photons that love to clump together).
• The Immanant (The "Mixed" Score): This is the paper's main focus. It's a middle ground. Imagine a game where the rules change depending on the "personality" of the particles. Some particles act like the "Anti-Social" type, some like the "Social" type, and some are a mix. The "Immanant" is the score calculated using these mixed rules. The paper looks at every possible "personality" (mathematically called partitions of $n$) to see how the score behaves.

2. The Main Discovery: The Average Score

The authors wanted to know: If I pick a random $n \times n$ piece from a giant $d \times d$ grid, what is the average size of the square of this Immanant score?

They found a beautiful, simple rule:
The average size depends entirely on the ratio of two "sizes" (dimensions):

1. How many ways the "personality" (the Immanant rule) can be arranged for $n$ particles.
2. How many ways that same "personality" can be arranged in the giant $d$-dimensional universe.

The Analogy:
Imagine you have a specific dance move (the Immanant rule).

• The first number is how many dancers you need to do that move perfectly in a small room ($n$).
• The second number is how many dancers you need to do that move in a massive stadium ($d$).
  The paper proves that the average "loudness" (the squared score) of the dance in the stadium is simply the ratio of the small room's capacity to the stadium's capacity for that specific dance.

They also found that for very large stadiums (large $d$), the average loudness drops off predictably, roughly like $1/d^n$.

3. The "Pecking Order" of Scores

The paper also looked at which "personality" rules produce louder or quieter scores on average. They discovered a "pecking order" (called dominance order):

• Some rules (like the "Social" Permanent) tend to produce larger average scores.
• Other rules (like the "Anti-Social" Determinant) tend to produce smaller average scores.
• The "Mixed" rules fall somewhere in between, depending on exactly how they are mixed.

Think of it like different types of noise in a room. Some types of noise (Permanents) are naturally louder than others (Determinants), and the paper maps out exactly how much louder one is compared to the other.

4. The Hard Part: The "Second Moment" (The Variance)

Calculating the average score was the easy part (the "First Moment"). The paper also tried to calculate the Second Moment, which is like asking: "How much does the score fluctuate? Is the score always close to the average, or does it sometimes go wild?"

This is much harder. It's like trying to predict not just the average height of a crowd, but how much the heights vary from person to person.

• For the "Anti-Social" (Determinant) and "Social" (Permanent) cases, the authors found specific formulas.
• For the "Mixed" cases (Immanants), the math gets incredibly messy. The authors had to write a computer program to crunch the numbers for small groups (up to 5 particles).
• They found that while the formulas are complex rational polynomials (fractions with $d$ in them), they can be calculated. They even found a formula for the "leading term" (the most important part of the answer) for groups up to 9 particles.

5. Why Does This Matter? (According to the Paper)

The paper mentions that these calculations are useful for understanding computational complexity.

• In simple terms: If you are trying to build a computer that simulates these quantum particles, knowing the "average" and "fluctuation" of these scores helps prove that the computer would need an impossible amount of time to solve the problem for random inputs.
• It suggests that for certain types of particles (those with "Mixed" symmetries), the problem is just as hard (or hard in a specific way) as the famous "BosonSampling" problem, which is known to be very difficult for classical computers.

Summary

The paper is a mathematical map. It tells us that if you take a random slice of a quantum universe and calculate a specific "mixed" score (Immanant) for it:

1. The Average: You can predict the average size of this score using a simple ratio of dimensions.
2. The Hierarchy: Some "mixed" rules are naturally louder than others.
3. The Fluctuation: While calculating the exact fluctuations is hard, the authors have provided the tools (and computer-generated results) to figure it out for small groups of particles.

They did this by using a powerful mathematical toolkit called "Weingarten Calculus," which acts like a specialized calculator for averaging over all possible random shuffles of a quantum system.

Technical Summary

Technical Summary: Mixed Symmetries of $S_n$: Immanants in the Sampling of $U(d)$ Submatrices

Problem Statement
The paper addresses the statistical properties of immanants of $n \times n$ submatrices drawn from ensembles of Haar-distributed unitary matrices in $U(d)$, specifically where $n \le d$. While the quantum states of indistinguishable bosons and fermions correspond to the permanent and determinant, respectively, systems of partially distinguishable particles may exhibit mixed permutation symmetries. These states transform under irreducible representations (irreps) of the symmetric group $S_n$ that are neither fully symmetric nor fully antisymmetric. The authors investigate the moments of the squared modulus of these immanants, $|\text{Imm}_\lambda M|^2$, to understand their distribution and (anti)concentration properties. Such analysis is motivated by the potential to establish average-case computational complexity for sampling these matrix functions, a key component in demonstrating quantum computational advantage.

Methodology
The primary mathematical tool employed is Weingarten Calculus, a framework for integrating polynomials of matrix elements over the unitary group with respect to the Haar measure.

1. First Moment (Mean): The authors derive the mean of $|\text{Imm}_\lambda M|^2$ by expanding the immanant definition and applying the Weingarten formula for the second moment of matrix elements ($m=n$). This reduces the integral to a sum over permutations, which is simplified using the orthogonality relations of finite group characters.
2. Second Moment: Calculating the fourth moment of the matrix elements ($m=2n$) to find the mean of $|\text{Imm}_\lambda M|^4$ is significantly more complex. The authors introduce specific subgroups of $S_{2n}$:
   • $V_n$: A subgroup permuting symbols within columns of an $n \times 2$ array (isomorphic to $S_n \times S_n$).
   • $H_n$: A subgroup swapping signs of rows (isomorphic to $\mathbb{Z}_2^n$).
     By exploiting the symmetries of the resulting character sums over these subgroups, the authors reduce the computational complexity of the summation.
3. Asymptotic Analysis: The leading order terms of the moments are extracted to determine the behavior as $d \to \infty$.

Key Contributions and Results

• Exact Formula for the Mean: The paper establishes a closed-form expression for the mean of the squared immanant:
  $$\int_{U(d)} dU \, |\text{Imm}_\lambda M|^2 = \frac{n!}{N^\lambda(d)}$$
  where $N^\lambda(d)$ is a polynomial in $d$ derived from the dimension formula of the $U(d)$ representation labeled by partition $\lambda$. This result generalizes known results for determinants and permanents (reproducing Nezami's findings).

  • Dominance Order: The authors prove that if partition $\lambda$ is dominated by $\mu$ ($\lambda \triangleleft \mu$), the mean of $|\text{Imm}_\lambda M|^2$ is strictly greater than that of $|\text{Imm}_\mu M|^2$ for fixed $d$.

• Algorithmic Formula for the Second Moment: While a general closed-form expression for the fourth moment is not provided for arbitrary $\lambda$, the authors derive an algorithmic formula (Proposition 6.3) that utilizes the symmetries of the subgroups $H_n$ and $V_n$ to reduce the number of terms required for evaluation.

  • Explicit Evaluations: Using this algorithm, the authors provide explicit rational polynomial expressions for the second moment for all partitions $\lambda \vdash n$ with $n \le 5$.
  • Special Cases: For the determinant ($\lambda=(1^n)$), a closed form is derived: $\int |\text{Det } M|^4 = 1/\text{dim}((2n), U(d))$. For the permanent ($\lambda=(n)$), a conjecture is proposed based on the derived structure.

• Leading Term Analysis: The authors derive a formula for the leading coefficient $J_\lambda$ of the fourth moment expansion in powers of $1/d$. This coefficient is shown to be symmetric with respect to the conjugate partition ($J_\lambda = J_{\lambda'}$). Explicit values for $J_\lambda$ are computed for $n \le 9$.

• Numerical Verification: The theoretical predictions are validated against numerical simulations of Haar-random unitaries, showing agreement between the derived rational polynomials and averaged data from $10^4$ to $10^5$ submatrices.

Significance and Claims
The paper claims to provide the first systematic treatment of the moments of immanants for mixed symmetry states in random unitary ensembles. The significance lies in:

1. Theoretical Foundation: Providing explicit $d$-dependent formulae for the first and second moments, which are necessary to analyze the concentration properties of these functions.
2. Complexity Implications: The authors note that understanding these moments is a prerequisite for proving average-case hardness results for sampling immanants, which is relevant to the broader context of BosonSampling and quantum computational advantage.
3. Computational Limits: The work highlights the rapid growth in computational requirements for higher moments, limiting explicit polynomial results to $n \le 5$, while the leading term analysis extends to $n \le 9$.

The authors explicitly state that full proofs of the results are deferred to a future publication, presenting this work as a summary of results and algorithms derived from a talk at ISQS29.