QSeqSim: A Symbolic Simulator for Qiskit While Loops Using Sequential Quantum Circuits

본 논문은 Qiskit 통합 심볼릭 시뮬레이터인 QSeqSim 을 소개하며, 이는 양자 프로그램을 순차 회로로 변환하고 대규모 다중 반복 벤치마크에 대한 측정 확률을 계산하기 위해 BDD 기반 가중 모델 카운팅을 활용함으로써 while 루프가 포함된 양자 프로그램의 효율적인 시뮬레이션을 가능하게 합니다.

핵심

매우 정교한 양자 요리 (양자 프로그램) 를 위한 레시피가 있다고 상상해 보세요. 대부분의 현대식 요리책인 Qiskit과 같은 도구는 "소스가 특정 색으로 변할 때까지 이 단계를 반복해서 요리하세요"라는 지시를 작성할 수 있게 해줍니다. 이를 while 루프라고 합니다.

하지만 지금까지 이러한 레시피를 실제로 요리하는 주방 기기 (시뮬레이터) 들은 그 지시를 이해하지 못했습니다. "특정 조건이 될 때까지 계속 요리하세요"라는 지시가 포함된 레시피를 실행하려고 하면, 기기는 단순히 충돌하거나 "이것을 어떻게 해야 할지 모릅니다"라고 말했을 뿐입니다.

QSeqSim은 바로 이러한 "특정 조건이 될 때까지 계속" 지시를 처리하도록 특별히 설계된 새로운 스마트 주방 조수입니다. 간단한 비유를 통해 그 작동 원리를 설명해 보겠습니다.

1. 문제: "루프"의 간극

표준 양자 회로를 생각하면 한 줄로 늘어선 도미노가 하나씩 쓰러지는 것과 같습니다. 첫 번째 도미노를 밀면 모두 고정된 순서로 쓰러집니다. 이는 시뮬레이션하기 쉽습니다.

하지만 while 루프는 복도에 있는 미닫이 문과 같습니다. 당신은 문을 통과해 작업을 수행하고 센서를 확인한 뒤, 센서가 "아직 완료되지 않았습니다"라고 말하면 다시 미닫이 문을 통과해 작업을 반복합니다. 문이 열릴 때마다 방의 상태 (양자 상태) 가 변하며, 문은 언제든지 닫힐 수 있습니다.

현재의 도구들 (Qiskit-Aer 등) 은 도미노가 일렬로 쓰러지는 경우만 처리할 수 있습니다. 스스로 다시 돌아오는 미닫이 문은 어떻게 처리해야 할지 모릅니다. QSeqSim은 바로 이러한 "미닫이 문" 행동을 네이티브로 이해하고 시뮬레이션하도록 설계된 최초의 도구입니다.

2. 해결책: 루프를 "기억 기계"로 변환

이러한 루프를 이해하기 위해 QSeqSim 은 양자 프로그램을 **순차 양자 회로 (Sequential Quantum Circuit)**라는 특수한 기계로 변환합니다.

• 비유: 공장의 조립 라인을 상상해 보세요.
  • 외부 큐비트 (External Qubits): 루프를 통과할 때마다 새로 들어오는 원자재와 같습니다. 측정 (확인) 된 후 폐기됩니다.
  • 내부 큐비트 (Internal Qubits): 컨베이어 벨트 위의 작업 진행 중인 제품과 같습니다. 기계 안에 머무르며 업데이트되고, 다음 루프 반복으로 이어집니다.
  • 루프: 기계가 게이지 (측정) 를 확인합니다. 게이지가 "계속 진행"이라고 말하면, 컨베이어 벨트가 다시 돌아와 업데이트된 작업 진행 중인 제품을 다음 사이클의 시작점으로 운반합니다.

QSeqSim 은 루프를 마법 같은 반복 버튼이 아니라, 이전 단계의 "기억"을 다음 단계로 전달하는 피드백 와이어를 갖춘 물리적 기계로 다룹니다.

3. 엔진: "스마트 파일 시스템" (BDDs)

양자 컴퓨터를 시뮬레이션하는 것은 어렵습니다. 가능한 경우의 수가 폭증하기 때문입니다 (거대한 미로에서 여행자가 취할 수 있는 모든 경로를 추적하려는 것과 같습니다).

QSeqSim 은 **이진 결정 다이어그램 (Binary Decision Diagrams, BDDs)**이라는 기법을 사용합니다.

• 비유: 양자 루프의 모든 가능한 결과를 담은 거대한 도서관이 있다고 상상해 보세요. 일반 컴퓨터는 도서관의 모든 책을 하나씩 읽으려 합니다.
• QSeqSim 의 트릭: 모든 책을 읽는 대신, QSeqSim 은 스마트 파일 시스템을 사용합니다. 미로의 많은 경로가 동일하다는 것을 발견하여 이를 단일 폴더로 묶습니다.
  • 1,000 개의 경로가 모두 같은 결과로 이어진다면, QSeqSim 은 이를 1,000 번 계산하지 않습니다. 한 번만 계산하고 "이 폴더는 1,000 개의 경로를 모두 대표합니다"라고 말합니다.
  • 이를 통해 이전 도구들이 감당하지 못했던 1,000 개 이상의 큐비트와 10 회 이상의 반복을 가진 루프를 압도당하지 않고 처리할 수 있습니다.

4. 가능한 것들 (결과)

저자들은 QSeqSim 이 "미닫이 문" 루프를 얼마나 잘 처리하는지 확인하기 위해 세 가지 유형의 "레시피" (벤치마크) 로 테스트했습니다.

• 성공할 때까지 반복 (Repeat-Until-Success, RUS): "이 트릭이 성공할 때까지 계속 시도하세요"라는 레시피입니다. QSeqSim 은 루프가 100 번 실행되어야 하더라도 이를 완벽하게 시뮬레이션했습니다.
• 양자 랜덤 워크: 술에 취한 사람이 격자 위를 걷는데, 매 단계마다 동전을 던져 방향을 정하고 벽에 부딪혔는지 확인하는 상황을 상상해 보세요. QSeqSim 은 **1,000 단계 이상 (큐비트)**과 10 회 이상의 루프가 포함된 워크를 시뮬레이션했습니다.
• 그로버 검색 (Grover's Search): 루프를 사용하여 건초더미에서 바늘을 찾는 유명한 검색 알고리즘입니다. QSeqSim 은 수백 개의 큐비트를 사용하여 이를 시뮬레이션할 수 있었습니다.

5. 왜 이것이 중요한가 (현재 시점에서)

이 논문은 QSeqSim 이 특정 간극을 메운다고 주장합니다: while 루프가 포함된 Qiskit 프로그램을 실제로 실행할 수 있는 최초의 도구라는 점입니다.

이전에는 프로그래머가 루프를 작성하면 수동으로 모든 단계를 풀어서 (언롤) 작성하거나, 아예 실행할 수 없었습니다. 이제 그들은 루프를 자연스럽게 작성할 수 있으며, QSeqSim 이 이를 "기억 기계"로 변환하고, 스마트 파일 시스템을 사용하여 다양한 결과의 확률을 계산한 뒤 정확한 결과를 알려줍니다.

간단히 말해: QSeqSim 은 양자 컴퓨터가 "결과가 맞을 때까지 이것을 반복하세요"라는 지시를 이해하고 실행할 수 있게 해주는 번역가이자 계산기입니다.

기술 요약

기술 요약: QSeqSim

문제 제기

양자 프로그래밍 프레임워크의 급속한 진화에도 불구하고, 현대 양자 언어의 표현력과 현재 실행 백엔드의 기능 사이에는 상당한 격차가 존재합니다. 구체적으로, Qiskit과 OpenQASM 3는 while 루프와 같은 고수준 제어 흐름 구조를 지원하여 반복-성공 (RUS), 약측정 그로버 검색, 피드백 기반 양자 랜덤 워크와 같은 패턴을 가능하게 하지만, 이러한 프로그램을 시뮬레이션할 수 있는 Qiskit 네이티브 도구는 존재하지 않습니다.

기본 시뮬레이터인 Qiskit-Aer와 현재 클라우드 하드웨어 백엔드는 while_loop 구조를 지원하지 않습니다. 이러한 프로그램을 실행하려는 시도는 제어 흐름이 해당 시뮬레이터가 처리할 수 있는 회로 형태로 저하 (lowering) 될 수 없기 때문에 구문 분석 또는 컴파일 오류로 이어집니다. 결과적으로 Qiskit 생태계 내에서 비단순한 while 루프 프로그램의 의도된 반복적 의미론을 실현하는 실행 엔진은 존재하지 않습니다.

방법론

저자들은 이 격차를 해소하기 위해 while 루프 프로그램을 **순차 양자 회로 (Sequential Quantum Circuits, SQCs)**로 해석하는 Qiskit 통합 심볼릭 시뮬레이션 백엔드인 QSeqSim을 제시합니다. 방법론은 세 가지 핵심 구성 요소를 포함합니다:

1. 의미론적 프레임워크: 조합형에서 순차형으로

QSeqSim은 고전적 제어를 포함하는 Qiskit 프로그램의 실행 모델을 재정의합니다:

• 번역: QuantumCircuit 객체를 OpenQASM 3로 변환한 후 추상 구문 트리 (AST) 로 구문 분석합니다.
• 분해: 파서가 회로 블록을 세 가지 유형으로 분류합니다:
  • CQC (조합 양자 회로): 직선형 게이트 세그먼트.
  • DQC (동적 양자 회로): 회로 중간 측정 및 조건부 분기 (if/else, switch) 를 포함하는 블록.
  • SQC (순차 양자 회로): while 루프를 나타내는 블록.
• 상태 분할: SQC 의 경우, 시스템은 양자 비트를 내부 양자 비트(상태가 유지되어 반복 간 피드백됨) 와 외부 양자 비트(반복 범위 내에서 측정되고 폐기됨) 로 명시적으로 분할합니다. 이는 양자 상태 피드백에 대한 정확한 의미론을 제공합니다.

2. 심볼릭 실행 엔진 (BDD 기반)

QSeqSim 의 핵심은 순차적 행동을 처리하도록 양자 회로의 기존 부울 인코딩 (특히 Tsai 외의 연구) 을 확장한 이진 결정 다이어그램 (BDD) 기반 엔진입니다:

• 심볼릭 연산자: 엔진은 루프 반복 간 상태 진화를 관리하기 위해 두 가지 전용 연산자를 도입합니다:
  • 상태 조합: 현재 내부 상태와 새로운 외부 입력 상태를 텐서 곱합니다.
  • 상태 유지: 측정된 외부 양자 비트를 폐기하면서 다음 반복을 위해 업데이트된 내부 상태를 보존하기 위해 부분 추적 (partial trace) 을 수행합니다.
• 운영 의미론: 시뮬레이터는 루프 가드 (고전 비트에서 유도됨) 가 거짓으로 평가될 때까지 루프 본문을 반복적으로 실행하여 while 루프를 펼치는 작은 단계 운영 의미론을 사용하여 프로그램을 실행합니다.

3. 효율적인 확률 계산

심볼릭 시뮬레이션의 주요 과제는 명시적 열거 없이 대규모 구조화된 결정 다이어그램에 대한 측정 확률을 계산하는 것입니다.

• 가중 모델 카운팅 (WMC): QSeqSim은 하이퍼 함수 구성 대신 구조화되고 희소한 BDD 에 가중 모델 카운팅을 적용합니다. 이를 통해 시스템은 BDD 크기에 비례하는 시간에 기저 상태의 기여도를 집계하여, 회로 중간 측정 및 루프 가드에 필요한 확률 쿼리를 효율적으로 처리할 수 있습니다.

주요 기여

논문은 다음과 같은 주요 기여를 주장합니다:

1. 직접 while 루프 지원을 제공하는 최초의 Qiskit 백엔드: QSeqSim은 while 루프를 포함하는 Qiskit 프로그램을 OpenQASM 3 로 저하시키고 실행 가능한 작은 단계 의미론을 제공함으로써 직접 실행하는 최초의 도구입니다.
2. 순차 부울 모델로의 확장: 상태 조합 및 유지를 위한 심볼릭 연산자를 도입하여 순차 양자 회로의 명시적 상태 피드백 모델링을 가능하게 함으로써, BDD 기반 인코딩을 순수 조합 회로에서 일반 순차 회로로 확장합니다.
3. 확장 가능한 심볼릭 시뮬레이션: 성숙한 BDD 백엔드와 WMC 기법을 활용함으로써 QSeqSim은 기존 도구의 능력을 넘어선 while 루프로 인한 순차 회로의 효율적인 시뮬레이션을 달성합니다.

실험 결과

저자들은 MacBook Air(M2, 16 GB) 에서 세 가지 벤치마크 카테고리를 사용하여 QSeqSim 을 평가했습니다:

• 반복 - 성공 (RUS): 시스템은 다양한 유니타리 연산자를 가진 RUS 회로를 성공적으로 시뮬레이션했습니다. 짧은 루프 (10 회 반복) 는 1 초 미만으로 완료된 반면, 더 긴 루프 (100 회 반복) 는 약 1.5 초에서 약 108 초 사이의 실행 시간을 보여 BDD 구조에 대한 특정 유니타리의 영향에 민감함을 입증했습니다.
• 양자 랜덤 워크 (QRW): 이 도구는 10 회 이상의 루프 반복에 대해 1000 개 이상의 양자 비트(구체적으로 $N=1024$ 위치 사이트) 를 가진 회로로 확장되었습니다. 그러나 성능은 반복당 게이트 수에 의해 제한되었습니다. $N=1024$의 경우 30 분 타임아웃 내에서 최대 13 회 반복만 가능했습니다.
• 그로버 검색: 유사한 확장성 추세가 관찰되었습니다. 256 개의 양자 비트의 경우, 시스템은 타임아웃 전에 최대 5 회 반복까지 처리했으며, 이는 BDD 가 깊은 루프를 잘 처리하지만 매우 큰 다중 양자 비트 연산자와 반복 반복의 결합은 여전히 계산 집약적임을 나타냅니다.
• 무작위 while 루프: 100 개의 양자 비트 무작위 회로에서 QSeqSim 은 처리 가능했으며, 다양한 게이트 및 측정 밀도에서 중앙 실행 시간이 1 분 미만으로 유지되었습니다.

이 도구는 또한 도달 가능성 분석에서 유용성을 입증하여, 특정 상태 구성 (예: 보행자가 특정 위치에 도달하는 것) 및 측정 결과 패턴 (예: 루프 종료 확률) 에 대한 정확한 확률을 샘플링 노이즈 없이 계산했습니다.

중요성 및 주장

이 논문은 QSeqSim 을 양자 프로그래밍 언어의 고수준 표현력과 현재 시뮬레이터의 제한 사항 사이의 필수적인 연결고리로 위치시킵니다. 그 중요성은 다음과 같습니다:

• 형식 분석 가능화: while 루프에 대한 네이티브 실행 엔진을 제공함으로써, 이전에는 Qiskit 생태계에서 접근할 수 없었던 피드백 및 측정 제어 반복이 포함된 양자 프로그램의 형식 검증 및 분석을 가능하게 합니다.
• 심볼리즘을 통한 확장성: BDD 와 가중 모델 카운팅을 사용한 심볼릭 시뮬레이션이 상당한 양자 비트 수와 루프 깊이를 가진 순차 양자 회로를 효과적으로 처리할 수 있으며, 이러한 특정 구조화된 문제에 대해 단순한 상태 벡터 시뮬레이션보다 우수한 성능을 보임을 입증합니다.
• 미래 작업의 기반: 저자들은 현재 구현이 상용 하드웨어에서 실행되지만, 아키텍처는 더 대규모의 시뮬레이션 및 형식 검증 작업을 처리하기 위해 병렬화가 지원되는 서버급 머신에 대한 향후 배포를 지원하도록 설계되었다고 언급합니다.