Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

개요: "완벽하게 편향되지 않은" 친구들의 게임

당신이 $d$ 차원의 고차원 방에서 파티를 열려고 한다고 상상해 보세요. 당신은 특정 패턴으로 서 있는 사람들의 그룹(기저, bases)을 초대하고 싶습니다.

"상호 무편향 기저(Mutually Unbiased Basis, MUB)"의 규칙은 완벽한 균형을 맞추는 게임과 비슷합니다:

그룹 내부: 모든 사람은 서로 완벽하게 직각을 이루며 서 있어야 합니다(직교, orthonormal).
그룹 간: 만약 당신이 A 그룹에서 한 명을, B 그룹에서 한 명을 뽑는다면, 그들 사이의 "각도"는 가능한 모든 쌍에 대해 정확히 동일해야 합니다. 그들은 서로에게 "편향되지" 않았습니다.

수학자들은 이 게임에 대해 어려운 한계를 알고 있습니다: 당신은 결코 $d + 1$ 개보다 많은 그룹을 가질 수 없습니다. 예를 들어, 6차원 방( $d=6$ )에서는 최대 7개의 그룹을 가질 수 있습니다. 6차원 방에서 실제로 그 한계인 7개에 도달할 수 있는지, 아니면 규칙이 그전에 무너지는지는 유명한 미해결 난제입니다.

문제: 컴퓨터가 그 한계를 "볼" 수 있을까?

이 논문은 **합의 제곱(Sum-of-Squares, SoS)**이라고 불리는 특정 유형의 컴퓨터 알고리즘에 대해 구체적인 질문을 던집니다. SoS를 매우 똑똑하지만 약간 근시안적인 탐정이라고 생각해보세요. So로는 사람들의 위치를 설명하는 수학 방정식들을 살펴봄으로써 특정 배치가 불가능하다는 것을 증명하려고 노력합니다.

이 탐정에게는 "차수(degree)"라는 제한이 있습니다. 4차(degree-4) 탐정은 한 번에 최대 4개의 변수 사이의 관계(예를 들어, 네 사람의 위치가 어떻게 상호작용하는지)만을 볼 수 있습니다.

특정 질문("Open Problem 23"에서 발췌)은 다음과 같았습니다: 4차 탐정이 6차원 방에 7개의 그룹이 존재할 수 없다는 것을 증명할 수 있는가?

발견: 탐정은 잘못된 지도를 사용하고 있다

저자 셰한 사르카르(Shreyhaan Sarkar)는 답이 당신이 탐정에게 사람들을 어떻게 설명하느냐에 달려 있다는 것을 발견했습니다.

1. "벡터" 지도 (실패)

첫 번째 방법에서, 탐정에게는 모든 사람의 머리, 손, 발의 좌표(벡터의 실수부와 허수부)가 주어집니다.

속임수: 저자는 무작위적이고 독립적인 사람들의 그룹을 사용하여 "가짜 현실"을 구축했습니다. 이 가짜 세상에서 그룹들은 엄밀한 의미에서는 완벽하게 무편향된 것이 아니지만, 만약 당신이 "4차 렌즈"를 통해서만 본다면 그들은 완벽하게 무편향된 것처럼 보입니다.
비유: 군중의 흐릿한 사진을 보고 있다고 상상해 보세요. 멀리서 보면(4차 수준에서는), 군중은 완벽하게 균형 잡혀 있고 무작위로 보입니다. 탐정은 수학을 체크하고, 모든 것이 0으로 더해지는 것을 확인한 뒤, "헤이, 이 배치는 가능하다!"라고 말합니다.
결과: 탐정이 이 "가짜 현실"(의사 기대값, pseudoexpectation이라 불림)에 속을 수 있기 때문에, 탐정은 7개의 그룹이 존재할 수 없다는 것을 증명할 수 없습니다. 탐정은 $d+1$ 의 한계를 보지 못합니다. 6차원 방에 100개의 그룹이 가능할지도 모른다고 생각합니다. 비록 우리가 그것이 틀렸다는 것을 알고 있음에도 말이죠.

2. "투영체(Projector)" 지도 (성공)

저자는 그다음 사람들을 설명하는 다른 방법을 시도했습니다. 탐정에게 사람들의 팔다리 좌표를 주는 대신, 각 사람이 드리우는 그림자 또는 **투영(projection)**의 설명( $P = vv^*$ 로 수학적 표현)을 주었습니다.

차이점: 이 "투영체" 언어에서는 "무편향성"을 위한 규칙이 훨씬 단순해집 (4차 식이 아닌 2차 식).
결과: 탐정이 이 지도를 사용할 때, "가짜 현실" 속임수는 더 이상 통하지 않습니다. 4차 탐정은 이제 명확하게 수학적 모순을 볼 수 있습니다. 탐정은 $d+1$ 개 이상의 그룹을 가질 수 없다는 것을 성공적으로 증명해 냅니다.

핵심 요약

이 논문은 문제를 해결하지 못한 이유가 수학이 너무 어려워서가 아니라, 설명이 너무 약했기 때문이라고 결론짓습니다.

벡터 좌표: 퍼즐 조각을 하나씩 하나씩 보면서 퍼즐을 풀려고 하는 것과 같습니다. 4차 탐정은 혼란에 빠져 퍼즐이 풀릴 수 있다고 생각하지만, 실제로는 그렇지 않습니다.
투영체 좌표: 퍼즐 상자에 그려진 그림을 보는 것과 같습니다. 4차 탐정은 즉시 패턴을 알아차리고 퍼즐이 불가능하다는 것을 깨닫습니다.

이것이 특정 질문에 왜 중요한가

이 논문은 "Randomstrasse101 Open Problem 23"을 구체적으로 다루며, 이는 두 가지 "벡터" 방식에 대해 물었습니다.

답변: 아니오. 해당 특정 벡터 설명을 사용하는 차수-4 합의 제곱 증명은 6차원에서 7개의 상호 무편향 기저가 존재할 수 없음을 증명할 수 없습니다.
주의 사항: 이것이 어떠한 증명도 존재하지 않는다는 뜻은 아닙니다. 단지 이 특정한 직접적인 방식으로 문제를 쓰는 것이 4차 알고리즘에게는 너무 약하다는 뜻입니다. 만약 문제를 "투영체" 방식으로 바꾼다면, 알고리즘은 한계를 찾아낼 만큼 충분히 강력해집니다.

요약하자면: 이 논문은 만약 당신이 생생한 좌표를 사용하여 문제를 설명한다면, 제한된 "시야"(4차)를 가진 컴퓨터는 불가능한 것을 가능하다고 믿도록 속을 것이라는 점을 보여줍니다. 하지만 만약 당신이 "그림자"(투영체)를 사용하여 문제를 설명한다면, 동일한 컴퓨터가 진실을 볼 수 있게 됩니다.

기술 요약: 차수 4의 벡터-좌표(Vector-Coordinate) SoS는 MUB 상한을 감지할 수 없다

문제 정의
본 논문은 7개의 상호 무편향 기저(MUB)가 $\mathbb{C}^6$ 에 존재하지 않음을 증명하기 위해 차수 4의 합-제곱(Sum-of-Squares, SoS) 증명이 존재하는지를 묻는 Randomstrasse101 오픈 문제 23을 다룬다. 이 문제는 두 가지 특정 벡터-좌표 인코딩을 사용하여 프레임화된다:

사차 등식 정식화(Quartic Equality Formulation): 제약 조건이 벡터 성분의 실수부와 허수부에 대한 사차 관계식, 즉 $|\langle v, w \rangle|^2 = 1/d$ 로 인코딩된다.
$2 \times 2$ 헤르미트(Hermitian) 반정부호(Semidefinite) 정식화: 기저 간 조건이 이차 내적 $\langle v, w \rangle$ 를 포함하는 $2 \times 2$ 헤르미트 행렬에 대한 반정부호 제약 조건으로 인코딩된다.

더 넓은 맥락에서, 이는 $m \le d + 1$ 이라는 알려진 상한 $m$ 에 관한 문제이다. 소수 거듭제곱 차원에서는 등호가 성립하지만, $d=6$ 인 경우는 여전히 미해결 상태이며, $m=7$ 은 불가능하다는 추측이 존재한다.

방법론
저자들은 차수 4 의사기댓값(pseudoexpectations)을 구축함으로써 차수 4 SoS 완화(relaxation)의 능력을 분석한다. 차수 4 의사기댓값은 최대 차수가 4인 다항식에 대한 선형 범함수 $\tilde{\mathbb{E}}$ 로서, 양의 성질( $\tilde{\mathbb{E}}[f^2] \ge 0$ )과 제약 조건에 대한 일관성을 만족한다. 만약 어떤 시스템에 대해 이러한 의사기댓값이 존재한다면, 해당 시스템에 대한 차수 4 SoS 반박(불가능성에 대한 증명)은 존재할 수 없다.

핵리의 방법론은 다음과 같다:

하아-무작위(Haar-Random) 구성: 저자들은 독립적인 하아-무작위 유니터리 행렬에 대한 기댓값을 기반으로 하는 의사기댓값을 정의한다. 구체적으로, $m$ 개의 기저를 가진 경우, 벡터들은 독립적인 무작위 유니터리 행렬의 열(column)로 취급된다.
제약 조건 검증:
- 동일 기저 제약: 무작위 구성에서 직교 정규성은 점별로(pointwise) 정확하게 성립한다.
- 교차 기저 제약: 독립적인 하아-무작위 단위 벡터 $x, y$ 에 대하여, $\mathbb{E}[|\langle x, y \rangle|^2] = 1/d$ 이다.
아핀 승수 분석(Affine Multiplier Analysis): 반정부호 정식화에 대해, 저자들은 아핀-선형 함수에 작용하는 내적 $z = \langle x, y \rangle$ 의 곱셈 연산자의 연산자 노름(operator norm)에 대한 특정 경계값을 증명한다. 그들은 $|\mathbb{E}[p z q]| \le \frac{1}{d} \sqrt{\mathbb{E}[|p|^2]\mathbb{E}[|q|^2]}$ 임을 보여준다.
정식화 비교: 논문은 벡터-좌 좌표 정식화와 이차 내적 $\langle v, w \rangle$ 를 포함하는 $2 \times 2$ 헤르미트 반정부호 제약 조건을 사용하는 투영 연산자-좌표(projector-coordinate) 정식화를 대조한다. 여기서 변수는 랭크-1 투영 연산자 $P = vv^*$ 이다.

주요 기여 및 결과

벡터-좌표 정식화에 대한 하한:
주요 결과(정리 5.1 및 7.1)는 임의의 차원 $d$ 와 임의의 제안된 기저 수 $m$ 에 대하여, 표준 벡터-좌표 MUB 시스템이 독립적인 하아-무작위 기저로부터 유도된 차수 4 의사기댓값을 가짐을 확립한다.
- 사차 등식: 의사기댓값은 사차 항 $\mathbb{E}[|\langle x, y \rangle|^2 - 1/d] = 0$ 이므로 사차 제약 조건을 만족한다. 제약 조건이 차수 4이므로, 차수 4 반박은 이들에 상수를 곱할 수 있으며, 의사기댓값은 이를 소거한다.
- 반정부호 정식화: 아핀 승수 경계(정리 6.1)를 사용하여, 저자들은 의사기댓값이 $2 \times 2$ 헤르미트 행렬에 대한 차수 4 로컬라이징(localizing) 제약 조건을 만족함을 보여준다.
- 결과: 이러한 벡터-좌 좌표 정식화에서의 차수 4 SoS는 $m > d + 1$ 인 경우(MUB가 존재할 수 없거나 존재하지 않는다고 추측되는 경우)에도 $m$ 개의 MUB 존재를 반박할 수 없다. 구체적으로, $d=6, m=7$ 인 경우, 이러한 인코딩에서는 존재하지 않음에 대한 차수 4 SoS 증명이 존재하지 않는다.
정식화 분리 (투영 연산자 vs. 벡터):
논문은 이러한 실패가 벡터-좌 좌표 인코딩에 특이적임을 입증한다. 변수가 중심화된 투영 연산자 $Q = P - I/d$ 인 투영 연산자-좌표 정식화(정리 8.1)에서는:
- 교차 무편향 조건이 이차식( $\text{Tr}(P_i^{(k)} P_j^{(\ell)}) = 1/d$ )이 된다.
- 저자들은 $m > d + 1$ 일 때마다 투영 시스템에 대한 차수 4 SoS 반박을 구성한다.
- 이 반박은 투영 연산자 제곱 합의 트레이스(trace)를 포함하는 그람 행렬(Gram matrix) 항등성에 의존하며, 이는 $m > d + 1$ 일 때 제약 조건에 의해 음수의 상수를 산출한다.
- 결과: 차수 4 SoS는 투영 좌표 정식화에서 기본적인 상한 $m \le d + 1$ 을 성공적으로 회복한다.

의의 및 주장
본 논문은 MUB 문제에 대한 저차 SoS 계층 구조의 능력에 관한 **정식화 의존적 분리(formulation-dependent separation)**를 주장한다:

오픈 문제 23에 대한 부정적 답변: 문제 설명에 기술된 두 가지 특정 벡터-좌 좌표 인코딩(사차 방정식 및 $2 \times 2$ LMI)에 대하여, 답은 부정적이다. 차수 4 SoS는 기본적인 개수 제한( $m \le d + 1$ )을 감지하기에는 본질적으로 너무 약하다.
정식화 민감도: 저차 SoS의 해결 능력 실패는 방법론 자체의 보편적 한계가 아니라, 직접적인 벡터-좌 좌표 완화의 한계이다. 동일한 차수의 완화가 투영 좌표에 적용될 때는 훨씬 강력하여, 알려진 상한을 성공적으로 회복한다.
$d=6$ 에 대한 시사점: 투영 정식화가 $d=6$ 에 대해 $m \le 7$ 을 회복하지만, 논문은 $d=6, m=7$ 케이스가 이 상한의 "타이트한(tight)" 경계임을 언급한다. 따라서, 이 분리 결과가 더 강력한 투영 변수 차수 4 증명이 $\mathbb{C}^6$ 에서 정확히 7개의 MUB 존재를 배제할 수 있는지 여부를 결정적으로 답해주지는 않으며, 단지 8개 이상을 배제할 수 있음을 보여줄 뿐이다.

이 연구는 벡터-좌 좌표 SoS에 대한 특정 차수 4 장애물을 고립시킴으로써, 차수 6 MUB 문제에 대한 성공적인 저차 SoS 접근법은 직접적인 벡터 좌표보다는 리프팅된 정식화(예: 투영 연산자)를 활용해야 함을 시사한다.