A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

기술 요약: 양자 위상 추정(QPE)을 통한 최대 클리크 및 최소 히팅 셋을 위한 그로버 증폭 오라클

문제 정의
본 논문은 두 가지 근본적인 NP-난해 조합 최적화 문제인 그래프 상의 **최대 클리크 문제(Maximum Clique Problem, MCP)**와 하이퍼그래프 상의 **최소 히팅 셋 문제(Minimum Hitting Set Problem, MHSP)**를 다룹로다. MCP는 그래프 $G$에서 서로 인접한 정점들의 가장 큰 부분집합을 찾는 것이며, MHSP는 하이퍼그래프 $H$의 모든 하이퍼에지를 교차하는 가장 작은 정점 부분집합을 찾는 것입니다. 이 문제들은 계산 생물학에서 사이버 보안에 이르기까지 다양한 분야의 중심에 있습니다.

기존의 양자 접근 방식, 특히 그로버 알고리즘에 기반한 방식은 공간 복잡도(space complexity) 측면에서 상당한 확장성 문제를 겪습니다. MCP를 위한 전통적인 게이트 모델 오라클은 일반적으로 인접성을 명시적으로 확인하거나 에지 정보를 저장하기 위해 $O(N^2)$개의 큐비트(여기서 $N$은 정점의 수)를 필요로 합니다. 하이퍼에지의 수 $M$이 $N$에 대해 지수적($M \in O(2^N)$)일 수 있는 하이퍼그래프의 경우, 하이퍼에지당 하나의 보조 큐비트(ancilla qubit)를 요구하는 표준 방식은 실행 불가능합니다.

방법론
저자들은 **양자 위상 추정(Quantum Phase Estimation, QPE)**과 두 가지 특정 인코딩 연산자인 그래프 인코딩 연산자(Graph Encoding Operator, GEO) 및 **하이퍼그래프 인코딩 연산자(Hypergraph Encoding Operator, HEO)**를 기반으로 한 새로운 그로버 오라클 구성을 제안합니다.

1. MCP를 위한 그래프 인코딩 연산자 (GEO):

   • 에지를 명시적으로 확인하는 대신, 저자들은 여집합 그래프 $\bar{G}$를 활용합니다. 정점 부분집합 $S$가 $G$의 클리크라는 것은 $S$가 $\bar{G}$에서 유도된 부분 그래프의 에지가 0개(즉, 에지가 없음)라는 것과 동치입니다.
   • GEO는 원래 동료 논문 [26]에서 그래프 동형 불변량(graph isomorphism invariant)으로 정의되었으며, $\bar{G}$에 적용됩니다. 이는 정점 부분집합 $S$에 의해 유도되는 에지의 수를 계산하고, 이 카운트를 계산 기저 상태 $|x\rangle$($S$를 나타냄)의 **위상(phase)**에 인코딩합니다.
   • 오라클 구성:
     • 위상 레지스터(Phase Register): GEO에 대한 QPE를 수행하여 에지 수 $|E(\bar{G}_S)|$를 위상 레지스터로 추출합니다.
     • 가중치 레지스터(Weight Register): $-k$로 사전 로드된 별도의 레지스터를 사용하여 부분집합 크기 $|S| \geq k$를 검증합니다. 제어 증가(controlled increment) 연산은 $|x\rangle$의 비트에 따라 이 레지스터를 업데이트합니다.
     • 플래깅(Flagging): 만약 위상 레지스터가 에지가 0임을 나타내고(즉, $S$가 클리크임을 의미), 가중치 레지스터의 최상위 비트(MSB)가 $|S| \geq k$임을 나타내면, 그 상태를 표시하기 위해 위상 플립(phase flip)이 적용됩니다.
   • 공간 효율성: 이 회로는 정점 레지스터에 $N$개의 큐비트를, 위상 레지스터에 $\lceil \log_2 |E(\bar{G})| \rceil + 1$개를, 가중치 레지스터에 $\lceil \log_2 N \rceil + 1$개의 큐비트를 사용합니다. $|E(\bar{G})| \leq N(N-1)/2$이므로, 총 큐비트 수는 $O(N)$입니다.

2. MHSP를 위한 하이퍼그래프 인코딩 연산자 (HEO):

   • HEO는 부분집합 $S$에 의해 커버되는 하이퍼에지의 수를 계산하도록 설계되었습니다. 부분집합이 히팅 셋이 되려면 모든 $M$개의 하이퍼에지를 커버해야 합니다.
   • 메커니즘: 이 연산자는 위상 게이트를 통해 구현된 포함-배제의 원리를 사용합니다.
     • 1단계: 제어되지 않은 위상 게이트(uncontrolled phase gates)가 각 정점의 차수(incident hyperedges의 수)에 비례하는 위상을 더합니다.
     • 2단계: 다중 제어 위상 게이트(multi-controlled phase gates)가 중복 계산된 교집합의 위상을 뺍니다. 구체적으로, 하이퍼에지 $E$에 대해 $S$가 $E$와 $k$개의 정점에서 교차한다면, 이 구성을 통해 순 위상 기여도가 (단순히 $k$가 아니라) 정확히 1개의 커버된 하이퍼에지에 대응하도록 보장합니다.
   • 오라클 구성: GEO와 유사하게, QPE를 사용하여 커버된 하이퍼에지의 수를 추출합니다. 전역 위상 시프트 $-|E(H)|\theta$가 적용되어, 모든 에지를 커버하는 히팅 셋의 경우 순 위상이 0이 되도록 합니다. 가중치 레지스터는 $|S| \leq k$인지 확인합니다.
   • 공간 효율성: HEO는 정점을 위한 $N$개의 큐비트와 $\lceil \log_2 M \rceil$ 크기의 위상 레지스터를 필요로 합니다. $M$이 $N$에 대해 지수적($M \in O(2^N)$)이라 하더라도, $\log(2^N) = N$이므로 총 큐비트 요구량은 $O(N)$으로 유지됩니다.

주요 기여

• 선형 공간 복잡도: 본 논문의 주요 기여는 그로버 기반 MCP 및 MHSP 오라클의 큐비트 요구량을 $O(N^2)$(또는 하이퍼그래프의 경우 $O(M)$)에서 $O(N)$으로 줄인 것입니다. 이는 구조적 정보(에지/하이퍼에지 카운트)를 명시적인 저장이나 확인을 위한 보조 큐비트 대신 상태의 위상에 인코딩함으로써 달성되었습니다.
• 하이퍼그래프에 대한 확장성: HEO를 사용하면 선형 큐비트만을 사용하여 지수적인 수의 하이퍼에지($M \in O(2^N)$)를 가진 하이퍼그래프에 대한 MHSP를 해결할 수 있으며, 이는 이전에는 달성되지 못한 성과입니다.
• 불리언 함수의 쌍대화(Dualization): 본 논문은 균등 중첩(uniform superposition) 하에서 HEO의 QPE 레지스터를 측정하는 것이 히팅 셋의 개수를 근사할 수 있음을 보여줍니다. 양의 비가약적 디스정규형(PIDNF)으로 표현된 양의 불리언 함수에 대한 쌍대화 문제를 직접 해결하는 핵심 단계인 만큼, 이는 쌍대화 문제를 다루는 양자적 접근법을 제공합니다.
• 게이트 복잡도 분석: 저자들은 상세한 분석을 통해 공간 복잡도는 선형이지만, 오라클 호출당 게이트 복잡도는 그래프의 경우 $O(|E(\bar{G})| \log |E(\bar{G})| + N \log N)$이고 하이퍼그래프의 경우 $O(MN^2 \log M)$임을 보여줍니다. 또한 밀집 그래프(dense graph) $G$의 경우 그 여집합 $\bar{G}$는 희소(sparse)하므로 GEO가 실제적으로 효율적임을 언급합니다.

결과 및 검증

• 수치 시뮬레이션: 저자들은 Qiskit과 AerSimulator를 사용하여 전체 그로버 알고리즘을 구현했습니다.
  • 그래프: $N=5$에서 $N=10$ 사이의 그래프에 대해 테스트했습니다. 시뮬레이션 결과, "계산-표시-취소(compute-mark-uncompute)" 시퀀스가 타겟 클리크 상태를 올바르게 증폭하여, 이론적으로 최적인 반복 횟수에서 99.5%~100%의 성공 확률을 달성함을 확인했습니다.
  • 하이퍼그래프: HEO 구성이 커버된 하이퍼에지의 수를 올바르게 인코딩하며, 위상 상쇄가 예측대로 작동하여 히팅 셋을 식별함을 검증했습니다.
• 비교: 본 논문은 자신의 $O(N)$ 공간 복잡도를 $O(N^2)$ 큐비트를 요구하는 기존 알고리즘들(Haverly 및 López, Sanyal 등, Han 등)과 대조합니다. 저자들은 이 접근 방식이 공간을 위상 정밀도와 회로 깊이로 트레이드오프(trade-off)하는 방식이지만, 현재 양자 하드웨어의 주요 병목 현상인 큐비트 수 측면에서 상당한 이점을 제공한다고 설명합니다.

의의 및 주장
본 논문은 제안된 알고리즘이 공간 계산 복잡도 측면에서 최대 클리크 및 최소 히팅 셋 문제를 위한 기존의 모든 그로버 기반 양자 알고리즘보다 우수함을 주장합니다.

• 단 $O(N)$개의 큐비트만을 요구함으로써, 이 방법은 더 큰 $N$에 대해서도 양자 시뮬레이터 및 잠재적인 미래 하드웨어에서 이러한 문제들을 다룰 수 있게 합니다.
• 선형 큐비트를 사용하여 지수적인 에지를 가진 하이퍼그래프를 처리할 수 있는 능력은 독보적인 역량으로 강조되며, 이는 양자 환경에서 양의 불리언 함수에 대한 쌍대화 문제를 해결하는 핵심 단계인 히팅 셋의 개수 근사를 가능하게 합니다.
• 저자들은 이 접근 방식이 높은 정밀도의 위상 회전(특히 $M \in O(2^N)$인 하이퍼그래프의 경우)에 의존하며, 이는 큐비트 수에서 게이트 정밀도와 회로 깊이로 복잡성의 부담을 옮기는 것임을 겸허히 인정하며, 이는 결함 허용(fault-tolerant) 양자 컴퓨팅과 관련된 트레이드오프입니다.

이 연구는 MCP가 여전히 NP-hard이므로 클래식 알고리즘에 대한 초다항적(super-polynomial) 가속을 주장하는 것이 아니라, 그로버 반복을 통한 클래식 전수 조사(exhaustive search) 대비 이차적(quadratic) 가속을 훨씬 더 효율적인 자원 점유율로 달성하는 것을 목표로 합니다.