A remark on the Brown-Susskind conjecture

기술 요약: 브라운-서스킨드 추측(Brown-Susskind Conjecture)에 관한 고찰

문제 정의
본 논문은 특정 큐비트 쌍의 집합에서 선택된 고정된 수의 2-큐비트 게이트들의 곱으로 구성될 수 있는 $n$-큐비트 유니터리($U(2^n)$) 집합의 차원 성장을 조사한다. 이 연구는 국소적 무작위 회로의 양자 복잡도가 시스템 크기에 대한 지수 값에 도달할 때까지 게이트 수에 따라 선형적으로 증가한다는 브라운-서스킨드 추측의 맥락 내에 위치한다. 해당 추측은 [3]과 [4](Zhi Li의 추가 증명 포함)에서 이미 증명되었으나, 그 작업들은 고정되고 반복되는 아키텍처(예: 계단형 또는 바퀴 살 모양 토폴로지)에 의존한다. 본 논문은 2-큐비트 쌍의 시퀀스가 미리 정해진 재귀적 패턴을 따르는 대신, 고정된 알파벳 $S$ 내에서 자유롭게 진화하는 시나리오를 다룬다.

방법론 및 수학적 프레임워크
저자들은 도달 가능한 유니터리 집합의 구조를 분석하기 위해 실대수 기하학(real-algebraic geometry)과 리 이론(Lie theory)의 도구들을 사용한다.

1. 그래프 이론적 생성: 저자들은 노드가 큐비트를 나타내고 에지가 가용 큐비트 쌍($S$)을 나타내는 그래프 $\Gamma$를 정의한다. 저자들은 $\Gamma$가 연결되어 있을 때만 2-큐비트 게이트들의 부분군($G_\alpha$)이 전체 유니터리 군 $U(2^n)$을 생성한다는 것을 확립한다. 이 증명은 리 대수 $\mathfrak{u}(2^n)$을 활용하며, $\Gamma$가 연결되어 있다면 2-큐비트 게이트들에 의해 생성된 리 대수가 모든 파울리 문자열(Pauli strings)을 포함하여 전체 대수를 생성함을 보여준다.

2. 대수적 다양체 및 반대수 집합: $k$개의 게이트 시퀀스에 의해 도달 가능한 유니터리 집합 $U_k$는 구성 사상 $F_k: G_{\alpha_1} \times \dots \times G_{\alpha_k} \to U(2^n)$의 이미지로 정의된다. 저자들은 $U(2^n)$과 게이트 부분군들이 실대수 다양체(real-algebraic varieties)인 반면, $U_k$는 일반적으로 대수적 부분 다양체가 아닌 반대수 집합(semialgebraic set, 다항식 방정식과 부등식으로 정의되는 유한한 집합들의 합집합)임을 지적한다.

3. Tarski–Seidenberg를 통한 차원 분석: 분석은 실대수 다양체 사이의 다항 사상의 이미지가 반대수 집합이라는 것을 보장하는 타르스키-세이덴베르크(Tarski–Seidenberg) 정리에 의존한다. 저자들은 $U_k$의 성장을 분석하기 위해 자리스키 폐쇄(Zariski closure)와 대수 집합의 차원 개념을 활용한다.

주요 기여 및 결과
중심 결과는 회로 구성의 각 단계에서 도달 가능한 집합의 차원을 다루는 정리 1.1이다:

• 차원 증가 선택지의 존재: 이 정리는 결과 집합 $U_k$가 아직 최대 차원에 도달하지 않은 경우(즉, $\dim(U_k) < \dim(U(2^n))$), 알파벳 $S$로부터 후속 큐비트 쌍 $\alpha_{k+1}$을 선택하는 방법이 존재한다는 것을 명시한다.
• 증명 메커니즘: 증명은 귀류법으로 진행된다. 주어진 $U_k$에 대해 차원을 증가시키는 $\alpha_{k+1}$의 선택지가 존재하지 않는다고 가정하면, 포함 관계 $U_k \subseteq U_{k+1}$은 두 실대수 다양체가 동일한 차원을 가지므로 등가($U_k = U_{k+1}$)를 의미하게 된다. 이 등가는 $U_k$가 알파벳 내의 임의의 $G_{k+1}$에 의한 우측 작용(right action)에 대해 불변임을 의미한다. $S$의 부분군들이 $U(2^n)$을 생성하므로, 이는 $U_k$가 전체 군 $U(2^n)$과 같아야 함을 강제하며, 이는 $U_k$가 최대치가 아니라는 초기 가정에 모순된다.
• 기약성(Irreducibility): 핵심 보조정리는 실대수 다양체 $U_k$가 기약(irreducible)임을 확립한다. 즉, $U_k$는 두 개의 진 자리스키 닫힌 부분집합의 합집합으로 분해될 수 없다. 이 성질은 동일한 차원이 집합의 동일성을 의미한다고 결론짓는 데 필수적이다.
• 비구성적 성격: 저자들은 차원을 증가시키는 큐비트 쌍 $\alpha_{k+1}$의 존재를 증명하지만, 차원을 높이기 위한 구체적인 다음 큐비트 쌍 $\alpha_{k+1}$을 어떻게 결정하거나 구성할지는 알지 못한다고 명시적으로 언급한다. 저자들은 좋은 선택이 최근에 사용된 에지로부터 "멀리 떨어진" 쌍을 포함하는 것일 수 있다고 추측하지만, 이는 증명되지 않았다. 이는 고정된 아키텍처를 사용하는 [3] 및 [4]의 작업과 대조된다.

특수 사례: 일매개변수 부분군
본 논문은 해밀토니안 $H_1$과 $H_2$에 의해 생성되는 두 일매개변수 부분군(one-parameter subgroups)과 관련된 특정 사례도 조사한다.

• 추측 1 (Seth Lloyd의 것으로 간주됨): 만약 $iH_1$과 $iH_2$가 스큐-헤르미션(skew-Hermitian) 연산자의 리 대수를 생성하고 부분군들이 주기적이라면, $k \le 2^{2n}$에 대하여 $k$-번 곱의 집합의 차원은 정확히 $k$이다.
• 지지 근거: 저자들은 주기성 가정 하에 이 부분군들이 닫힌 실대수 부분 다양체라고 주장한다. 결과적으로 (두 부분군 사이를 전환해야 하므로) 차원은 각 단계에서 최소 1만큼 증가해야 하며, 1보다 많이 증가할 수 없으므로 성장은 정확히 선형적이다.

의의 및 한계
본 논문은 자유롭게 진화하는 아키텍처에서, 회로 구성이 아직 전체 유니터리 군에 도달하지 않은 경우라면 어떤 게이트 시퀀스에 대해서도 차원을 증가시킬 수 있는 다음 게이트의 존재가 있다는 이론적 보증을 제공한다. 이 결과는 도달 가능한 집합의 기약성과 기저 큐비트 상호작용 그래프의 연결성에 의존한다.

그러나 저자들은 다음과 같은 구성적 능력의 한계에 대해 명확히 밝히고 있다:

• 존재성 대 구성성: 본 논문은 차원을 증가시키는 큐비트 쌍 $\alpha_{k+1}$의 존재를 증명하지만, 이 쌍을 선택하기 위한 알고리즘이나 방법을 제공하지 않는다는 점을 명시적으로 밝힌다. 저자들은 최근 사용된 에지로부터 "멀리 떨어진" 쌍을 선택하는 것이 하나의 휴리스틱한 선택이 될 수 있다고 언급하지만, 이는 추측에 불과하다.
• 이전 연구와의 대조: 저자들은 이러한 다음 게이트의 구체적인 선택에 관한 불확실성이, 다음 게이트가 미리 정해져 있는 재귀적이고 고정된 아키텍처를 사용하는 [3] 및 [4]의 연구에서는 발생하지 않는다는 점을 강조한다.

요약하자면, 본 논문은 도달 가능한 집합의 기약성과 기저 큐비트 상호작용 그래프의 연결성에 기반하여, 자유 진화 아키텍처에서 각 단계마다 차원 성장이 가능하다는 이론적 보증을 제공하지만, 이러한 성장을 달성하기 위한 구성적 전략은 제시하지 않는다.