MoMPy: automated construction of moment matrices for semidefinite programming relaxations

기술 요약: "MoMPy: semidefinite programming relaxations를 위한 moment matrices의 자동 구축"

문제 정의
Navascués–Pironio–Acín (NPA) 계층 구조와 같은 준정치적 계획법(Semidefinite Programming, SDP) 계층은 양자 상관관계를 경계 짓고 양자 특성을 인증하는 표준 도구이다. 이러한 방법들은 연산자 곱의 기댓값인 모멘트(moment)를 행렬의 성분으로 구성하는 "모멘트 행렬" 구축에 의존한다. 이 과정에서 발생하는 핵심적인 병목 현상은 어떤 행렬 성분이 동일한 SDP 변수에 대응하는지를 식별하는 "장부 정리(bookkeeping)" 작업이다. 투영 사영의 멱등성($P^2=P$), 측정 결과의 직교성($P_i P_j = 0$), 그리고 서로 다른 당사자 간의 가환성(commutation)과 같은 물리적 제약 조건은 서로 다른 연산자 단어(monomials)들이 동일한 모멘트를 갖게 함을 의미한다.

수동으로 이러한 식별 과정을 도출하는 것은 오류가 발생하기 쉽고, 수만 개의 성분을 포함하는 대규모 계층에서는 불가능하다. 잘못된 식별은 제약 조건을 누락시켜 경계값을 약화시키거나, 비물리적인 제약 조건을 부과하여 결과를 완전히 무효화할 수 있다. 기존의 소프트웨어 도구들은 특정 시나리오(예: Bell 비국소성 대 준비-측정 모델)를 위해 별도의 코드 경로를 사용하거나 특화된 대수적 구조를 사용하므로, 다양한 유형의 완화(tracial, state-based, 또는 block-valued)를 하나의 프레임워크 내에서 통합하기 어렵다.

방법론
본 논문은 선언적 접근 방식을 통해 모멘트 행렬의 구축을 자동화하는 오픈 소스 Python 패키지인 MoMPy를 제시한다. 핵심 방법론은 다음과 같다:

1. 선언적 추상화 (Declarative Abstraction): 사용자는 연산자 레이블 세트와 일련의 구조적 관계(멱등성, 직교성, 가환성, 그리고 실수성/역전성)를 정의한다. 패키지는 이러한 관계를 스스로 추론하지 않으며, 사용자가 명시적으로 선언해야 한다.
2. 단어 재작성 알고리즘 (Word-Rewriting Algorithm): 식별 문제를 정수 튜플에 대한 단어 재작성 문제로 재구성한다. MoMPy는 **메모이제이션된 너비 우선 탐색(memoised breadth-first search)**과 서로소 집합 포레스트(disjoint-set forest/union-find) 자료 구조를 결합하여 사용한다.
   • 이 알고리즘은 선언된 관계 하에서 단어들의 동치류(equivalence classes)를 계산한다.
   • 각 고유한 모노미얼이 어떻게 많은 행렬 성분을 레이블하든 관계없이, 빌드당 정확히 한 번만 처리되도록 보장한다.
   • "스티키 제로 클래스(sticky zero class)"는 단어가 반드시 0이 되어야 하는 경우(예: 직교성으로 인해)를 처리하며, 동치류를 통해 0을 역방서로 전파한다.
3. 통합 모멘트 맵 ($\Theta$): 구성 방식은 물리적 시나리오의 특정 모멘트 맵에 독립적이다. 단일 MomentProblem 객체에 설정된 플래그를 통해 세 가지 주요 모드를 지원한다:
   • 상태 모멘트 (State moments, NPA): $\Theta(X) = \langle \psi | X | \psi \rangle$ (비순환적).
   • 트레이스 모멘트 (Tracial moments): $\Theta(X) = \text{Tr}(X)$ (순환적).
   • 블록 가치 모멘트 (Block-valued moments): $\Theta(X) = X$ (연산자 값 성분, $d \times d$ 블록).
4. 통합 (Integration): 출력물은 SDP 변수 인덱스의 행렬과 룩업 테이블(lookup table)로 구성된다. 이는 CVXPY와 같은 모델링 레이어에 직접 입력되도록 설계되었으며, 목적 함수와 솔버 선택은 사용자에게 맡긴다.

주요 기여
본 논문은 세 가지 주요 기여를 한다:

1. 일반적 추상화: NPA, tracial, block-valued 계층 구조에 걸친 공통 단계인 "연산자 관계에 의해 생성된 단어들의 몫 공간(quotienting) 생성"을 분리해 냈다. 이 추상화는 네 가지 단어 수준 관계와 선택적 순환성/블록 크기 플래그로 정의되며, "당사자(parties)"나 "설정(settings)"과 같은 시나리오별 개념 없이도 핵심 구성을 수행한다.
2. 효율적인 알고 알고리즘: 구현된 알고리즘은 행렬의 크기가 아닌, 도달 가능한 고유 단어의 수에 따라 비용이 결정된다. 이는 독립적인 브루트 포스(brute-force) 구현 및 수치적 실현 가능성 검사를 통해 검증되었다.
3. 범용성의 입증: 저자는 단일 MomentProblem 클래스와 서로 다른 선언된 관계 및 플래그를 조합함으로써, 일반적으로 별개의 처리가 필요했던 구성들을 재현할 수 있음을 보여준다. 여기에는 다음이 포함된다:
   • Bell 유형 경계 (NPA).
   • 삼자 Mermin 부등식.
   • 스티어링(Steering) 및 측정 호환성 (부분 트레이스를 사용하는 블록 행렬 활용).
   • 준비-측정 차원 증인(dimension witness) 및 상태 판별 (트레이스 모멘트 활용).
   • 장치 독립적 무작위성 인증.
   • 연산자 값 모멘트(블록 행렬)를 이용한 결정론적 상관관계의 인증.

결과 및 검증

• 정확성: 패키지는 720개의 무작위 시나리오에 대해 브루트 포스 참조 구현과 비교 검증되었으며, 행렬 분할에 대해 정확히 일치함을 확인했다. 또한 알려진 폐쇄형 최적값(예: CHSH에 대한 Tsirelson의 경계 $2\sqrt{2}$, 로컬 경계 2, Mermin의 대수적 최대값 4)을 재현한다.
• 성능: 8가지 구조적으로 구별되는 시나리오(이분 Bell 테스트부터 네트워크 구성까지)에 대한 벤치마크 결과, 빌드 시간이 행렬 크기가 아닌 고유 단어 수에 따라 스케일링됨을 보여주었다. 예를 들어, 27,000개의 변수를 가진 $3165 \times 3165$ 행렬을 1,100만 개 이상의 고유 단어를 탐색하여 약 98초 만에 구축하였다.
• 블록 가치 일관성: 핵심 결과로서, dim 및 cyclicity 플래그만 다를 뿐 동일한 모노미얼 리스트와 대수를 사용하여 블록 모멘트 행렬(성분이 $d \times d$ 연산자인 행렬)을 성공적으로 구축하였다. 이는 밑바탕이 되는 추상화가 서로 다른 모멘트 맵 선택에 대해 견고하다는 점을 입증한다.

의의 및 주장
저자는 MoMPy가 순수하게 처리량(throughput)을 높이기 위해 설계된 것이 아님을 명시한다. 컴파일된 특화 도구(예: Moment)가 표준 계층을 더 빠르게 구축할 수는 있다. 대신, MoMPy의 의의는 표현의 범용성과 **감사 가능성(audibility)**에 있다.

• 통합 인터페이스: tracial, state, block-valued 모멘트가 동일한 대수와 모노미얼 리스트를 공유하는 하나의 객체를 선택하는 옵션인 최초의 도구이다.
• 투명성: 리라이팅(rewriting) 핵심 코어가 순수 Python으로 작성되어 있고 인자별로 문서화되어 있기 때문에, 사용자는 자신의 완화 모델이 의존하는 식별 과정을 블랙박스로 믿는 대신 직접 감사할 수 있다. 이는 잘못된 식별(예: 적용되지 않는 곳에 순환성을 부과하는 경우)이 경계값을 조용히 저하시킬 수 있는 상황에서 매우 중요하다.
• 상호작용성: 이 도구는 연구자들이 코드를 새로 작성하지 않고도 다양한 구조적 가정을 테스트할 수 있도록, 수백에서 수천 행 규모의 행렬을 반복적으로 설계하고 재구축하는 실제 연구 환경에 적합하도록 설계되었다.

결론적으로, 본 논문은 모멘트 행렬의 "장부 정리"가 시나리오별 문제가 아닌 공통된 문제임을 밝히며, 하나의 선언적 구성이 이전에는 별도의 구현을 요구했던 광범위한 양자 정보 작업들을 포괄할 수 있음을 보여준다.