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

이 논문은 2025년 7월 프라하에서 열린 ISQS29에서 발표된 Trevor Welsh의 강연을 바탕으로, Haar 분포를 따르는 유니터리 행렬 앙상블의 부분 행렬 immanant에 대한 평균 및 고차 모멘트에 관한 결과를 제시한다.

핵심

당신이 $d$개의 카드를 가진 거대하고 완벽하게 섞인 카드 덱을 가지고 있다고 상상해 보세요. 하지만 이 카드는 단순히 52장이 아니라, "유니터리 행렬(unitary matrix)"이라 불리는 복잡한 다차원 격자 구조로 배열되어 있습니다. 이 격자는 모든 것이 확률의 법칙(하르 측도, Haar measure)에 따라 완벽하게 혼합된 양자 시스템을 나타냅니다.

이제 당신은 이 격자에서 $n \times n$ 크기의 작은 정사각형 조각을 하나 꺼낸다고 상상해 보세요. 이 논문은 매우 구체적인 질문을 던집니다: 만약 당신이 이 작은 조각에 대해 특별한 숫자(임만언트, immanant)를 계산한다면, 새로운 무작위 조각들을 계속 꺼낼 때 이 숫자의 크기는 평균적으로 어느 정도가 될까요?

다음은 이 논문의 발견을 쉬운 비유를 사용하여 정리한 내용입니다:

1. 세 가지 유형의 "숫자" (행렬식, 영구식, 그리고 임만언트)

이 논문을 이해하려면 먼저 저자들이 측정하고 있는 세 가지 유형의 숫자를 이해해야 합니다. 이것들은 당신의 $n \times n$ 격자에 담긴 숫자들로 진행되는 게임의 점수를 계산하는 서로 다른 방식이라고 생각하면 됩니다:

• 행렬식 (Determinant, "비사교적" 점수): 이것은 숫자의 곱을 모두 더하되, 특정 규칙에 따라 일부를 빼는 고전적인 수학 공식입니다. 이는 마치 플레이어들이 서로를 상쇄시키는 게임과 같습니다. 물리학에서는 이것이 페르미온(전자처럼 같은 위치에 있기를 싫어하는 입자)을 설명합니다.
• 영구식 (Permanent, "사교적" 점수): 이것은 행렬식과 비슷하지만, 절대로 빼지 않고 오직 더하기만 합니다. 이는 마치 누가 누구든 상관없이 모두가 점수를 얻는 게임과 같습니다. 물리학에서는 이것이 보존(광자처럼 서로 뭉치기를 좋아하는 입자)을 설명합니다.
• 임만언트 (Immanant, "혼합된" 점수): 이것이 이 논문의 핵심 주제입니다. 이것은 그 중간 지점에 있습니다. 입자들의 "성격"에 따라 규칙이 변하는 게임을 상상해 보세요. 어떤 입자들은 "비사교적" 유형처럼 행동하고, 어떤 입자들은 "사교적" 유형처럼 행동하며, 어떤 것들은 그 둘이 섞여 있습니다. "임만언트"는 이러한 혼합된 규칙을 사용하여 계산되는 점수입니다. 이 논문은 가능한 모든 "성격"(수학적으로는 $n$의 분할, partitions of $n$)에 대해 이 점수가 어떻게 작동하는지 살펴봅니다.

2. 주요 발견: 평균 점수

저자들은 알고 싶었습니다: 내가 거대한 $d \times d$ 격자에서 무작위 $n \times n$ 조각을 뽑았을 때, 이 임만언트 점수의 제곱의 평균 크기는 얼마인가?

그들은 아름답고 단순한 규칙을 찾아냈습니다:
평균 크기는 전적으로 두 가지 "크기(차원)"의 비율에 달려 있습니다:

1. $n$개의 입자에 대해 "성격"(임만언트 규칙)을 배치하는 방법의 수.
2. 거대한 $d$차원 우주에서 동일한 "성격"을 배치하는 방법의 수.

비유:
당신에게 특정한 춤 동작(임만언트 규칙)이 있다고 상상해 보세요.

• 첫 번째 숫자는 작은 방($n$)에서 그 동작을 완벽하게 수행하는 데 필요한 무용수의 수입니다.
• 두 번째 숫자는 거대한 경기장($d$)에서 그 동작을 수행하는 데 필요한 무용수의 수입니다.
  논문은 특정 춤의 평균적인 "음량"(제곱된 점수)이 단순히 그 특정 춤에 대한 작은 방의 수용량과 경기장의 수용량 사이의 비율이라는 것을 증명합니다.

또한 그들은 거대한 경기장(큰 $d$)에서 평균 음량이 대략 $1/d^n$의 비율로 예측 가능하게 감소한다는 것을 발견했습니다.

3. 점수의 "서열"

논문은 또한 어떤 "성격" 규칙이 평균적으로 더 크거나 작은 점수를 만들어내는지도 조사했습니다. 그들은 "지배 순서(dominance order)"라고 불리는 서열을 발견했습니다:

• 어떤 규칙들(예: "사교적" 영구식)은 평균적으로 더 큰 점수를 만드는 경향이 있습니다.
• 다른 규칙들(예: "비사교적" 행렬식)은 더 작은 점수를 만드는 경향이 있습니다.
• "혼합된" 규칙들은 정확히 어떻게 섞여 있느냐에 따라 그 사이에 위치합니다.

이것은 방 안의 다양한 종류의 소음과 같습니다. 어떤 종류의 소음(영구식)은 본질적으로 행렬식보다 더 크고, 논문은 그 차이가 얼마나 큰지를 정확하게 지도화합니다.

4. 어려운 부분: "이계 모멘트" (분산)

평균 점수를 계산하는 것은 쉬운 부분이었습니다 ("일계 모멘트"). 논문은 또한 **이계 모멘트(Second Moment)**를 계산하려고 시도했습니다. 이것은 **"점수가 얼마나 요동치는가? 점수가 항상 평균 근처에 머무는가, 아니면 가끔 제멋대로 튀는가?"**를 묻는 것과 같습니다.

이것은 훨씬 더 어렵습니다. 이는 단순히 군중의 평균 키를 예측하는 것이 아니라, 키가 사람마다 얼마나 다양한지를 예측하는 것과 같습니다.

• "비사교적"(행렬식) 및 "사교적"(영구식) 사례의 경우, 저자들은 구체적인 공식을 찾아냈습니다.
• "혼합된" 사례(임만언트)의 경우, 수학적 계산이 믿을 수 없을 정도로 복잡해집니다. 저자들은 적은 수의 입자 그룹(최대 5개까지)에 대해 숫자를 처리하기 위해 컴퓨터 프로그램을 사용해야 했습니다.
• 그들은 이 공식들이 $d$를 포함한 유리 다항식(rational polynomials)이지만 계산 가능하다는 것을 발견했습니다. 심지어 9개 입자 그룹까지의 "주요 항(leading term, 가장 중요한 부분)"에 대한 공식도 찾아냈습니다.

5. 이것이 왜 중요한가? (논문에 따르면)

이 논문은 이러한 계산이 **계산 복잡도(computational complexity)**를 이해하는 데 유용하다고 언급합니다.

• 간단히 말해서: 만약 당신이 이러한 양자 입자들을 시뮬레이션하는 컴퓨터를 만들려고 한다면, 이 점수들의 "평균"과 "변동"을 아는 것은 무작위 입력에 대해 문제를 해결하는 데 불가능할 정도의 시간이 걸린다는 것을 증가하는 데 도움이 됩니다.
• 이는 특정 유형의 입자들(특정한 "혼합" 대칭성을 가진 입자들)에 대해, 이 문제가 매우 어렵다고 알려진 유명한 "보존 샘플링(BosonSampling)" 문제만큼이나 (혹은 특정 방식으로 그만큼) 어렵다는 것을 시사합니다.

요약

이 논문은 수학적 지도입니다. 만약 당신이 무작위 양자 우주의 한 조각을 가져와서 특정 "혼합" 점수(임만언트)를 계산한다면:

1. 평균: 당신은 차원의 비율을 사용하여 이 점수의 크기를 예측할 수 있습니다.
2. 계층: 어떤 "혼합" 규칙은 본질적으로 다른 규칙보다 더 큽니다.
3. 변동: 정확한 변동을 계산하는 것은 어렵지만, 저자들은 소규모 입자 그룹에 대해 이를 파악할 수 있는 도구와 컴퓨터 생성 결과를 제공했습니다.

그들은 모든 가능한 무작위 양자 시스템의 섞임(shuffle)에 대해 평균을 내는 특수 계산기 역할을 하는 "와인가텐트-칼큘러스(Weingarten Calculus)"라는 강력한 수학적 도구 상자를 사용하여 이 작업을 수행했습니다.

기술 요약

기술 요약: $S_n$의 혼합 대칭성: $U(d)$ 부분 행렬 샘플링에서의 이만넌트(Immanant)

문제 정의
본 논문은 $n \le d$인 경우, Haar 분포를 따르는 $U(d)$ 유니터리 행렬 앙상블에서 추출된 $n \times n$ 부분 행렬의 이만넌트(immanant)에 대한 통계적 특성을 다룬다. 구별 불가능한 보존(bosons)과 페르미온(fermions)의 양자 상태는 각각 퍼머넌트(permanent)와 디터미넌트(determinant)에 대응하지만, 부분적으로 구별 가능한 입자 시스템은 혼합된 치환 대칭성을 나타낼 수 있다. 이러한 상태들은 완전 대칭적이거나 완전 반대칭적인 것을 넘어, 대칭군 $S_n$의 기약 표현(irreducible representations, irreps)을 따른다. 저자들은 이만넌트의 절댓값 제곱 $|\text{Imm}_\lambda M|^2$의 모멘트를 조사하여 그 분포와 (반)집중(concentration) 특성을 이해하고자 한다. 이러한 분석은 양자 계산 우위(quantum computational advantage)를 입증하는 데 핵심적인 요소인, 이러한 행렬 함수들을 샘플링하는 것의 평균 사례 계산 복잡도(average-case computational complexity)를 확립하려는 동기에서 비롯되었다.

방법론
주요 수학적 도구로는 **와이겐가르트 계산법(Weingarten Calculus)**이 사용되었는데, 이는 Haar 측도에 따라 유니터리 군 위의 행렬 요소들에 대한 다항식을 적분하는 프레임워크이다.

1. 1차 모멘트 (평균): 저자들은 $|\text{Imm}_\lambda M|^2$의 평균을 구하기 위해 이만넌트의 정의를 전개하고, 행렬 요소의 2차 모멘트($m=n$)에 대한 와이겐가르트 공식을 적용한다. 이는 적분을 치환에 대한 합으로 환원시키며, 이는 유한 군의 캐릭터(character) 직교 관계를 사용하여 단순화된다.
2. 2차 모멘트: 행렬 요소의 4차 모멘트($m=2n$)를 계산하여 $|\text{Imm}_\lambda M|^4$의 평균을 구하는 과정은 훨씬 더 복합적이다. 저자들은 다음과 같은 특정 부분군들을 도입한다:
   • $V_n$: $n \times 2$ 배열 내의 기호들을 치환하는 부분군 ($S_n \times S_n$과 동형).
   • $H_n$: 행의 부호를 바꾸는 부분군 ($\mathbb{Z}_2^n$과 동형).
     이러한 부분군들에 대한 캐릭터 합의 대칭성을 활용함으로써, 저자들은 합산의 계산 복잡도를 줄인다.
3. 점근 분석 (Asymptotic Analysis): $d \to \infty$일 때의 거동을 결정하기 위해 모멘트의 최고 차수 항들을 추출한다.

주요 기여 및 결과

• 평균에 대한 정확한 공식: 본 논문은 제곱 이만넌트의 평균에 대한 폐쇄형 표현식을 확립한다:
  $$\int_{U(d)} dU \, |\text{Imm}_\lambda M|^2 = \frac{n!}{N^\lambda(d)}$$
  여기서 $N^\lambda(d)$는 분할(partition) $\lambda$에 의해 레이블링된 $U(d)$ 표현의 차원 공식으로부터 유도된 $d$에 대한 다항식이다. 이 결과는 디터미넌트와 퍼머넌트에 대한 알려진 결과들을 일반화한다(Nezami의 연구를 재현함).

  • 지배 순서 (Dominance Order): 저자들은 만약 분할 $\lambda$가 $\mu$에 의해 지배된다면 ($\lambda \triangleleft \mu$), 고정된 $d$에 대해 $|\text{Imm}_\lambda M|^2$의 평균이 $|\text{Imm}_\mu M|^2$보다 엄격히 크다는 것을 증명한다.

• 2차 모멘트를 위한 알고리즘 공식: 임의의 $\lambda$에 대한 4차 모멘트의 일반적인 폐쇄형 표현식은 제공되지 않지만, 저자들은 $H_n$과 $V_n$의 대칭성을 활용하여 평가에 필요한 항의 수를 줄이는 알고리즘적 공식(Proposition 6.3)을 유도한다.

  • 명시적 평가: 이 알고리즘을 사용하여, 저자들은 $n \le 5$인 모든 분할 $\lambda \vdash n$에 대해 2차 모멘트에 대한 명시적인 유리 다항식 표현을 제공한다.
  • 특수 사례: 디터미넌트($\lambda=(1^n)$)의 경우, $\int |\text{Det } M|^4 = 1/\text{dim}((2n), U(d))$라는 폐쇄형이 유도된다. 퍼머넌트($\lambda=(n)$)의 경우, 유도된 구조를 바탕으로 한 추측이 제시된다.

• 최고 차수 항 분석 (Leading Term Analysis): 저자들은 $1/d$의 거듭제곱에 대한 4차 모멘트 전개의 최고 계수 $J_\lambda$에 대한 공식을 유도한다. 이 계수는 켤레 분할(conjugate partition)에 대해 대칭임($J_\lambda = J_{\lambda'}$)이 밝혀졌다. $J_\lambda$의 명시적 값들은 $n \le 9$까지 계산되었다.

• 수치적 검증: 이론적 예측은 Haar-무작위 유니터리 행렬에 대한 수치 시뮬레이션과 대조되어 검증되었으며, 유도된 유리 다항식과 $10^4$에서 $10^5$개의 부분 행렬로부터 얻은 평균 데이터 사이의 일치를 보여주었다.

의의 및 주장
본 논문은 혼합 대칭 상태의 이만넌트 모멘트에 대한 최초의 체계적인 처리를 제공한다고 주장한다. 그 의의는 다음과 같다:

1. 이론적 토대: 이 함수들의 집중 특성을 분석하는 데 필요한 1차 및 2차 모멘트에 대한 명시적인 $d$ 의존적 공식을 제공한다.
2. 복잡도 함의: 저자들은 이러한 모멘트를 이해하는 것이 이만넌트 샘플링의 평균 사례 어려움(average-case hardness) 결과를 증명하기 위한 전제 조건임을 언급하며, 이는 BosonSampling 및 양자 계산 우위라는 더 넓은 맥락과 관련이 있다.
3. 계산적 한계: 본 연구는 고차 모멘트에 따른 계산 요구량의 급격한 증가를 강조하며, 이로 인해 명시적인 다항식 결과가 $n \le 5$로 제한됨을 보여주는 동시에, 최고 차수 항 분석은 $n \le 9$까지 확장됨을 보여준다.

저자들은 결과에 대한 전체 증명이 향후 출판물로 미루어졌음을 명시하며, 본 작업을 ISQS29 강연에서 도출된 결과 및 알고리즘의 요약으로 제시한다.