기술 요약: 토너먼트 해법의 양자 쿼리 복잡도

문제 정의

본 논문은 다양한 **토너먼트 해법(tournament solutions)**을 계산하는 데 드는 **양자 쿼리 복잡도(quantum query complexity)**를 조사한다. 토너먼트는 모든 서로 다른 정점 쌍이 정확히 하나의 화살표로 연결된 유향 그래프로, 라운드 로빈 경기나 쌍방 과반수 관계를 모델링한다. 토너먼트 해법은 토너먼트를 비어 있지 않은 "승리" 정점들의 집합으로 매핑한다.

쿼리 모델에서 토너ament는 암시적으로 주어지며, 알고리즘은 에지 $(u, v)$를 쿼리함으로써만 해당 방향을 알 수 있다. 비용은 쿼리의 횟수이다. 이러한 문제들에 대한 고전적 쿼리 복잡도는 흔히 균일한 반면(통상적으로 $\Theta(N^2)$), 본 연구는 양자 알고리즘(중첩 및 그로버 탐색 활용)이 상당한 속도 향상을 달ach할 수 있는지 탐구한다.

연구된 구체적인 해법들은 다음과 같다:

• 콘도르세 승자 (Condorcet Winner): 다른 모든 정점을 이기는 정점.
• 코플랜드 집합 (Copeland Set, $CO(T)$): 최대 외차수(out-degree)를 가진 정점들의 집합.
• 언커버드 집합 (Uncovered Set, $UC(T)$): "킹(kings)"들의 집합 (두 단계 이내에 다른 모든 정점에 도달하는 정점들).
• 스트롱 킹 (Strong King): 모든 $u$가 $v$를 이길 때, $v$가 $u$를 이기는 횟수가 $u$가 $v$를 이기는 횟수보다 많은 정점 $v$ (구체적으로 $p(v,u) > p(u,v)$).
• 톱 사이클 (Top Cycle, $TC(T)$): 유일한 최소 지배 집합 (집합 내의 모든 멤버가 집합 외부의 모든 정점을 이기는 집합).

방법론

저자들은 양자 알고리즘 설계와 하한선(lower-bound) 기법을 혼합하여 사용한다.

1. 하한선 (Adversary Method):

   • 하한선을 증명하기 위한 주요 도구는 앰베인스(Ambainis)의 어드버서리 방법(Theorem 2.13)이다.
   • 이를 적용하기 위해, 저자들은 새로운 약속 문제(promise problem)인 **헤비-로우(Heavy-Row)**를 도입한다. 주어진 $m \times m$ 불리언 행렬에서, 단 하나의 행을 제외한 모든 행의 가중치(weight)가 $k$일 때, 가중치가 $k+1$인 행이 존재하는지 결정하는 문제이다.
   • 저자들은 이전 연구 [14]에서 사용된 합성 정리(composition theorem)를 피하고, 어드버서리 방법을 직접 사용하여 $Q(\text{Heavy-Row}) = \Omega(m^{3/2})$임을 증명한다.
   • 이 문제는 외차수나 구조적 특성(예: 스트롱 킹 여부)이 헤비-로우의 존재 여부에 의존하도록 특정 토너먼트를 구성함으로써 토너먼트 문제로 환원된다.
   • 코플랜드 집합의 경우, 여러 행이 헤비할 수 있는 Heavy-Rows$_k$로 일반화하여 $\Omega(N^2)$ 하한선을 확립한다.
   • 언커버드 집합의 경우, "타이트(tight)"한 행렬과 "결핍된(deficient)" 행렬을 세는 문제를 포함하는 **타이트-카운트(Tight-Count)**를 정의하여 $\Omega(N^{3/2})$ 하한선을 확립한다.

2. 상한선 (Algorithm Design):

   • 톱 사이클: 알고리즘은 먼저 삽입 정렬을 통해 $O(N \log N)$ 쿼리로 **해밀턴 경로(Hamiltonian path)**를 찾는다. 톱 사이클은 이 경로의 접두사(prefix)에 해당한다. 이 접두사의 끝을 찾는 문제는 분할 정복 전략과 양자 최솟값 찾기(Dürr-Høyer)를 결합하여 백 에지(back-edge)를 효율적으로 찾아내는 구간 덮기 문제로 환원된다.
   • 콘도르세 승자: 알고리즘은 킹을 찾고($O(\sqrt{N} \text{polylog } N)$ 알고리즘 [25] 사용), 그 후 그로버 탐색을 수행하여 해당 킹을 이기는 정점이 있는지 확인한다.
   • 스트롱 킹: 모든 최대 외차수 정점이 스트롱 킹이라는 사실로부터 상한선이 즉각적으로 도출되며, 이는 최대 차수 정점을 찾는 $\Theta(N^{3/2})$ 과정을 활용한다.

주요 기여 및 결과

본 논문은 다음과 같은 양자 쿼리 복잡도를 확립한다 (여기서 $N$은 정점의 수이며, $\tilde{O}$는 다항 로그 인자를 숨긴다).

문제	고전적 복잡도	양자 복잡도	핵심 결과
콘도르세 승자	$\Theta(N)$	$\tilde{\Theta}(\sqrt{N})$	상당한 속도 향상; 킹 + 그로버를 통해 발견됨.
톱 사이클	$\Theta(N^2)$	$\tilde{\Theta}(N)$	주요한 속도 향상. 톱 사이클은 세 가지 중첩된 집합($CO \subseteq UC \subseteq TC$) 중 양자적으로 계산하기 가장 "쉬운" 것이다.
최대 외차수 정점	$\Theta(N^2)$	$\Theta(N^{3/2})$	이전 연구 [14]와 일치함; 저자들은 헤비-로우 환원을 통해 자기 완결적인 증명을 제공함.
스트롱 킹	$\Theta(N^2)$	$\Theta(N^{3/2})$	고전 대비 다항식 속도 향상이 있으나, 단일 킹을 찾는 것($\tilde{O}(\sqrt{N})$)보다는 느림.
언커버드 집합 (킹)	$\Theta(N^2)$	$\Omega(N^{3/2}), O(N^2)$	집합 문제와 단일 요소 문제를 구분함. 모든 킹을 찾는 것은 하나를 찾는 것보다 어렵다.
코플랜드 집합	$\Theta(N^2)$	$\Theta(N^2)$	속도 향상 없음. 최대 차수 정점 전체 집합을 계산하는 것은 에지의 상수 비율을 읽어야 하므로 고전적 경계와 일치함.

구체적인 기술적 발견:

• 코플랜드 집합의 어려움: 저자들은 단일 코플랜드 승자(최대 차수 정점)를 찾는 데는 $\Theta(N^{3/2})$가 걸리지만, 그러한 정점들의 전체 집합을 계산하는 데는 $\Theta(N^2)$ 쿼리가 필요함을 보여준다. 이는 톱 사이클에서 최대 차수 정점들보다 더 빠르게 집합이 계산되는 것과 대조적이다.
• 스트롱 킹: 스트롱 킹을 찾는 데는 $\Theta(N^{3/2})$ 쿼리가 필요하다. 이는 고전적인 $\Theta(N^2)$에 비해 다항식 속도 향상이 있는 것이지만, 일반적인 킹을 찾는 것($\tilde{O}(\sqrt{N})$)보다는 현저히 느리다.
• 톱 사이클 알고리즘: 알고리즘은 $O(N \log^2 N)$ 쿼리를 달성한다. 이는 $\Theta(N^2)$ 비트에 대한 OR 함수를 임베딩하여 얻은 하한선 $\Omega(N)$에 의해 로그 인자 차이 내에서 최적이다.
• 대안적 증명: 본 논문은 합성 정리를 우회하여 어드버서리 방법을 통해 헤비-로우 문제로부터 직접 환원함으로써, 최대 차수 정점을 찾는 $\Theta(N^{3/2})$ 경계에 대한 자기 완결적인 증명을 제공한다.

의의 및 주장

본 논문은 토너먼트 해법의 양자 쿼리 복잡도가 고전적인 경우와 달리 균일하지 않다고 주장한다.

• 난이도의 계층 구조: 양자 설정에서 가장 큰 해법 집합(톱 사이클)이 계산하기 가장 쉽고($\tilde{\Theta}(N)$), 가장 작은 집합(코플랜드 집합)이 가장 어렵다($\Theta(N^2)$).
• 집합 vs 요소: 토너먼트 해법 전체를 계산하는 것이 그 해법의 단일 멤버를 찾는 것보다 엄격하게 더 어려울 수 있다는 것이 핵심 주제이다.
  • 킹의 경우: 하나를 찾는 것은 $\tilde{O}(\sqrt{N})$이지만, 전체 집합(언커버드 집합)을 찾는 것은 $\Omega(N^{3/2})$이다.
  • 코플랜드의 경우: 하나를 찾는 것은 $\Theta(N^{3/2})$이지만, 전체 집합을 찾는 것은 $\Theta(N^2)$이다.
• 구조적 통찰: 본 연구는 이러한 문제들의 어려움이 검색(searching)보다는 계수(counting)(차수나 특정 구조의 개수를 결정하는 것)에서 기인한다는 점을 강조한다. 그로버 탐색이 특정 요소를 찾는 데 도움을 줄 수는 있지만, 계수 문제는 종종 높은 복잡도를 유지하거나 입력의 상당 부분을 읽어야 한다.

저자들은 이러한 결과들이 토너먼트 해법을 양자 영역에서 재평가할 필요가 있음을 시사하며, 양자 속도 향상이 해법 집합의 구체적인 정의와 토너먼트의 기저 구조적 특성에 매우 의존적임을 입증한다.