당신이 복잡한 오케스트라(양자 회로)를 지휘하여 교향곡을 연주하려는 지휘자라고 상상해 보십시오. 하지만 당신에게는 공연장 한 곳조차 없습니다. 대신, 당신은 복도(양자 네트워크)로 연결된 여러 곳에 흩어져 있는 서로 다른 음악실(양자 컴퓨터 또는 QC)의 공간을 빌려야 합니다.

각 음악실에는 저마다의 규칙이 있습니다:

어떤 방은 매우 크지만 대여료가 비쌉니다.
어떤 방은 작고 저렴하지만 한 번에 아주 적은 수의 연주자만 수용할 수 있습니다.
어떤 방은 특정 악기(게이트)에 적합한 음향을 갖추고 있지만, 어떤 방은 최악입니다.
연주자를 한 방에서 다른 방으로 옮기는 데는 시간과 비용이 들며, 이는 복도를 따라 걷는 것(마이그레이션)이거나, 미리 약속된 마법 링크가 필요한 마법의 순간이동 장치를 사용하는 것일 수 있습니다.

당신의 목표는 이 교향곡을 최대한 빠르고 저렴하게 연주하는 것입니다. 당신은 네 가지 큰 결정을 내려야 합니다:

각 방에서 얼마나 많은 연주자를 고용할 것인가.
매 순간 각 연주자를 어디에 배치할 것인가.
어떤 곡의 파트를 어느 방에서 연주할 것인가.
음악의 요구에 따라 연주자들을 방 사이에서 어떻게 이동시킬 것인가.

이 논문의 저자들은 이 문제를 결합 양자 큐비트 리싱 및 양자 회로 분배(JQLQCD) 문제라고 부릅니다.

핵심 과제: 완벽하게 풀기에는 너무 어려운 퍼즐

저자들은 일반적이고 복잡한 규칙을 가진 많은 방과 복잡한 오케스트라의 경우, 완벽한 해답을 찾는 것이 수학적으로 불가능하다는 것을 증명했습니다. 컴퓨터 과학 용어로, 이 문제는 **NP-완전(NP-complete)**입니다. 이는 숫자를 더 많이 넣을수록 기하급수적으로 어려워지는 스도쿠 퍼즐을 푸는 것과 같습니다. 컴퓨터는 최적의 배치를 찾기 위해 모든 가능한 연주자 배치 조합을 일일이 확인해야 하며, 대규모 오케스트라의 경우 우주의 나이보다 더 긴 시간이 걸릴 수도 있습니다.

완벽한 해결이 가능한 "특수 사례들"

하지만 상황이 단순해진다면, 완벽한 답을 빠르게 찾을 수 있다는 것을 저자들은 발견했습니다. 그들은 수학적으로 다룰 수 있는 6가지 "특수 시나리오"를 식별했습니다:

"무제한 공간" 시나리오: 만약 한 방이 무한히 크고 무료라면, 그냥 모든 사람을 그곳에 몰아넣고 다른 방은 무시하면 됩니다.
"동일한 음악실" 시나리오: 모든 방이 정확히 같고 연주자 이동이 무료라면, 곡을 빨리 끝내기 위해 사람들을 고르게 분산시키면 됩니다.
"선형 체인" 시나리오: 곡이 단 하나의 긴 음표 줄기(분기가 없는 형태)라면, 지도의 최단 경로를 찾는 것처럼 선을 따라가기만 해도 최적의 경로를 파악할 수 있습니다.
"독립된 밴드" 시나리오: 오케스트라가 실제로 서로 상호작용하지 않는 서로 다른 노래를 연주하는 여러 개의 작은 밴드로 구성되어 있다면, 각 밴드의 문제를 개별적으로 해결할 수 있습니다.
"무한 자원" 시나리오: 돈과 공간이 중요하지 않다면, 물리적으로 가능한 한 가장 빠르게 곡을 마치는 데에만 집중하면 됩니다.
"트리 구조" 시나리오: 곡의 구조가 단순한 트리 형태(가계도와 같은 형태)라면, 끝에서부터 시작으로 거꾸로 올라가며 가장 저렴한 경로를 찾을 수 있습니다.

현실 세계를 위한 "탐욕적(Greedy)" 해결책

대부분의 실제 양자 회로는 이러한 단순한 특수 사례에 해당하지 않으므로, 저자들은 완벽하지는 않더라도 빠르게 "좋은" 답을 얻을 수 있는 방법이 필요했습니다. 그들은 **"탐욕 알고리즘(Greedy Algorithm)"**을 만들었습니다.

이 알고리즘을 매우 효율적이지만 약간 성급한 매니저라고 생각해보십시오. 모든 가능한 배치를 확인하는 대신(시간이 너무 오래 걸림), 이 매니저는 일련의 스마트하고 국소적인 결정을 내립니다:

방 점수 매기기: 매니저는 각 방을 살펴보고, 대여 비용과 다른 방으로부터의 접근 용이성을 바탕으로 점수를 매깁니다.
최선 선택: 그들은 점수가 가장 높은 방을 먼저 선택합니다.
채우기: 그곳에서 잘 작동하는 악기를 연주하고, 상호작용이 필요한 다른 연주자들과 가까이 있는 연주자들을 우선순위로 두어 방을 채웁니다.
정교화: 초기 할당이 끝난 후, 매니저는 빠른 "국소 탐색(local search)"을 수행하여, 연주자를 다른 방으로 옮기는 것이 비용이나 시간을 절약할 수 있는지 확인합니다. 만약 그렇다면, 그 교체를 실행합니다.

결과: 빠르고 충분히 좋은 결과

저자들은 이 "탐욕적 매니저"를 **시뮬레이티드 어닐링(Simulated Annealing)**이라 불리는 훨씬 느리고 철저한 방식(운이 좋기를 바라며 무작위적인 변화를 계속 시도하는 매우 인내심 강한 매니저와 같은 방식)과 비교 테스트했습니다.

속도: 탐욕적 매니저는 인내심 강한 매니저보다 50배에서 200배 더 빨랐습니다. 대규모 오케스트라의 경우, 탐욕적 매니저는 1초도 안 되어 계획을 마쳤지만, 인내심 강한 매니저는 30분 이상이 걸렸습니다.
품질: 탐욕적 매니저의 계획은 인내심 강한 매니저가 찾아낸 최선의 계획보다 비용이 8%에서 15% 정도 더 높았습니다.

결론

이 논문은 복잡한 작업에 대해 양자 컴퓨터를 대여하고 양자 회로를 분배하는 완벽한 방법을 빠르게 찾는 것은 수학적으로 불가능하지만, 우리에게 필요한 것은 완벽함이 아니라 속도라는 점을 강조합니다. 그들의 "탐욕 알고리즘"은 매우 효율적인 물류 코디네이터처럼 작동합니다: 완벽한 해결책만큼이나 잘 해내면서도 훨씬 짧은 시간 안에 스마트하고 빠른 결정을 내리며, 이는 즉각적인 결정이 필요한 실제 상황에서 매우 실용적입니다.

기술 요약: 큐비트 리싱 및 양자 회로 분배의 결합 최적화

1. 문제 정의

본 논문은 결합 큐비트 리싱 및 양자 회로 분배(Joint Qubit Leasing and Quantum Circuit Distribution, JQLQCD) 문제를 다룬다. 이 문제는 에이전트가 양자 네트워크로 연결된 이종(heterogeneous) 양자 컴퓨터(QC) 네트워크로부터 리스(lease)한 자원을 사용하여 특정 양자 회로를 실행하고자 할 때 발생한다.

회로 분할(partitioning)이나 단일 장치로의 매핑(mapping)에만 집중했던 기존 연구와 달리, JQLQCD는 에이전트가 다음 네 가지 상호 의존적인 결정을 동시에 내려야 한다:

리싱(Leasing): 각 QC로부터 얼마나 많은 저장 및 실행 큐비트를 리스할지 결정한다.
배치(Placement): 특정 시간 슬롯 동안 서로 다른 회로 큐비트를 어느 QC에 저장할지 결정한다.
스케줄링(Scheduling): 회로의 각 게임을 특정 QC에서 실행하도록 할당한다.
이동(Movement): 게이트 피연산자(operand) 요구 사항을 충족하기 위해 큐비트를 QC 간에 이동시키는 방법(물리적 전송을 통한 마이그레이션(migration) 또는 사전 공유된 얽힘을 통한 텔레포테이션(teleportation))을 선택한다.

목표는 다음을 포함하는 총 시스템 비용 함수를 최소화하는 것이다:

리싱 비용 (저장 및 실행 용량).
게이트 실행 비용 (QC마다 다름).
통신 비용 (마이그레이션 및 텔레포테이션).
$\beta$ 로 가중치가 부여된 메이크스팬(makespan, 회로 완료 시간).

이 문제는 QC의 저장 및 실행 용량, 게이트 가용성(일부 게이트는 모든 QC에서 실행할 수 없음), 그리고 회로 선행 제약 조건(DAG 구조)에 의해 제약을 받는다.

2. 방법론

A. 수학적 정식화

저자들은 JQLQCD를 포괄적인 정수 선형 계획법(Integer Linear Programming, ILP) 모델로 정식화한다. 이 정식화는 다음을 명시적으로 모델링한다:

결정 변수: 큐비트 위치( $x_{q,p,t}$ ), 실행 사용( $z_{q,p,t}$ ), 이동 유형(마이그레이션 $\gamma$ 또는 텔레포테이션 $w$ ), 게이트 할당( $u_{g,p}$ )을 위한 이진 변수; 시작 시간( $t_g$ ) 및 메이크스팬( $T_{max}$ )을 위한 정수 변수.
제약 조건: 용량 제한, 큐비트 유일성, 게이트 할당 유효성, 실행 시 피연산자 존재 여부, 선행 제약 조건, 그리고 이동 일관성(위치 변경이 유효한 마이그레이션 또는 텔레포테이션 이벤트와 일치하는지 확인).
비용 모델링: 마이그레이션과 텔레포테이션 모두에 대해 거리 의존적 비용을 반영하여, 물리적 전송과 얽힘 기반 통신 사이의 트레이드오프를 인정한다.

B. 복잡도 분석

본 논문은 일반적인 JQLQCD 문제가 **NP-완전(NP-complete)**임을 증명한다. 이는 알려진 NP-완전 문제인 선행 제약이 있는 멀티프로세서 스케줄링 문제( $P|prec|C_{max}$ )로부터 다항 시간 환원을 통해 입증된다. 나아가, 이 문제는 **강한 NP-완전(strongly NP-complete)**임이 밝혀졌으며, 이는 $P=NP$가 아닌 한 의사 다항 시간(pseudo-polynomial time) 알고리즘이 존재할 수 없음을 의미한다.

그러나 저자들은 문제의 파라미터가 QC의 수( $|P|$ ), 최대 QC 용량( $\kappa$ ), 그리고 회로 의존 그래프의 트리 폭(tree-width)일 때, 이 문제가 **고정 파라미터 계산 가능(Fixed-Parameter Tractable, FPT)**하다는 것을 확립한다.

C. 특수 사례 및 정확한 알고리즘

일반적인 난해성을 인식하여, 본 논문은 폐쇄형(closed form)으로 해결하거나 다항 시간 알고리즘으로 최적해를 구할 수 있는 6가지 특수 사례를 식별한다:

이종 네트워크 내 무제한 용량 QC: 중앙 집중식 솔루션(무제한 용량의 QC만 사용)이 최적인 충분 조건 및 필요 조건을 도출한다.
제로 이동 비용을 갖는 동종(Homogeneous) QC: 리싱 비용과 메이크스팬( $\beta$ ) 사이의 트레이드오프를 바탕으로 사용할 최적의 QC 수를 결정하는 알고리즘을 제공한다.
순차적 게이트를 갖는 체인 토폴로지: 문제를 시간 확장 그래프(time-expanded graph) 상의 최단 경로 문제로 축소하며, 이는 디이크스트라(Dijkstra) 알고리즘이나 동적 계획법(DP)을 통해 해결 가능하다.
독립적 서브회로: 회로를 서로 분리된 구성 요소로 나누어 각각 독립적으로 해결하는 분해 접근 방식을 제안한다.
메이크스팬 최소화만을 고려한 무한 자원: 고전적인 멀티프로세서 스케줄링 문제로 축소되며, 임계 경로 분석을 통해 해결 가능하다.
트리 구조 회로: 역위상 정렬 순서로 게이트를 처리하는 DP 접근 방식을 사용하여 최적 비용을 찾는다.

D. 일반 인스턴스를 위한 휴리스틱

정확한 해를 구하는 것이 계산적으로 불가능한 일반 인스턴스를 위해, 저자들은 **국소 탐색 정교화가 포함된 그리디 알고리션(Greedy Algorithm with Local Search Refinement)**을 제안한다:

그리디 단계: 리싱 비용과 평균 통신 비용의 복합 지표를 기준으로 QC의 점수를 매긴다. 큐비트는 낮은 점수와 높은 친화도(상호작용하는 큐비트를 함께 배치)를 가진 것들을 우선시하여 반복적으로 QC에 할당된다.
정교화 단계: 국소 탐색은 목적 함수를 개선하는 이동을 수용하면서, 총 비용을 줄이기 위해 큐비트를 다른 QC로 재할당하는 시도를 반복한다.

3. 주요 기여

본 논문의 주요 기여는 다음과 같다:

문제 정식화: 마이그레이션과 텔레포테이션 프리미티브를 모두 명시적으로 모델링하여, 자원 리싱과 회로 분배의 결합 최적화를 위한 최초의 포괄적인 ILP 정식화를 제공한다.
복잡도 증명: 일반 문제에 대한 NP-완전성 및 강한 NP-완전성 증명.
특수 사례 분석: 다항 시간 또는 폐쇄형 최적해를 허용하는 6가지 특정 시나리오와 이종 네트워크에서의 최적성을 위한 필요충분조건 식별.
휴리스틱 개발: 분산 양자 컴퓨팅에서의 실시간 의사결정을 위해 설계된 국소 탐색 기반의 실용적인 그리디 알고리즘.
경험적 검증: 시뮬레이티드 어닐링(SA) 및 최적 솔루션과 비교하여 알고리즘의 성능을 보여주는 광범위한 수치적 평가.

4. 수치 결과

저자들은 다양한 파라미터(회로 크기, QC 수, 메이크스팬 가중치 $\beta$ )에 대해 제안된 그리디 알고리즘을 시뮬레이티드 어닐링(SA) 및 특수 사례의 최적 솔버와 비교 평가하였다.

솔루션 품질:
- 일반 인스턴스의 경우, 그리디 알고리즘은 SA가 찾은 비용의 8~15% 이내의 해를 달성한다.
- 알려진 최적해가 있는 특수 사례의 경우, 그리디 알고리즘은 최적해의 4~12% 이내의 해를 찾는다.
- 순차적 회로 케이스(Case 3)의 경우, 그리디 알고리즘은 최적해의 3~5% 이내를 유지하며 매우 우수한 성능을 보인다.
계산 효율성:
- 그리디 알고리즘은 SA보다 50~200배 빠르다.
- 대규모 인스턴스(50 큐비트, 500 게이트, 10 QC)의 경우, 그리디 알고리즘은 4.2초 만에 완료되는 반면, SA는 2000초 이상(33분)이 소요된다.
- 그리디 알고리즘은 실제 적용 시 근사 선형 시간 복잡도( $O(|G|^{1.15})$ )를 보이며, 대규모 회로로 효과적으로 확장된다.
확장성: 알고리즘은 문제 규모가 커짐에 따라 SA 대비 일관된 솔루션 품질을 유지하므로, 빠른 의사결정이 중요한 실시간 시나리오에 적합하다.

5. 의의 및 주장

본 논문은 회로 분할이나 단일 장치 매핑과는 구별되는, 자원 리싱과 회로 분배의 결합 최적화를 다룸으로써 문헌의 중요한 공백을 메운다고 주장한다.

저자들은 사용자가 여러 제공자로부터 자원을 임대해야 하는 신흥 양자 클라우드 컴퓨팅 환경에서 본 연구가 중요하다고 강조한다. 비용과 성능의 균형을 맞추는 실행 가능한 휴리스틱을 제공함으로써, 본 논문은 분산 양자 워크로드를 관리하는 에이전트에게 실용적인 도구를 제공한다. 결과는 일반적인 문제가 계산적으로 어렵더라도, 특히 현재 및 가까운 미래의 양자 하드웨어(제한된 큐비트 수 및 결맞음 시간)의 제약을 고려할 때 효율적인 근사법이 실현 가능하다는 것을 시사한다.

본 논문은 향-보장(provable guarantees)이 있는 근사 알고리즘, 충실도(fidelity) 및 동적 실행을 포함한 확장된 정식화, 그리고 실제 양자 네트워크 테스트베드에서의 실험적 검증을 향후 연구 과제로 제시하며 마무리한다.

Joint Optimization of Qubit Leasing and Quantum Circuit Distribution