Optimizing Parallel Execution of Commuting Pauli Product Rotations

본 논문은 결함 허용 양자 컴퓨팅에서 교차하는 파울리 곱 회전 연산의 병렬 실행을 최적화하기 위해 클리크 재배열과 생성자 재구성을 두 가지 휴리스틱으로 제안하여, 큐비트당 포트 제약을 완화함으로써 하드웨어 제한으로 인한 회로 깊이를 크게 줄이는 것을 목표로 한다.

핵심

거대한 양자 컴퓨터를 위한 대규모 고위험 무도회를 조직한다고 상상해 보세요. 목표는 모든 사람이 최대한 빠르게 춤추도록(계산을 수행하도록) 하는 것입니다.

오류 정정 양자 컴퓨팅(자신의 실수를 스스로 수정할 수 있는 방식) 세계에는 특별한 규칙이 하나 있습니다. 두 명의 춤추는 사람(양자 연산) 이 서로 간섭하지 않는다면, 그들은 동시에 춤출 수 있다는 것입니다. 이를"교환(commuting)"이라고 합니다.

그러나 함정이 하나 있습니다. 무대(하드웨어) 는 특정 춤추는 사람의 손을 동시에 잡을 수 있는 사람 수에 엄격한 제한이 있습니다. 각 춤추는 사람이 동시에 잡을 수 있는 손이 단 두 개(포트) 만 있다고 생각하세요. 만약 세 사람이 동시에 같은 춤추는 사람의 손을 잡으려 한다면, 시스템이 충돌하거나 기다려야 하므로 전체 속도가 느려집니다.

이 논문은 무대 매니저가 모든 사람이 손이 부족해지지 않고 함께 춤출 수 있도록 파티를 조직하는 새로운 규칙 세트를 다룹니다.

문제: "손 잡기"병목 현상

저자들은 **파울리 곱 회전 **(Pauli Product Rotations)이라고 불리는 특정 유형의 양자 계산을 살펴보았습니다. 이는 복잡한 춤 동작과 같습니다.

• 이상적인 상황: 서로 충돌하지 않는 4 개의 동작이 있다면, 모든 동작을 하나의 큰 그룹(춤의 한"단계") 으로 수행할 수 있어야 합니다.
• 현실: 비록 충돌하지 않더라도, 모든 동작이 같은 춤추는 사람의"X-손"또는"Z-손"을 잡으려 할 수 있습니다. 하드웨어가 동시에 잡을 수 있는 손이 2 개만 허용된다면, 4 개의 동작을 한 번에 수행할 수 없습니다. 2 개는 지금 수행하고 2 개는 나중에 수행하도록 나누어야 합니다. 이로 인해 한 단계가 두 단계로 나뉘어 전체 춤이 더 오래 걸리게 됩니다 (회로 깊이 증가).

해결책: 두 가지 새로운 트릭

저자들은 규칙을 위반하지 않고 더 많은 사람을 수용하기 위해 무대를 재배치하는 두 가지 영리한 휴리스틱(지능적인 단축키) 을 제안합니다.

1. 클리크 재배치 (The "Seating Chart" Shuffle)

모두가 잘 지내는 친구 그룹이 있다고 상상해 보세요. 그들을 한 테이블에 앉힙니다. 하지만 현재 앉은 방식 때문에 모두 같은 소금통 (하드웨어 포트) 에 도달하려 할 수 있습니다.

• 트릭: 저자들은 그룹 내 춤추는 사람들의 순서를 무작위로 섞을 것을 제안합니다.
• 결과: 누가 누구 옆에 서는지 변경함으로써"소금통"요구가 더 고르게 분산되는 새로운 배열을 찾을 수 있습니다. 이를 통해 이전에 나뉘었던 그룹들을 병합할 수 있어 필요한 총 단계 수를 줄일 수 있습니다.
• 비유: 결혼식 좌석표를 재배열하는 것과 같습니다. 손님은 동일하더라도 누가 누구 옆에 앉는지 변경하면 동시에 같은 접시를 전달하려는 사람이 줄어듭니다.

2. 생성자 재구조화 (The "Math Magic" Rewrite)

이것은 더 복잡한 트릭입니다. 춤추는 그룹이 루틴을 수행한다고 상상해 보세요. 이 루틴은 일련의"기본 동작"(생성자) 으로 정의됩니다.

• 트릭: 수학적으로 동일한 최종 춤 동작을 다른 기본 동작의 조합으로 설명할 수 있는 경우가 많습니다. 저자들은 춤의 수학을 다시 써서 춤추는 사람들이 정확히 같은 결과를 얻기 위해 다른 손을 사용하도록 하는 방법을 찾았습니다.
• 결과: 세 명의 춤추는 사람이 모두"X-손"을 잡는 대신, 하나는"X-손"을 잡고 다른 하나는"Z-손"을 잡거나, 서로 상쇄되어 아무도 손을 잡을 필요가 없도록 지시를 다시 씁니다.
• 비유: 부엌에 가기 위해 붐비는 거실 (바쁜 포트) 을 통과할 필요가 없다는 것을 깨닫는 것과 같습니다. 같은 장소로 이어지지만 교통량이 적은 복도를 통해 다른 경로를 택할 수 있습니다.

그들이 발견한 것

이 팀은 QASMBench 와 같은 표준 양자 회로 라이브러리에 이러한 트릭을 테스트했습니다.

• 성과: 두 가지 트릭을 함께 사용하여 컴퓨터가 기다려야 하는 시간 (깊이) 을 **평균 10% 에서 20%**까지 줄였습니다.
• 최고 사례: 특정 시나리오에서는 최대 **50%**까지 감소하는 것을 보았습니다. 이는 장편 영화의 시간을 장면을 재배열하기만 해서 절반으로 줄이는 것과 같습니다.
• 하드웨어 제한: 이러한 트릭은 하드웨어에"손"(포트) 이 적당히 있을 때 가장 잘 작동한다는 것을 발견했습니다. 하드웨어가 너무 붐비면 (너무 많은 포트가 필요하면) 트릭이 큰 도움을 줍니다. 하지만 하드웨어가 매우 진보하여 많은 포트 (약 20 개 이상) 를 갖추게 되면 병목 현상이 자연스럽게 사라지기 때문에 트릭의 도움은 줄어듭니다.

결론

이 논문은 새로운 하드웨어를 발명하는 것이 아니라 더 나은 소프트웨어 조직을 발명하는 것입니다. 현재 양자 컴퓨터의 엄격한 물리적 제한 (큐비트당 두 개의"손"만 가능) 이 있더라도, 지시 사항을 그룹화하고 다시 쓰는 방식을 더 똑똑하게 함으로써 계산을 크게 가속화할 수 있음을 보여줍니다.

이를 양자 도시의 교통 통제라고 생각하세요. 더 많은 도로 (하드웨어) 를 즉시 건설할 수는 없지만, 교통 흐름을 변경 (재배치) 하고 차량을 우회 (재구조화) 함으로써 정체를 해소하고 모든 사람이 목적지에 훨씬 빠르게 도달하게 할 수 있습니다.

기술 요약

기술적 요약: 교환하는 파울리 곱 회전 병렬 실행 최적화

문제 제기
결함 허용 양자 컴퓨팅 (FTQC), 특히 격자 수술이 탑재된 표면 코드 아키텍처 내에서 이론적 최소 회로 지속 시간은 상호 교환하는 파울리 곱 회전 (PPR) 그룹의 수에 의해 결정됩니다. 상호 교환하는 PPR 들은 이론적으로 병렬로 실행될 수 있지만, 실제 하드웨어는 논리 큐비트당 "접근점" 또는 "포트"에 대해 엄격한 제약을 부과합니다. 표준 표면 코드에서 각 논리 패치는 논리 정보와 인터페이스하기 위해 제한된 수의 X 및 Z 에지 (일반적으로 각각 두 개) 를 제공합니다.

한 큐비트당 포트 예산을 초과하는 교환하는 PPR 집합 (예: 두 개의 포트만 사용 가능한 경우 단일 큐비트에서 세 개의 동시 X 측정이 필요한 경우) 이 발생할 때, 해당 그룹은 순차적 단계로 분할되어야 합니다. 이러한 분할은 교환 관계만으로 유도된 이론적 최소값을 넘어 회로 깊이를 증가시킵니다. 기존 컴파일 도구는 물리 계층 연결性或 잡음 감소에 주로 초점을 맞추지만, 포트 포화로 인해 교환하는 연산이 강제로 직렬화되는 이러한 특정 논리 계층 제약은 충분히 다루지 못합니다.

방법론
저자들은 논리 큐비트 오버헤드를 증가시키지 않고 PPR 의 병렬 실행을 최적화하는 컴파일 프레임워크를 제안합니다. 이 접근법은 입력 회로가 파울리 기반 컴퓨팅 (PBC) 패러다임을 통해 파울리 곱 측정 (PPM) 시퀀스로 이미 컴파일되었다고 가정합니다. 여기서 클리포드 게이트는 끝으로 이동하여 측정에 흡수되고, 비클리포드 회전과 자원 상태 측정만 남습니다.

본 논문은 하드웨어 제한된 깊이를 줄이기 위해 두 가지 주요 휴리스틱을 도입합니다:

1. 클릭 재배열 (Clique Reshuffling):

   • 입력 회로는 초기에 상호 교환하는 곱들의 최대 집합 (클릭) 으로 분할됩니다.
   • 저자들은 클릭 내 곱들의 순서가 하드웨어 제약이 적용될 때 이들이 어떻게 재그룹화되는지에 영향을 미친다고 관찰합니다.
   • 이 휴리스틱은 그룹 내 교환하는 곱들의 순서를 치환하고 그룹화를 재평가하는 것을 포함합니다. 무작위 치환 (특히 인접한 교환 쌍을 스왑하는 것) 을 샘플링함으로써, 알고리즘은 결과 하드웨어 제약 그룹의 수가 적거나 포트 사용에 있어 더 균형을 이루는 구성을 찾습니다.

2. 생성자 재구성 (Generator Restructuring):

   • 상호 교환하는 그룹 내에서 곱들의 집합은 순 논리 연산자를 위한 생성 집합으로 작용합니다. 모든 동등한 생성 집합은 동일한 논리 연산을 수행합니다.
   • 저자들은 각 회전에 대해 고유한 자원 상태에 Z-기저 측정을 추가함으로써 PPR 이 PPM 으로 변환된다는 사실을 활용합니다. 이 구조는 그룹 내 다른 곱 $P_j$를 사용하여 곱 $P_i$를 동등한 곱 $P_i \otimes P_j$로 대체할 수 있게 하여, 생성자를 효과적으로 다시 씁니다.
   • 목표는 특정 큐비트에서 비항등 문자 (X, Y, Z) 의 빈도를 최소화하는 새로운 생성 집합을 선택하여 "포트 압력"을 줄이는 것입니다.
   • 모든 $O(2^{s^2})$ 생성 집합을 나열하는 것은 계산적으로 불가능하므로, 저자들은 탐욕 휴리스틱을 사용합니다. 이 휴리스틱은 하드웨어 제한을 초과하는 큐비트 (예: X 요구 사항이 3 인 큐비트에서 X 개수를 2 로 줄이는 경우) 에서 특정 포트 유형의 카운트를 줄이는 결과 곱을 생성하도록 파울리 쌍을 곱하여 선택합니다.

통합 및 워크플로우
제안된 접근법은 이러한 전략들을 결합합니다. 먼저 클릭 재배열을 적용하여 입력 회로의 여러 변형을 생성합니다. 각 변형에 대해 탐욕 생성자 재구성을 적용하여 포트 사용을 최소화합니다. 마지막으로, 각 변형에 대해 하드웨어 제약 교환 그룹을 구성하고 최소 회로 깊이를 산출하는 구성을 선택합니다.

결과
저자들은 QASMBench 스위트에서 방법론을 평가하여 회로를 Clifford+T 및 Clifford+Rz 형식으로 컴파일한 후 이를 PPR 로 변환했습니다.

• 깊이 감소: 결합된 휴리스틱은 비재순서 기준선 대비 평균 하드웨어 제한 깊이 감소율을 10~20% 달성했습니다. 특정 사례에서는 감소율이 50% 에 달했습니다.
• 확장성: 성능 향상은 큐비트당 포트 예산에 따라 확장되는 것으로 관찰되었습니다. 사용 가능한 X/Z 포트 수가 증가함에 따라 깊이 감소가 개선되어 결국 20 포트 근처에서 포화되었습니다. 이는 하드웨어 아키텍처가 더 많은 접근점을 노출하도록 진화함에 따라 휴리스틱이 여전히 효과적임을 시사합니다.
• 민감도: 저자들은 비자명한 파울리 가중치의 밀도가 증가함에 따라 (더 작은 교환 클릭으로 이어짐) 깊이 감소가 감소한다고 지적했습니다. 또한, 재배열 횟수를 늘리는 것은 체감 효과를 가져왔으며, 대부분의 이득은 처음 몇 번의 실행에서 실현되었습니다.

의의 및 주장
본 논문은 표면 코드의 논리 컴파일에서 특정 병목 현상, 즉 제한된 물리적 접근 포트로 인한 교환 연산의 직렬화 문제를 해결한다고 주장합니다. 포트 제약 병렬화 문제를 공식화하고 다항 시간 휴리스틱 (클릭 재배열 및 생성자 재구성) 을 제안함으로써, 저자들은 논리 큐비트 수를 증가시키거나 복잡한 라우팅 솔루션을 요구하지 않고도 상당한 깊이 감소가 가능함을 입증했습니다.

저자들은 명시적으로 그들의 분석이 제약 없는 라우팅을 가정한다고 명시했습니다 (즉, 특정 포트로 논리 큐비트를 라우팅하는 오버헤드를 모델링하지 않음). 그들은 평면 표면 코드와 같은 라우팅 제약 아키텍처에서 이러한 개선을 적용하려면 추가 분석이 필요하며 이는 향후 과제로 남겨두었다고 인정합니다. 이 작업은 교환하는 파울리 그룹의 대수적 성질을 활용하는 하드웨어 동기화 병렬화 최적화에 대한 개념 증명 역할을 합니다.