Local equivalence of stabilizer states: a graphical characterisation

기술 요약: 안정화 상태의 국소적 동등성: 그래픽적 특징 규명

문제 정의

안정화 상태(Stabilizer states), 특히 그래프 상태(graph states)는 측정 기반 양자 컴퓨팅, 오류 수정, 비밀 공유 등에 활용되는 양자 정보 처리의 핵심 자원이다. 이 분야의 중심 과제는 두 상태가 동일한 얽힘을 갖는지 결정하는 것이다. 양자 정보 이론에 따르면, 두 상태가 동일한 얽힘을 공유한다는 것은 두 상태가 LU-동등(Local Unitary equivalent, 국소 유니터리 동등)함을 의미한다. 즉, 국소 유니터리 연산을 통해 서로 변환될 수 있음을 뜻한다.

LC-동등(Local Clifford equivalence, 국소 클리포드 동등)은 국소 보충(local complementation, 정점의 이웃을 보충하는 그래프 변환)을 통한 그래픽적 특징 규명이 잘 확립되어 있다. 한편, LU-동등과 LC-동등이 그래프 상태에 대해 일치할 것이라는 가설이 있었으나, 이는 반례(예: LU-동등하지만 LC-동등하지 않은 그래프 상태 쌍)에 의해 거짓으로 판명되었다. 결과적으로, LU-동등에 대한 완전한 그래픽적 특징 규명을 찾는 문제는 미해결 과제로 남았다. 컷 랭크 함수(cut-rank function)와 같은 기존 도구들은 LU-동등 클래스를 완전히 구별하기에 불충분했으며, LC와 LU 동등 사이의 간극에는 구조적인 그래픽적 설명이 결여되어 있었다.

방법론

저자들은 표준적인 국소 보충을 일반화한 그래픽 변환 계층을 도입함으로써 이 문제를 해결한다. 이 방법론은 다음 세 가지 핵심 축에 기반한다:

1. 일반화된 국소 보충 ($r$-local complementation):
   본 논문은 양의 정수 $r$로 매개변수화된 새로운 변환인 $r$-국소 보충을 정의한다. 이 연산은 $r$-incidence라고 불리는 특정 카운팅 조건을 만족하는 독립 멀티셋(independent multiset) $S$ 상에서 수행된다.

   • $r=1$인 경우, 이는 표준적인 국소 보충과 일치한다.
   • $r > 1$인 경우, 이 변환은 $S$ 내의 공통 이웃 수를 $2^r$로 나눈 나머지(modulo $2^r$)를 기준으로 에지를 토글(toggle)한다.
   • 저자들은 이러한 변환이 로컬 클리포드 그룹을 확장한 $LC_r = \langle H, Z(\pi/2^r) \rangle$에 속하는 국소 유니터리를 사용하여 그래프 상태에 구현될 수 있음을 증명한다.

2. 최소 국소 집합 및 정점 유형:
   국소 유니터리의 작용을 특징짓기 위해, 저자들은 최소 국소 집합(최소 국소 집합에 의해 불변인 정점들의 부분집합)을 활용한다. 이들은 각 정점에 유형(type) $X, Y, Z, \perp$를 할당하여 정점을 분류하는 체계를 도입한다.

   • 이러한 유형 분류를 통해 저자들은 그래프의 표준 형태(Standard Form)를 정의할 수 있다. 모든 그래프는 표준 국소 보충만을 사용하여 표준 형태(유형 $X$인 정점들이 독립 집합을 형성하고, $X$의 이웃이 유형 $Z$이며, 특정 순서 제약 조건이 충족되는 형태)로 변환될 수 있다.

3. 표준 형태 분석:
   LU-동등한 그래프들을 각각의 표준 형태로 변환함으로써, 저자들은 이들 사이의 국소 유니터리 사상이 특정 제약을 받는다는 것을 보여준다. 구체적으로, 표준 형태에 있는 두 그래프가 LU-동등하다면, 그 사상은 $X$ 및 $Z$ 회전을 포함하는 특정 구조로 축소된다. 그래프 구조로부터 도출된 회전 각도에 대한 제약 조건은 $r$-국소 보충에 필요한 조건과 정확히 일치한다.

주요 기여 및 결과

1. $LC_r$-동등성의 그래픽적 특징 규명

본 논문은 두 그래프 상태가 $LC_r$-동등($LC_r$ 내의 국소 유니터리에 의해 변환 가능함)할 필요충분조건이 그에 대응하는 그래프들이 $r$-국소 동등한 것임을 확립한다.

• 정리 32: $LC_r$-동등성은 표준 국소 보충의 시퀀스와 최대 하나의 $r$-국소 보충에 의해 그래픽적으로 포착된다.
• 이는 $LC_1$-동등(LC-동등)이 오직 표준 국소 보충의 시퀀스만으로 포착된다는 알려진 결과를 일반화한 것이다.

2. LU-동등성의 완전한 특징 규명

저자들은 LU-동등성이 이러한 일반화된 변환들의 합집합에 의해 완전히 포착됨을 증명한다.

• 정리 33: 두 그래프 상태가 LU-동등하다면, 그들은 $(\lfloor n/2 \rfloor - 1)$-국소 동등하다 (여기서 $n$은 큐비트의 수).
• 이는 모든 LU-동등성이 일반화된 국소 보충의 시퀀스로 그래픽적으로 나타낼 수 있음을 의미하며, LU-동등 클래스에 대한 완전한 그래픽적 설명을 제공한다.

3. 엄격한 무한 계층 구조의 동등성

주요 결과 중 하나는 그래프 상태 동등성의 엄격한 무한 계층 구조를 증명하는 것이다.

• 논문은 Kneser 그래프의 변형인 이분 그래프 계열($C_{t,k}$ 및 $C'_{t,k}$로 표기)을 구축하여, 임의의 정수 $r$에 대해 $LC_{r+1}$-동등하지만 $LC_r$-동등하지 않은 그래프 상태 쌍이 존재함을 보여준다.
• 이는 LC-동등성과 LU-동등 사이의 간극이 단일 단계가 아니라, 무한한 중간 단계의 계층 구조임을 확인시켜 준다.
• 이 구성은 LU-LC 추측에 대한 알려진 반례(예: 27-정점 반례)를 $LC_1$-동등하지 않은 $LC_2$-동등의 사례로 복구한다.

4. 특정 가계(Families)에 대한 LU $\Leftrightarrow$ LC 추측의 해결

새로운 그래픽적 특징 규명을 사용하여, 저자들은 주어진 그래프에 대해 LU-동등성과 LC-동등성이 일치하는지에 대한 필요충분조건을 제시한다.

• 명제 34: 그래프 $G$에 대해 LU $\Leftrightarrow$ LC가 성립할 필요충분조건은, 표준 형태에서 유형 $X$의 정점들에 대한 임의의 $r$-국소 보충이 표준 국소 보충에 의해 구현될 수 있는 것이다.
• 이 기준은 리피터 그래프 상태(완전 그래프 기반 및 바이클리크 그래프 기반 모두 포함)가 LU $\Leftrightarrow$ LC를 만족함을 증명하는 데 적용되어, 기존 문헌의 미해결 문제를 해결한다.

의의

본 논문의 주요 의의는 안정화 상태에 대한 LU-동등성의 첫 번째 완전한 그래픽적 특징 규명을 제공했다는 점에 있다. $r$-국소 보충 및 관련 표준 형태를 도입함으로써, 본 연구는 다음과 같은 성과를 거두었다:

• 그래프의 조합론적 특성과 국소 유니터리의 대수적 특성 사이의 간극을 메웠다.
• 이전에는 특징 규명되지 않았던, 구조화되고 무한한 얽힘 동등 계층을 밝혔다.
• 양자 상태의 동등성을 결정하기 위한 새로운 도구 세트를 제공하여, LU-LC 추측에 대한 최소 반례 탐색을 돕고 양자 프로토콜에서의 얽힘 분석을 단순화할 수 있게 하였다.

저자들은 LC-동등성을 결정하는 것은 다항 시간 내에 가능한 것으로 알려져 있으나, 일반적인 LU-동등성 문제의 복잡도는 이 새로운 그래픽 프레임워크를 사용하여 탐구해야 할 미해결 과제로 남아 있다고 언급하였다.