No Free Compression in Quantum Relaxations for Optimization

기술 요약: 양자 완화(Quantum Relaxations)에서의 무료 압축은 존재하지 않는다

문제 정의
QAOA(Quantum Approximate Optimization Algorithm) 및 양자 어닐링(Quantum Annealing)과 같은 양자 최적화 알고리즘은 종종 문제의 크기와 가용 하드웨어 사이의 불일치 문제에 직면한다. 전통적인 이진 인코딩은 하나의 결정 변수에 하나의 큐비트를 할당하며, 이는 가용 큐비트 수($m \approx n$)로 해결 가능한 문제의 크기를 제한한다. 이를 해결하기 위해, $m$개의 고전적 이진 변수를 $n$개의 큐비트로 압축하는($n \ll m$) "큐비트 효율적(qubit-efficient)" 인코딩 방식이 제안되어 왔다. 이러한 방법들은 대개 변수를 직접적인 비트-대-큐비트 매핑 대신, 지정된 관측량(예: 파울리 스트링 또는 마요라나 연산자)의 기댓값으로 표현하는 방식에 의존한다.

이러한 압축된 인코딩은 레지스터 폭을 크게 줄여주지만, 압축에 따른 자원 트레이드오프—구체적으로 도달 가능한 기댓값의 기하학적 구조, 값의 크기, 그리고 정보 복구 비용—는 여전히 명확히 이해되지 않은 상태로 남아 있다. 본 논문은 "무료(free)" 압축이 존재하는지, 아니면 큐비트 수의 감소가 필연적으로 다른 물리적 또는 정보 이론적 자원으로 비용을 전가하는지를 조사한다.

방법론
저자는 특정 연산자 기하학에서 일반적인 정보 이론적 경계로 나아가는 세 가지 뚜로를 통해 이 문제를 분석한다:

1. 정확한 마요라나 기하학(Exact Majorana Geometry): 본 논문은 $2n$개의 마요라나 연산자에 의한 쌍별 상관관계(pairwise correlators)를 통해 $m = \binom{2n}{2} \approx 2n^2$개의 이진 변수를 인코딩하는 "완전 이차 마요라나 패밀리(complete quadratic-Majorana family)"에 집중한다. 저자는 모든 가능한 타겟 부호 할당(bit string)에 대해 정해진 부호를 보장할 수 있는 상관관계의 최소 크기인 "유니버설 마진(universal margin)" $\Delta$를 정의한다. 저자는 스펙트럴 그래프 이론, 특히 마요라나 연산자의 공분산 행렬을 토너먼트 행렬(tournament matrices)과 연관시키는 방법을 활용하여 정확한 해석적 경계를 도출한다.
2. 가우시안 완전성(Gaussian Completeness): 저자는 비가우시안 양자 상태(얽힘 또는 상호작용이 있는 상태)가 페르미온 가우시안(free-fermion) 상태보다 더 넓은 범위의 이점 상관관계를 생성할 수 있는지 조사한다. 저자는 마요라나 연산자의 공분산체(covariance body, spectrahedron)의 특성을 활용한다.
3. 일반 정보 이론적 경계: 특정 연산자 구조와 독립적인 베이스라인을 설정하기 위해, 저자는 양자 무작위 액세스 코드(QRAC) 이론을 적용한다. 저자는 고정된 이진 관측량 패밀리에 대한 유니버설 마진 $\delta$의 경계를 도출하고, 신뢰할 수 있는 무작위 액세스 디코딩을 위해 필요한 큐비트 폭($n$)과 상태 복사본 수($N$) 사이의 관계를 나약의 경계(Nayak's bound)를 통해 도출한다.

주요 기여 및 결과

• 마요라나 인코딩의 정확한 유니버설 마진:
  본 논문은 $n$개 큐비트에 대한 완전 이차 마요라나 패밀리에 대해 유니버설 마진이 다음과 같음을 증명한다:
  $$\Delta_{\text{Maj}}(n) = \tan\left(\frac{\pi}{4n}\right) \sim \frac{\pi}{4n} = \Theta(1/n)$$
  이 결과는 최악의 경우의 부호 패턴이 스위칭 및 재라벨링 하에서 "전이적 토너먼트(transitive tournament)"와 동일함을 식별함으로써 도출되었다. 일반적인 무작위 부호 패턴은 $\Theta(1/\sqrt{n})$의 마진을 유지하는 반면, 최악의 경우의 스케일링은 엄격하게 $\Theta(1/n)$이다. 이는 일반적인 정보 이론적 기대치보다 파라미터적으로 더 강력한 붕괴를 나타낸다.

• 이점 상관관계의 가우시안 완전성:
  저자는 임의의 밀도 연산자와 페르미온 가우시안 상태가 정확히 동일한 집합의 도달 가능한 이차 마요라나 공분산 행렬(공분산체)을 생성함을 보여준다. 결과적으로, 비가우시안 자원(예: 얽힘 또는 상호작용)은 도달 가능한 이점 상관관계의 집합을 확장할 수 없다. 이는 목적 함수가 이러한 상관관계에 선형적일 경우, 가우시안 상태에 대한 준정부호 계획법(semidefinite programming)만으로 최적의 완화(relaxation)를 찾는 데 충분함을 의미한다. 즉, 비가우시안 정보를 접근하기 위해서는 고차 상관관계가 필요하다.

• 일반 정보 이론적 베이스라인:
  $n$개 큐비트 상의 고정된 $m$개 이진 관측량 패밀리에 대해, 유니버설 마진 $\delta$는 다음을 만족한다:
  $$\delta \leq \sqrt{\frac{2 \ln 2 \cdot n}{m}}$$
  이는 어떤 고정된 관측량 패밀리도 $m$이 $n$에 대해 초선형적으로 성장하는 경우($n = o(m)$) 상수 마진을 유지할 수 없음을 확인시켜 준다. 또한, 성공 확률 $p > 1/2$인 임의의 무작위 액세스 디코딩을 위해, $N$개의 상태 복사본으로부터의 폭-복사본 곱은 $nN = \Omega(m)$을 만족해야 한다.

• 운영적 결과 ("No Free Lunch"):
  마진의 축소는 이진 출력을 복구하기 위한 비선형 디코더(예: $z_i = \tanh(\alpha \langle A_i \rangle)$)에서의 재스케일링 파라미터 $\alpha$를 필요로 한다. 마요라나의 경우, 고정된 디코딩된 크기를 유지하려면 $\alpha = \Omega(n)$이어야 한다. 이는 최악의 경우 단일 좌표의 부호 복구를 위해 $N = \Theta(n^2)$의 측정 샷(measurement shots) 또는 복사본이 필요함을 의미한다. 따라서 큐비트 절감은 더 높은 측정 해상도, 더 강한 비선형 재스케일링, 또는 증가된 샷 예산이라는 비용으로 상쇄된다.

의의 및 주장
본 논문은 특정하고 매우 압축된 양자 인코딩(완전 이차 마요라나 패밀리)에 대한 최초의 정확한 최악의 경우 마진 특성을 제공하며, 연산자 기하학에 특유한 $\Theta(1/n)$ 병목 현상을 밝혀냈다고 주장한다.

저자는 압축이 "실패"하는 것은 아니지만, "무료"도 아니라는 점을 강조한다. 큐비트 레지스터 폭의 감소는 다음의 형태로 다시 나타난다:

1. 제한된 기하학: 도달 가능한 기댓값은 비가우시안 상태에 의해 확장될 수 없는 특정 공분산체 내에 갇혀 있다.
2. 감소된 크기: 최악의 경우 상관관계의 크기는 큐비트 수에 반비례하여 줄어든다.
3. 증가된 복구 비용: 이러한 작은 값들을 디코딩하려면 $n$에 선형적으로 증가하는 재스케일링 파라미터나, 고립된 좌표를 위해 $n^2$에 비례하여 증가하는 측정 샷 예산이 필요하다.

본 연구는 양자 최적화 자원을 평가할 때 레지스터 폭뿐만 아니라 큐비트 수, 도달 가능한 마진, 디코딩 규칙, 그리고 샷 예산을 포함한 총체적인 평가가 필요함을 결론짓는다. 이 결과는 압축 일반에 내재된 비용(정보 이론적 경계)과 마요라나 기하학에 특유한 비용(정확한 마진 정리)을 구분한다.