A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

기술 요약: 이산 최적화를 위한 양자 비구조적 탐색 알고리즘

문제 정의
본 논문은 변수가 이진수(binary)이며 미분을 정의할 수 없는 이산 최적화 문제, 특히 조합 최적화(combinatorial optimisation) 문제를 해결하는 과제를 다룹니다. 경사 하강법 기반의 방법들은 연속 변수에는 효과적이지만, 종종 NP-난해(NP-hard)인 이산 공간에서는 실패합니다. QUBO(Quadratic Unconstrained Binary Optimisation) 프레임워크와 같은 기존의 양자 접근 방식은 1차 및 2차 항만을 포함하는 목적 함수로 제한됩니다. 또한, 현재의 많은 양자 최적화 알고리즘(예: 변분 양자 알고리즘, VQA)은 노이즈에 취속되거나 깊은 회로를 요구할 수 있는 하이브리드 고전-양자 루프에 의존합니다. 저자들은 QUBO의 이차 한계를 넘어서는 고차 항을 포함할 수 있는 일반적인 이산 함수 $f(x)$의 극값(extrema) 또는 근(roots)을 찾는 방법을 제안합니다.

방법론: QSERA 알고리즘
저자들은 그로버(Grover) 알고리즘에 기반한 양자 탐색 알고리즘(QSA) 계열의 일원인 **양자 극값 및 근 탐색 알고리즘(Quantum Search for Extrema and Roots Algorithm, QSERA)**을 소개합니다. 방법론은 두 가지 주요 단계로 진행됩니다:

1. 오라클 구성 ($f(x) \to u(z)$):
   첫 번째 단계는 극값(또는 근)을 찾는 조건 $f(x^*) \approx f^*$를 이진 문자열 $z^*$에 대한 비구조적 탐색 문제로 매핑하는 것입니다.

   • 재스케일링(Rescaling): 목적 함수 $f(x)$를 함수 $g(x) \in [0, 1]$로 재스케일링합니다. 최대화의 경우 $g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$이고, 최소화의 경우 $g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$이며, 근 찾기의 경우 특정 변환이 적용됩니다. 이를 위해서는 전역 최소값($f_{min}$)과 최대값($f_{max}$)에 대한 사전 지식 또는 추정치가 필요합니다.
   • 증폭(Amplification): $u(z^*) = 1$이고 $u(z \neq z^*) = 0$인 이진 오라클 $u(z)$를 만들기 위해, 함수 $g(x)$를 큰 거듭제곱 $n$으로 승수 처리합니다 (즉, $u_n(z) \equiv g(x)^n$). $n \to \infty$일 때, $u_n(z)$는 이상적인 오라클에 도달합니다.
   • 일반화: 본 논문은 $f(x)$가 차수 $K$까지의 일반적인 다항식(식 10)이 될 수 있음을 명시하며, 이는 표준 QUBO 형태보다 더 복잡한 목적 함수를 허용합니다.
   • 게이트 구현: 저자들은 오라클을 위한 양자 회로를 유도합니다. 이진 변수에 대응하는 자기 수반 연산자(self-adjoint operators) $B_k$를 정의하고, $G|z\rangle = g(x)|z\rangle$를 만족하는 유니터리 연산자 $G$를 구성합니다. 그 후 오라클 연산자 $Q^*$를 $e^{i\pi G^n}$으로 정의합니다. 이는 각 항의 차수(0차, 1차, 2차 등)에 따른 유니터리 연산자 $Q^*_j$의 곱으로 분해되며, 보조 큐비트(ancilla qubits)와 위상 변화 게이트를 사용하여 구현됩니다.

2. 탐색 실행:
   오라클 $Q^*$가 구성되면, 알고리즘은 그로버 확산 연산자($Q_+$)와 오라클($Q^*$)을 반복 루프 내에서 사용합니다. 상태는 균등 중첩(uniform superposition) 상태로 초기화되며, 타겟 상태 $|z^*\rangle$의 진폭을 증폭하기 위해 $(Q_+ Q^*)$ 연산자를 $m_{opt} \approx (\pi\sqrt{N} - 2)/4$번 적용합니다.

주요 기여

• QUBO를 넘어선 일반화: 이차 형식에 국한된 많은 양자 최적화 방법과 달리, QSERA는 고차 항(3차, 4차 등)을 가진 목적 함수를 처리할 수 있어 더 넓은 범위의 조합 문제에 적용 가능합니다.
• 명시적 회로 구성: 본 논문은 회로 파라미터에 필요한 계수의 재귀적 계산을 포함하여, 임의의 다항식 차수에 대한 양자 오라클 게이트를 구축하기 위한 상세한 수학적 유도를 제공합니다.
• 근사적 경계 처리: 저자들은 $f_{min}$과 $f_{max}$를 정확히 알지 못하는 시나리오를 분석합니다. 이들은 알고리즘이 추정치를 사용하더라도 여전히 작동할 수 있음을 입증하며, 정확한 최적값을 찾을 확률은 선택된 파라미터 $n$의 값에 달려 있음을 보여줍니다. $n$이 너무 크면 오라클 신호가 사라질 수 있고, 너무 작으면 신호가 충분히 구별되지 않습니다. 이러한 요인들 사이의 균형을 맞추기 위한 최적의 $n$이 존재합니다.

결과: 포트폴리오 최적화 사례 연구
저자들은 $N_a = 4$개의 자산에 대해 $N=16$개의 가능한 포트폴리오가 존재하는 포트폴리오 최적화 문제를 사용하여 QSERA를 검증했습니다.

• 설정: 목표는 벤치마크 수익률과 변동성으로부터의 거리를 최소화하는 2개의 자산 포트폴리오를 찾는 것이었습니다. 목적 함수는 4차 항까지 포함되었습니다.
• 구현: 포트폴리오 상태를 위한 4개의 큐비트, AND 연산을 위한 2개의 보조 큐비트, 그리고 위상 추적을 위한 1개의 보조 큐비트를 사용하여 양자 회로를 조립했습니다.
• 성능:
  • 최적의 그로버 반복 횟수($m_{opt} = 2$)와 신중하게 선택된 $n \approx 24$의 거듭제곱을 사용했을 때, 알고리즘은 가장 높은 확률로 최적의 포트폴리오(상태 $|1001\rangle$)를 성공적으로 식별했습니다.
  • 두 번째로 좋은 포트폴리오($|0101\rangle$) 역시 상대적으로 높은 확률을 보였는데, 이는 알고리즘이 추정된 경계에 가장 가까운 솔루션을 찾았음을 반영합니다.
  • 본 연구는 $f_{min}$과 $f_{max}$가 정확한 값이 아닌 추정치인 경우, 진정한 최적값을 측정할 확률이 1보다 작으므로, 최적해와 준최적해를 구별하기 위해 여러 번의 "샷(shots)"(반복 실행)이 필요함을 확인했습니다.
  • 거듭제곱 $n$과 성공 확률 사이의 관계를 시각화하여, 중간 $n$ 값에서 피크 확률이 나타나며 $n$이 너무 크거나(신호 억제) 너무 작을 경우(식별력 부족) 성능이 저하됨을 보여주었습니다.

의의 및 주장
본 논문은 QSERA가 이산 함수의 극값 또는 근을 찾기 위해 고전적 브루트 포스(brute-force) 탐색에 대해 이차적 가속(quadratic speed-up, $O(\sqrt{N})$)을 제공한다고 주장합니다. 이 알고리즘의 주요 의의는 다음과 같습니다:

1. 표준 QUBO 정식화와 호환되지 않는 고차 목적 함수를 해결할 수 있습니다.
2. VQA와 달리 하이브리드 고전-양자 파라미터 최적화 루프를 필요로 하지 않고 단일 샷 양자 실행을 통해 작동합니다(단, 경계가 근사적인 경우 통계적 신뢰를 위해 여러 번의 샷이 필요할 수 있음).
3. 경사 기반 방법이 실패할 수 있는 "노이즈가 많거나" 경사가 급격한 연속 함수(이산화 후)를 잠재적으로 다룰 수 있습니다. 다만, 저자들은 구조적 탐색이 일반적으로 연속 변수에 더 효율적이라고 언급했습니다.

저자들은 결론적으로, 알고리즘이 보장된 성공을 위해 함수의 경계에 대한 지식을 필요로 하지만, 현재의 QUBO 기반 접근 방식의 능력을 넘어서는 목적 함수 구조를 가진 이산 최적화 문제에 있어 견고한 도구로 남을 것이라고 밝힙了.