기술 요약: 양자 최적화를 위한 회전 인코딩(Rotational Encoding)

문제 정의

그로버 알고리즘(Grover's algorithm)과 같은 양자 탐색 알고리즘은 제약 충족 문제(CSP) 및 조합 최적화에 있어 계산적 이점을 제공한다. 그러나 이들의 실용성은 문제 특화형 오라클(oracle)을 구축하는 비용에 의해 크게 제약을 받는다. 전통적인 최적화 방식에서 오라클은 불리언(Boolean) 기반이며, 목적 함수 값을 이진수로 명시적으로 저장하기 위해 다중 큐비트 레지스터에 의존한다. 이러한 값들은 가변적인 임계값(threshold)과 비교하기 위해 산술 연산자(예: 제어 증가기/controlled-incrementers)와 비교기(comparator)를 사용한다.

이러한 전통적인 방식은 다음과 같은 상당한 오버헤드를 발생시킨다:

1. 자원 집약성: 여러 개의 다중 큐비트 레지스터(목적 함수 값을 위한 것 하나, 임계값 값을 위한 것 하나)와 수많은 보조 큐비트(ancilla qubits)가 필요하다.
2. 회로 깊이 및 비용: 산술 및 비교 회로가 많은 가역 게이트(reversible gates)로 구성되어, 높은 게이트 수, 깊은 회로 깊이, 그리고 결맞음 해제(decoherence)에 대한 높은 취약성을 초래한다.
3. 반복 실행: 불리언 오라클은 유효한 해를 비용에 따라 순위화할 수 없으므로, 최적화를 위해서는 반복적으로 업데이트된 임계값을 사용하여 탐색 알고리즘을 반복 실행해야 하며, 이는 실행 시간을 더욱 증가시킨다.

본 논문은 이러한 비용을 줄이기 위해 목적 함수 정보를 양자 연산에 직접 포함시키는 대안적 표현 방식의 필요성을 다룬다.

방법론: 각도 회전 카운터(Angular Rotational Counter, ARC)

저자들은 목적 함수를 다중 큐비트 레지스터 상의 이진 값이 아니라, 단일 큐비트 레지스터 상의 누적된 양자 회전 합으로 인코딩하는 회로 설계인 **각도 회전 카운터(ARC)**를 소개한다.

핵심 메커니즘

ARC는 다음과 같이 불리언 함수들의 가중치 합으로 분해될 수 있는 목적 함수 $C(x)$를 위해 설계되었다:
$$C(x) = \sum_{i=1}^{m} w_i f_i(x)$$
여기서 $w_i \geq 0$는 가중치이고 $f_i(x)$는 불리언 함수이다.

회로는 다음과 같이 작동한다:

1. 입력: 후보 해 $x$가 처리된다.
2. 불리언 평가: 각 항 $f_i(x)$가 제어 큐비트(control qubit) 상에서 계산된다.
3. 회전 인코딩: 만약 $f_i(x) = 1$이면, 제어 회전 게이트(구체적으로 $RX$)가 출력 큐비트에 $\frac{\pi}{K} w_i$의 각도로 회전을 적용한다. 만약 $f_i(x) = 0$이면, 회전은 일어나지 않는다.
4. 누적: 출력 큐비트에 적용되는 총 회전 각도는 목적 함수 값에 비례한다: $\theta = \frac{\pi}{K} C(x)$.

수학적 성질

논문은 출력 큐비트의 측정 확률이 목적 함수 $C(x)$와 단조 관계에 있음을 입증한다:

• 최대화(Maximization): 출력 큐비트를 $|0\rangle$로 초기화하면, $C(x)$가 증가함에 따라 $|1\rangle$을 측정할 확률이 증가한다 (구간 $(0, K)$ 내에서).
• 최소화(Minimization): $|1\rangle$로 초기화하면, $C(x)$가 증가함에 따라 $|1\rangle$을 측정할 확률이 감소한다.
• 제약 조건: $K$는 해당 범위 내에서 단조성을 보장하기 위해 최대 가능한 목적 함수 값보다 크거나 같아야 한다.

적용: 상태 할당(State Assignment)

저자들은 유한 오토마타의 구조적 오토마타 합성(structural automata synthesis)의 근본적인 문제인 상태 할당 문제에 ARC를 적용한다. 목표는 비용 함수를 최소화하도록 상태 인코딩에 고유한 이진 인코딩을 할당하는 것이다.

• 비용 함수: 상태 인코딩 간의 가중 해밍 거리(weighted Hamming distance)로, 이는 이차 할당 문제(quadratic assignment problem)의 특수한 경우이다.
• 오라클 구성: 오라클은 인코딩 체커(고유한 상태를 보장하기 위함)와 ARC 기반 비용 계산기를 포함한다. ARC는 전통적인 산술 카운터와 비교기를 대체한다.
• 알로리즘: 오라클은 그로버 탐색 알고리즘에 통합된다. 알고리즘은 구성된 오라클을 사용하여 그로버 탐색을 한 번 실행한다. 이후 입력 큐비트들이 측정되며, 측정 확률이 높은 순서대로 $r \geq 1$개의 해가 선택된다. 결정적으로, 선택된 해들은 유효성과 최적성을 검증하기 위해 반드시 여전히 체크되어야 한다. 이는 측정 확률이 비용의 경향성을 나타내기는 하지만, 사후 검증 과정 없이 단 한 번의 실행만으로 유효한 해를 보장하지는 않기 때문이다.

주요 기여

1. 회전 인코딩 프레임워크: 분해 가능한 목적 함수를 명시적인 이진 인코딩 대신 누적된 양자 회전을 통해 표현하는 방법으로서 ARC를 도입하였다.
2. 수학적 정식화: ARC가 목적 함수를 회전적으로 인코딩하며, 출력 큐비트의 측정 확률이 목적 함수 값에 단조 의존함을 입증하여, 반복적인 임계값 업데이트 없이 직접적인 최적화를 가능하게 함을 증명하였다.
3. 상태 할당을 위한 오라클 설계: 가중 해밍 거리 비용 함수를 사용하는 상태 할당 문제를 위한 특정 오라클을 구축하여, ARC의 중요한 조합 최적화 문제에 대한 적용 가능성을 입증하였다.
4. 종합적 평가: 26개의 벤치마크에 대해 ARC 기반 오라클을 기존의 불리언 기반 오라클과 비교 분석하였다.

실험 결과

저자들은 LGSynth'91 라이브러리의 26개 유한 상태 머신 벤치마크를 대상으로 ARC 오라클을 대응하는 불리언 기반 오라클과 평가하였다. 회로는 Qiskit(레벨 3 최적화)을 사용하여 네이티브 게이트(CZ, RX, RZ, $\sqrt{X}$, X)로 트랜스파일되었다.

성능 지표 (산술 평균 감소율):

• 큐비트 수: 20.8% 감소 (3.9%에서 45.2% 사이). 이는 비용과 임계값을 위한 다중 큐비트 레지스터를 단일 큐비트 레지스터로 대체한 데 기인한다.
• 게이트 수: 89.3% 감소 (63.8%에서 99.5% 사이).
• 회로 깊이: 92.4% 감소 (72.8%에서 99.7% 사이).
• 트랜스파일링 양자 비용(TQC): 90.6% 감소 (67.4%에서 99.6% 사이).

게이트 수와 깊이의 상당한 감소는 주로 비용이 많이 드는 제어 증가기(controlled-incrementer) 게이트와 비교기를 ARC 설계의 제어 회전(controlled-rotation) 게이트로 대체했기 때문이다.

의의 및 주장

본 논문은 ARC가 평가된 벤치마크에서 회로 자원 비용을 대폭 감소시킨다고 주장하며, 회전 인코딩이 명시적인 이진 인코딩에 대한 유망한 대안임을 입증한다.

• 자원 효율성: 이 접근 방식은 큐비트, 게이트 및 깊이 요구 사항을 크게 낮추며, 이는 제한된 결맞음 시간과 연결성을 가진 근접 미래 양자 장치(NISQ)에 매우 중요하다.
• 알고리즘 구조: 비용을 확률 진폭에 직접 인코딩함으로써 단일 실행 내에서 최적화를 가능하게 하며, 불리언 오라클에서 요구되는 반복적인 임계값 업데이트를 제거한다. 알고리즘은 측정 확률에 따라 후보 해를 선택한 후, 검증 단계를 거쳐 유효성을 확인한다.
• 확장성: 이론적 분석에 따르면 ARC 비용 계산기의 시간 복잡도는 $O(n^2 \log n)$이며, 이는 이전의 불리언 기반 상태 할당 방식에서 관찰된 지수적 스케일링보다 훨씬 낮다.

한계 및 겸손한 태도:
저자들은 자신들의 결과가 회로 자원 효율성 측면에서의 상당한 개선을 보여주기는 하지만, 이것이 물리적 실행 시간이나 점근적 양자 속도 향상(asymptotic quantum speedup)을 자체적으로 입증하는 것은 아님을 명시적으로 밝히고 있다. 이들의 성과는 노이즈나 오류 수정에 의존하는 물리적 하드웨어상의 실행 시간보다는 회로 합성 비용(큐비트, 게이트, 깊이) 측면에서 프레임화되어 있다. 또한, 현재의 적용 가능성은 분해 가능한 목적 함수(불리언 함수의 가중치 합)에 대해 입증되었으나, 저자들은 이 프레임워크가 다른 문제 클래스로 확장될 수 있음을 시사한다.