기술 요약: 비변분형 QWOA를 이용한 최근 문자열 문제의 양자 솔루션

1. 문제 정의

**최근 문자열 문제(Closest String Problem, CSP)**는 조합 최적화 문제로, NP-Hard로 분류된다. $m$개의 참조 문자열 세트가 주어졌을 때, 각 문자열의 길이는 $n$이고 알파벳 크기는 $k$이다. 목표는 참조 세트에 대한 최대 해밍 거리를 최소화하는 길이 $n$의 해 문자열 $s$를 찾는 것이다. 비용 함수는 다음과 같이 정의된다:
$$f(s) = \max_{i=1,2,...,m} d_H(s, s_i)$$
여기서 $d_H$는 해밍 거리이다.

고전적으로 이 문제를 정확하게 푸는 것은 매우 큰 $n$에 대해 계산적으로 불가능하다. 전수 조사(Exhaustive search)는 $O(k^n)$의 규모로 확장되며, 단일 후보에 대한 비용 행렬을 계산하는 데 $O(mn)$의 비교가 필요하므로, 총 고전적 복잡도는$O(k^n mn)$이 된다. 매개변수화된 고전 알고리즘들이 존재하지만, 이들은 여전히 최대 해밍 거리$d$에 대해 지수적 확장을 보인다. CSP는 생물정보학(예: 단백질 분자의 공통 구조 또는 변이된 바이러스 균주 식별), 통신(손상된 복사본으로부터 신호 재구성), 코드 교정 등에서 중요한 응용 가치를 지닌다.

2. 방법론: 비변분형 QWOA (NV-QWOA)

저자들은 **비변분형 양자 워크 최적화 알고리즘(Non-Variational Quantum Walk Optimization Algorithm, NV-QWOA)**을 사용하여 CSP에 대한 엔드 투 엔드 양자 구현을 제안한다. 변분 양자 알고리즘(VQA)인 QAOA와 달리, 매개변수를 튜닝하기 위해 고전적 최적화 루프에 의존하는 것과 달리, NV-QWOA는 문제 구조에 의해 결정되는 고정된 하이퍼파라미터 세트를 사용하여 변분법적 방법과 관련된 베런 플레이토(barren plateau) 문제 및 고전적 오버헤드를 피한다.

알고리즘 단계

알고리즘은 세 가지 주요 구성 요소로 이루어진 $p$번의 반복을 통해 양자 회로에서 작동한다:

1. 비용 평가 (위상 분리, Phase Separation):
   • 알고리즘은 후보 해 문자열의 중첩 상태와 모든 $m$개의 참조 문자열 사이의 해밍 거리를 계산한다.
   • 양자 푸리에 가산(Quantum Fourier Addition, QFA)과 양자 상태 비교기를 포함하는 결정론적 양자 회로 아키텍처를 사용하여 각 후보에 대한 최대 해밍 거리(비용)를 결정한다.
   • 비용에 비례하는 위상 변화(phase shift)가 해 레지스터에 적용된다. 저자들은 결정론적으로 정의된 $\gamma = \frac{\pi}{2(n+1)}$인 수정된 위상 분리 파라미터 $\gamma$ 처방을 도입한다. 이는 인스턴스별 최적화의 필요성을 없애고, 비용과 위상 사이의 상관관계를 약화시킬 수 있는 $2\pi$ 모듈로 위상 래핑(phase wrapping) 문제를 완화한다.
2. 믹싱 (양자 워크, Mixing):
   • 믹싱 그래프 상에서 연속 시간 양자 워크(Continuous Time Quantum Walk, CTQW)가 수행된다. CSP의 경우, 이 그래프는 노드가 해 문자열을 나타내고 에지가 해밍 거리가 1인 문자열들을 연결하는 **해밍 그래프(Hamming graph)**이다.
   • 이 믹싱 유니터리는 인접한 상태들 사이에서 진폭을 재분배하여, 유리한(낮은) 위상을 가진 상태들을 증폭시킨다.
3. 반복 (Iteration):
   • 단계 1과 2가 $p$번 반복된다. 알고리즘은 최적 또는 근사 최적해의 측정 확률을 증폭시키고 비최적 상태를 억제한다.

회로 구현 세부 사항

• 게이트 수준 인코딩: 구현에는 문제를 1-큐비트 및 2-큐비트 게이트로 변환하기 위한 Qiskit이 사용된다.
• 레지스터: 회로는 해 레지스터, 참조 레지스터, 문자 레지스터($k>2$인 경우), QFT 레지스터, 승자(winner) 레지스터, 승자 슬롯 레지스터, 위상 타겟 레지스터 등 7개의 양자 레지스터를 활용한다.
• 언컴퓨테이션 (Uncomputation): 비용 계산에 사용된 보조(ancilla) 레지스터들은 믹싱 단계와의 간섭을 방지하기 위해 헤르미안 켤레 연산을 통해 언컴퓨트(uncompute)되어 디텐글(disentangle)된다.
• 최적화: 저자들은 효율적인 OR 게이트 구현을 QFA와 통합하여 해밍 거리 계산을 최적화함으로써 추가적인 보조 큐비트의 필요성을 줄였다.

3. 주요 기여

• 명시적 게이트 수준 구현: 논문은 참조 문자열의 인코딩, 비용 평가 및 NV-QWOA 안사트(ansatz)를 포함하여 임의의 CSP 인스턴스를 양자 회로로 변환하는 완전하고 자동화된 워크플로우를 제공한다.
• 결정론적 위상 스케일링: 문제 크기에 의존하는 새로운 $\gamma$ 처방이 도입되었다. 이는 $\gamma$에 대한 휴리스틱 추정이나 고전적 최적화의 필요성을 제거하여 알고리즘이 진정으로 비변분형으로 유지되도록 보장한다.
• 자원 복잡도 분석:
  • 큐비트 복잡도: $O(nm \log k)$.
  • 회로 깊이: 고정된 알파벳 크기에 대해 $O(pm \log^2 n + pn \log n)$.
  • 이러한 추정치는 지수적인 고전 탐색 공간과 비교하여 유리한 스케일링 궤적을 나타낸다.
• 효율적인 Max 함수 회로: 저자들은 비이차적(non-quadratic) 특성 때문에 양자 회로에서 까다로운 작업인 모든 참조 세트에 대한 최대 해밍 거리를 결정론적으로 찾는 특정 회로 아키텍처(CCNOT 및 CSwap 게이트 사용)를 설계했다.

4. 결과

저자들은 Qiskit-Aer를 통한 고전적 상태 벡터 시뮬레이션을 사용하여 접근 방식을 검증했다.

• 시뮬레이션 파라미터: 실험은 문자열 길이 $n \in \{3, 4, 5, 6\}$, $m=2$개의 참조 문자열, 그리고 이진 알파벳($k=2$)에 대해 수행되었다. 이는 15~26개의 큐비트에 해당하는 회로이다.
• 성능:
  • $p=30$회 반복 후, 알고리즘은 최적 솔루션 세트(서브쉘 0)를 일관되게 증폭시켰다.
  • 최적 솔루션을 측정할 확률은 테스트된 모든 인스턴스에서 **80–90%**에 도달했다.
  • 근사 최적 솔루션인 서브쉘 1은 10–20%의 확률을 유지했으며, 다른 모든 서브쉘은 거의 0에 가까운 확률로 수렴했다.
  • 결정론적 $\gamma$ 처방은 비용 표준 편차 스케일링 없이도 효과적임을 입증했으며, 이는 작은 규모에서 다소 해로울 수 있음이 발견되었다.
• 관찰: 결과는 NV-QWOA가 고전적 파라미터 튜닝 없이도 균등 중첩 상태로부터 고품질 후보에 측정 확률을 효과적으로 집중시킬 수 있음을 보여준다.

5. 의의 및 주장

본 논문은 양자 하드웨어에서 최근 문자열 문제를 해결하기 위한 기초적인 프레임워크를 제공한다고 주장한다. 그 의의는 다음과 같다:

• 적용 가능성 입증: MaxCut 및 k-means와 같은 문제에서 테스트되었던 NV-QWOA가 NP-Hard인 CSP에도 적용 가능함을 검증한다.
• 하드웨어 준비성: 명시적인 게이트 수준 구현과 자원 추정치를 제공함으로써, 이 연구는 결함 허용(fault-tolerant) 양자 컴퓨터를 위한 향후 실험의 토대를 마련한다.
• 벤치마킹 잠재력: 저자들은 이 작업을 양자 알고리즘을 고전 솔버와 벤치마킹하기 위한 기초로 설정한다. 저자들은 완전한 "엔드 투 엔드 양자 가속(end-to-end quantum speedup)"을 입증하려면 반복 횟수($p$), 측정 반복, 고전적 오버헤드에 대한 추가적인 분석이 필요하며, 이는 본 연구에서 완전히 해결되지 않았음을 명시적으로 밝힌다.
• 미래 확장성: 저자들은 이 프레임워크가 최근 부분 문자열 문제(Closest Substring Problem)(길이가 $L$인 더 긴 참조 문자열 내에서 길이 $n$인 부분 문자열을 찾는 문제)로 확장될 가능성이 있다고 언급했으나, 현재 연구에서는 조사되지 않았다.

논문은 알고리즘이 시뮬레이션에서 강력한 증폭을 보여주기는 하지만, 실제적인 양자 우위로의 전환을 위해서는 스케일링 법칙 및 하드웨어 제약에 대한 추가적인 조사가 필요함을 인정하며 신중한 어조를 유지한다.