Quantum circuit partition as a maze: emerging percolation transition via path finding

이 논문은 양자 회로 분할을 미로 자르기 문제로 정형화하는 새로운 프레임워크를 제안하며, 특히 CNOT의 수가 큐비트의 수와 비슷할 때 게이트를 제거하지 않고도 회로를 두 개의 CNOT 클러스터로 최적으로 나눌 수 있는지 여부를 결정하는 것이 퍼콜레이션 상전이임을 입증한다.

핵심

복잡한 양자 컴퓨터 프로그램을 나타내는 거대하고 엉킨 실타래가 있다고 상상해 보세요. 당신의 목표는 이 실타래를 반으로 잘라 두 대의 서로 다른 컴퓨터가 각각의 절반을 동시에 작업하게 함으로써 처리 속도를 높이는 것입니다. 하지만 함정이 있습니다. 이 "실"은 CNOT 게이트라고 불리는 특별한 매듭들로 이루어져 있습니다. 만약 매듭을 통과하며 자르게 되면, 프로그램은 망가지고 멈춰버립니다. 당신은 매듭을 하나도 건드리지 않고 실을 가로지를 수 있는 방법을 찾아야 합니다.

이 논문은 이 문제를 미로 찾기처럼 다룹니다.

미로 비유

저자들은 양자 회로를 마치 비디오 게임 레벨처럼 격자 형태로 만들었습니다:

• 벽: CNOT 게이트는 미로의 벽입니다. 이것들은 지나갈 수 없는 단단한 장벽입니다.
• 경로: 당신은 미로의 왼쪽에서 오른쪽까지 선(즉, "절단선")을 그려야 합니다.
• 목표: 만약 벽에 부딪히지 않고 왼쪽에서 오른쪽까지 선을 그을 수 있다면, 당신은 회로를 두 개의 독립된 부분으로 성공적으로 분리한 것입니다. 만약 벽에 부딪힌다면, 그 회로는 나누는 과정에서 망가질 정도로 너무 복잡하게 얽혀 있는 것입니다.

문제점: "붐비는 중심부"

이런 미로들을 처음 만들었을 때, 저자들은 한 가지 패턴을 발견했습니다. 벽(매듭)들이 마치 도시 중심부의 교통 체증처럼 미로의 정중앙에 몰려 있다는 점이었습니다. 중심부가 너무 붐볐기 때문에, 벽에 부딪히지 않고 직선을 긋는 것은 거의 불가능했습니다.

해결책: 가구 재배치하기 (시뮬레이티드 어닐링)

이를 해결하기 위해 저자들은 **시뮬레이티드 어닐링(Simulated Annealing)**이라는 영리한 기술을 사용했습니다. 이것은 미로의 행(row)들을 재배치할 수 있는 매우 똑똑하고 인내심 있는 로봇이라고 생각하면 됩니다.

1. 섞기 (The Shuffle): 로봇은 "와이어"(양자 비트가 이동하는 선)의 순서를 섞습니다. 이는 마치 카드 한 덱을 섞는 것처럼, 섞었을 때 벽들이 덱의 맨 위나 맨 아래로 이동하는지 확인하는 것과 같습니다.
2. 목표: 로봇은 모든 벽을 중심부에서 밀어내어 미로의 위쪽과 아래쪽 가장자리로 몰아넣으려고 노력합니다.
3. 결과: 로봇이 성공하면, 미로 중앙을 가로지르는 텅 빈 깨끗한 통로인 **"중앙 복도(Central Corridor)"**를 만들어냅니다. 이제 당신은 단 하나의 벽에도 부딪히지 않고 이 빈 공간을 통해 절단선을 쉽게 그을 수 있습니다.

"상전이": 임계점

이 논문에서 가장 흥격적인 발견은 벽(CNOT 게이트)의 개수와 와이어(큐비트)의 개수를 변화시킬 때 일어나는 현상입니다.

그들은 물이 갑자기 얼음으로 변하는 것과 유사한 **임계점(Tipping point)**을 발견했습니다:

• "쉬운" 구역: 벽의 개수가 와이어의 개수와 비슷하거나 적을 경우, 로봇은 미로를 재배치하여 그 명확한 중앙 복도를 거의 항상 만들어낼 수 있습니다. 이 회로는 **분할 가능(partitionable)**합니다.
• "불가능한" 구역: 벽이 너무 많으면(CNOT 게이트가 너무 많으면), 미로가 너무 혼잡해져서 로봇이 아무리 행을 섞더라도 벽들이 모든 경로를 차단해 버립니다. 이 회로는 **분할 불가능(non-partitionable)**합니다.

이 "분할할 수 있음"에서 "분할할 수 없음"으로의 급격한 변화는 **퍼콜레이션 전이(percolation transition)**라고 불립니다. 이는 마치 홍수와 같습니다. 특정 수위에서 물이 갑자기 호수 전체를 연결하듯이, 특정 게이트 밀도에 도달하면 벽들이 갑자기 미로 전체를 연결하여 어떤 경로도 막아버립니다.

이것이 중요한 이유

이 논문은 단순히 "회로를 나누는 것이 어렵다"라고 말하는 데 그치지 않습니다. 대신 실용적인 규칙을 제시합니다: 만약 큐비트 하나당 대략 하나의 CNOT 게이트가 있다면, 회로를 분할할 수 있을 가능성이 높습니다. 만약 큐비트보다 훨씬 많은 게이트가 있다면, 아마도 분할할 수 없을 것입니다.

복잡한 수학 문제를 "미로 찾기" 게임으로 바꿈으로써, 저자들은 회로를 파괴하지 않고도 양자 회로를 분할하여 최적화할 수 있는지 알 수 있는 명확하고 시각적인 방법을 제공했습니다. 그들은 "미로 에이전트"(간단한 컴퓨터 프로그램)를 사용하여 최적의 경로를 찾아냈고, 이 "복도" 전략이 많은 유형의 양자 회로에서 작동함을 확인했습니다.

기술 요약

기술 요약: 미로로서의 양자 회로 분할: 경로 탐색을 통한 새로운 퍼콜레이션 전이(Percolation Transition)

문제 정의
양자 회로 최적화, 특히 노이즈가 있는 중간 규모 양자(NISQ) 장치에서, 두 큐비트 게이트(일반적으로 CNOT)의 수를 줄이는 것은 매우 중요한 목표입니다. 이는 CNOT 게이트가 상당한 노이즈 영향을 미치기 때문입니다. 회로 분할은 여러 장치에 걸쳐 병렬 최적화를 가능하게 하지만, 기존 방식은 주로 중간 회로 측정(mid-circuit measurement)과 큐비트 리셋을 통해 CNOT 게이트를 절단하는 방식에 의존합니다. CNOT 게이트를 절단하지 않고도 회로를 두 개의 하위 회로로 최적으로 분할할 수 있는지 여부를 결정하는 기준을 찾는 데에는 중요한 공백이 존재합니다. 핵심 과제는 게이트 절단 없이 (하위 회로의 독립적인 재합성을 허용하는) 분할 가능한 회로와 그렇지 않은 회로를 구별하는 기준을 식별하는 것입니다.

방법론
저자들은 회로 분할 문제를 "미로" 내에서의 경로 탐색 작업으로 공식화합니다. 방법론은 다음과 같은 몇 가지 주요 단계로 진행됩니다:

1. 회로 표현:

   • 와이어 표현 ($W$): 행은 큐비트 와이어를, 열은 CNOT 게이트를 나타내는 그리드입니다. 특정 셀은 CNOT가 해당 큐비트를 포함하는 경우 표시됩니다.
   • 미로 표현 ($M$): 변환된 그리드로, 행은 큐비트 와이어 사이의 공간(패딩 포함)을 나타내며, 열은 빈 공간과 CNOT 게이트가 번갈아 나타납니다. 이 표현에서 CNOT 게이트는 "벽" 역할을 합니다. 유효한 분할은 미로의 왼쪽 가장자리에서 오른쪽 가장다까지 벽과 교차하지 않는 연속적인 경로에 해당합니다.

2. 큐비트 순서 최적화 (시뮬레이티드 어닐링):

   • 무작위로 생성된 회로는 와이어 표현에서 미로의 중앙 부분에 벽 분포가 집중되어 있어 수평 이동이 어렵습니다.
   • 저자들은 큐비트 와이어의 순서를 치환하기 위해 시뮬레이티드 어닐링(SA)을 사용하여 와이어 표현을 최적화합니다. 이 치환은 미로 표현으로 다시 매핑됩니다.
   • SA 과정 동안, CNOT 상호작용이 그리드의 중앙 영역을 가로지르는 것을 억제하는 비용 함수가 최소화됩니다. 목표는 상호작용을 상단 및 하단 경계 쪽으로 밀어내어, 벽이 없는 "중앙 통로(central corridor)"를 만드는 것입니다.

3. 경로 탐색 휴리스틱:

   • 미로가 최적화되면, 휴리스틱 에이전트가 미로를 탐색합니다. 두 개의 결정론적 에이전트(벽에 부딪혔을 때 위로 이동하는 에이전트와 아래로 이동하는 에이전트)가 첫 번째 열의 각 셀에서 출발합니다.
   • 에이전트는 결과적인 하위 회로가 시간적으로 일관되도록 하기 위해 단조적(시간적으로 뒤로 가거나 수직 방향을 역전하지 않음)으로 움직이도록 제한됩니다.
   • 가중치 비용 함수($L_{tot}$)는 CNOT 불균형, 셀(면적) 불균형, 그리고 이상적인 수평 궤적으로부터의 경로 길이 편차라는 세 가지 지표를 기반으로 후보 경로를 평가합니다.

4. 네트워크 과학 분석:

   • 저자들은 회로를 CNOT 이벤트(노드)와 인과적 또는 얽힘 관계(엣지)를 나타내는 유향 그래프로 분석합니다.
   • 큐비트 영역의 분리 정도와 정보 흐름의 혼합(SA 최적화 전후)을 정량화하기 위해 중심성 측정(차수 및 매개 중심성)과 합의 역학(DeGroot 모델)을 활용합니다.

주요 결과

• 퍼콜레이션 상전이 (Percolation Phase Transition): 본 연구는 양자 회로 공간에서 상전이를 식별합니다. 유효하고 균형 잡힌 분할 경로가 존재하는 영역(분할 가능)과 CNOT을 절단하지 않고서는 그러한 경로가 존재하지 않는 영역(분할 불가능)이 명확히 존재합니다.
• 스케일링 기준: 이 전이는 CNOT 게이트의 수($N_c$)와 큐비트의 수($N_q$)의 비율에 의해 결정됩니다. 저자들은 $N_c$가 $N_q$와 거의 같을 때 두 개의 균형 잡힌 CNOT 클러스터로 분할하는 것이 가능하다는 것을 관찰했습니다. 큐비트 대비 CNOT 밀도가 높아짐에 따라 "중앙 통로"가 닫히고, 회로는 분할 불가능해집니다.
• 시뮬레이티드 어닐링의 효과: SA는 회로 레이아웃을 성공적으로 재구조화하여 CNOT 상호작용을 주변부로 이동시키고, 밀도가 낮은 중앙 통로를 생성합니다. 이 변환은 벽의 분포를 단일 피크(Beta 분포) 프로파일에서 바이모달(bimodal) 프로파일로 변화시켜 수평 절단의 존재를 용이하게 합니다.
• 네트워크 역학: 중심성 분석은 분할 가능한 영역에서 SA가 상호작용을 레지스터의 가장자리 큐비트로 집중시켜 중심부를 약하게 결합 상태로 남겨둔다는 것을 보여줍니다. 합의 역학은 희소한(sparse) 영역에서는 회로가 두 개의 약하게 결합된 클러스터로 분리되는 반면, 조밀한(dense) 영역에서는 정보가 전역적으로 혼합되어 분리를 방지함을 확인해 줍니다.
• 세 가지 영역: 경로 탐색 점수를 기준으로 세 가지 뚜렷한 상(phase)이 나타납니다:
  1. 제1상 (분할 가능): CNOT과 셀의 균형을 맞추는 엄격한 수평 절단이 존재합니다.
  2. 과도 영역 (Transient Regime): 경로는 벽을 피하기 위해 수직 및 수평 단계를 번갈아 수행해야 하며, 이로 인해 덜 균형 잡힌 분할이 발생합니다.
  3. 제2상 (분할 불가능): 회로를 분리할 수 있는 유효한 절단이 존재하지 않습니다. 에이전트는 경계로 몰리게 되며, 한쪽 분할은 무시할 수 있는 수준이 되고 다른 한쪽은 거의 전체 회로를 포함하게 됩니다.

의의 및 주장
본 논문은 회로 분할을 퍼콜레이션 현상으로 이해하기 위한 이론적 및 수치적 프레임워크를 제공한다고 주장합니다. 회로를 미로로 매핑함으로써, 저자들은 CNOT 게이트를 절단하지 않고도 양자 회로를 분할할 수 있는지 여부를 식별하는 확장 가능하고 실용적인 기준을 확립했습니다.

본 연구는 얽힘 게이트를 절단 없이 분할할 수 있는 능력을 퍼콜레이션 전이의 첫 번째 상으로 위치시키며, 이를 측정 유도 상전이(measurement-induced phase transitions) 및 위상적 전이(topological transitions)와 같은 더 넓은 임계 현상과 연결합니다. 저자들은 이 프레임워크가 양자 회로 최적화의 알고리즘 개발을 위한 기초를 형성하며, 중간 회로 측정의 오버헤드 없이 여러 장치에 걸쳐 병렬 최적화 작업을 수행할 수 있는 타당성을 판단하는 방법을 제공한다고 주장합니다. 결과에 따르면, 얽힘 게이트의 수가 큐비트 수에 따라 선형적으로 스케일링되는 회로의 경우, 이러한 분할이 이론적으로 가능하며 제안된 퍼콜레이션 기준으로 식별될 수 있음을 시사합니다.