Faster algorithm for achieving minimal-size quantum decision diagrams

기술 요약: 최소 크기 양자 결정 다이어그램 달성을 위한 더 빠른 알고리즘

문제 정의
결정 다이어그램(DD)은 양자 상태와 연산을 표현하기 위한 압축된 데이터 구조로, 동등한 하위 함수들을 정형(canonical) 형태로 병합함으로써 간결성을 달성한다. Local Invertible Map Decision Diagrams (LIMDD)는 특정 회로 클래스(예: Clifford 회로)에 대해 Quantum Multiple-Valued Decision Diagrams (QMDD)와 같은 다른 구조들보다 이론적으로 지수적인 이점을 제공하지만, 기존 구현체들에서는 이러한 이점이 충분히 실현되지 못했다.

주요 병목 현상은 정규형(normal-form) 절차, 특히 정형성을 보장하기 위해 요구되는 **고 결정론 규칙(high determinism rule)**이다. 이 규칙은 두 노드가 로컬 가역 맵(LIM)에 대해 동일한 양자 상태를 나타내는 자유도를 해결한다. 이 규칙을 위한 기존 알고리즘은 $n$-큐비트 노드에 대해 최악의 경우 $O(n^3)$의 시간 복잡도를 갖는 군론적 과업에 기반한다. 또한, 기존의 오픈 소스 구현체들(MQT-LIMDD 및 LimTDD)은 모든 경우에 최소 크기를 달ach하지 못하거나, 구현 복잡성을 피하기 위해 정형성 속성을 의도적으로 생략하며, 이는 노드 수의 지수적 팽창을 초р할 수 있다.

방법론
저자들은 준감소(semi-reduced) Pauli-LIMDD 노드를 완전 감소(fully reduced, 정형) 형태로 변환하기 위해, 특히 고 결정론 규칙을 최적화하는 새로운 알고리즘을 제안한다.

1. 알고리즘 개선:

   • 저자들은 벡터 공간의 교집합과 합집합을 계산하는 방법인 Zassenhaus 절차를 채택하여 고 결정론에 필요한 최소화 문제를 해결한다.
   • 안정자 그룹(stabilizer group)의 교집합과 코셋(coset)을 별도로 계산하는 대신, 바이너리 벡터(Pauli word), 중간 안정자(middle stabilizer), 우측 안정자(right stabilizer)라는 세 개의 레지스터를 가진 "Zassenhaus 행렬"을 구성한다.
   • Pauli-LIM 곱셈 규칙을 사용하여 이 행렬에 가우스 소거법을 수행함으로써, 최소 Pauli word와 그에 대응하는 안정자 생성자(stabilizer generators)를 동시에 찾아낸다.
   • 복잡도 감소:
     • 두 개의 서로 다른 자식을 가진 노드의 경우, 알고리즘은 $O(n^3)$의 최악 복잡도를 유지하지만 오버헤드는 줄어든다.
     • 단일 자식을 가진 노드(DD가 간결성을 달성하는 흔한 사례)의 경우, 문제는 단일 안정자 그룹에 대해 벡터를 최소화하는 문제로 단순화된다. 이는 복잡도를 $O(n^3)$에서 $O(n^2)$로 감소시킨다.

2. 재귀적 안정자 찾기:

   • 저자들은 Zassenhaus 결과를 사용하여 감소된 노드의 안정자 생성 집합을 계산하는 재귀적 알고리즘을 제시한다. 이는 중복된 그룹 교집합 계산을 피하여, 단일 자식 노드에 대한 $O(n^2)$ 케이스를 더욱 최적화한다.

3. 구현 (QolDDer):

   • 이 알고리즘은 C/C++로 작성된 새로운 바닥부터 제작된(from-scratch) 오픈 소스 Pauli-LIMDD 시뮬레이터인 QolDDer에 구현되었다.
   • QolDDer는 핵심 정규화 로직을 위해 별도의 라이브 library인 PauliLim을 포함한다.
   • 구현체는 부동 소수점 스칼라를 구성 가능한 임계값($\delta = 10^{-13}$)으로 처리하고 동등성 검사를 위한 탐색 트리를 사용하여 수치적 정밀도를 처리하는 동시에, 정형성을 유지한다.

주요 결과
저자들은 RandCliff(무작위 Clifford) 및 MQT-Bench 데이터셋을 사용하여 QolDDer를 두 가지 기존 LIMDD 구현체(MQT-LIMDD, LimTDD) 및 QMDD 시뮬레이터(MQT-DDSIM)와 비교 평가하였다.

• Clifford 회로에서의 지수적 가속: RandCliff에서 QolDDer는 QMDD(MQT-DDSIM)에 대해 지수적 가속을 보여준다. 이는 LIMDD가 Clifford 회로의 출력을 다항 공간 내에 표현할 수 있는 반면, QMDD는 결과로 발생하는 고도로 얽힌 상태를 간결하게 표현할 수 없다는 LIMDD의 이론적 이점을 확인시켜 준다.
• 정형성의 영향:
  • QolDDer에서 완전한 정형성(고 결정론)을 활성화하면, Clifford 회로에서 준감소(비정형) 버전과 비교하여 실행 시간이 현저히 빨라지고 노드 수가 급격히 줄어든다.
  • QolDDer는 MQT-LIMDD의 부분적인 정형성 구현으로 인해 많은 인스턴스에서 MQT-LIMDD 구현보다 한 자릿수 더 뛰어난 성능을 보인다.
  • QolDDer는 정형성 보장이 없는 LimTDD보다 Clifford 회로에서 일관되게 더 빠르며, 정형적 병합을 통한 노드 수 감소 덕분에 종종 25배 이상의 차이를 보인다.
• 일반 벤치마크에서의 한계: 광범위한 MQT-Bench 데이터셋에서 정형성의 성능 이점이 보편적인 것은 아니다. 양자 신경망(Quantum Neural Networks), 그로버 알고리즘(Grover's algorithm)과 같은 특정 회로 유형의 경우, LIM이 QMDD보다 더 많은 병합을 제공하지 않으며, 정형성을 유지하기 위한 오버헤드로 인해 QolDDer가 MQT-DDSIM보다 약간 느려진다(상수 배 차이). 그러나 스케일링은 선형적으로 유지된다.

의의 및 주장
본 논문은 LIMDD의 이론적 힘을 실현하는 데 있어 주요 장벽이 효율적이고 완전한 정형 구현의 부재였다고 주장한다. $O(n^2)$ 알고리즘과 견고한 오픈 소스 구현체(QolDDer)를 제공함으로써, 저자들은 다음을 입증한다:

1. LIMDD는 특정 중요 회로 클래스(Clifford 회로)에 대해 QMDD보다 실제로 지수적 이점을 가질 수 있다.
2. 정형성은 필수적이다. 정형성이 없으면 노드 수가 폭발할 수 있으며, 이는 데이터 구조의 이점을 상쇄한다.
3. 이 연구는 양자 설계 작업 및 일반 선형 대수 기반 시스템 분석을 위한 LIMDD 변형체의 발전을 가능하게 한다.

저자들은 일반 벤치마크에 대해 겸허한 태도를 유지하며, LIM이 QMDD보다 추가적인 병합을 제공하지 않는 회로의 경우 정형성 유지를 위한 오버헤드가 정당화되지 않을 수 있음을 언급한다. 향후 연구는 이러한 알고리즘을 더 넓은 XP 그룹으로 확장하고, 회로 동등성 검사나 고전적 선형 대수 문제와 같은 작업에 LIMDD를 적용하는 것을 목표로 한다.