Exhaustive and feasible parametrisation with applications to the travelling salesperson problem

이 논문은 군론(group theory)의 개념을 활용하여 제약 조건이 있는 조합 최적화 문제에서 모든 가능한 해를 확실하게 도달할 수 있으면서도 불가능한 해는 배제하는 '철저하게 매개변수화된(exhaustively parametrised) 실행 가능성 준수 양자 회로' 설계법을 제안하고, 이를 외판원 문제(TSP)에 적용하여 그 효용성을 입증했습니다.

핵심

1. 문제의 배경: "완벽한 배달 경로 찾기" (TSP)

여러분에게 9개의 도시를 방문해야 하는 배달원이 있다고 상상해 보세요. 모든 도시를 딱 한 번씩만 들러서 다시 출발지로 돌아와야 하는데, **"가장 짧은 거리"**로 움직이는 경로를 찾아야 합니다. 도시가 조금만 늘어나도 가능한 경로의 수가 폭발적으로 많아져서, 슈퍼컴퓨터로도 계산하기 매우 힘든 '악마의 문제'가 됩니다.

2. 기존 방식의 한계: "안개 속에서 보물찾기" (QAOA)

지금까지 과학자들이 양자 컴퓨터로 이 문제를 풀려고 썼던 방식(QAOA)은 마치 **"짙은 안개 속에서 보물(최적의 경로)을 찾는 것"**과 같았습니다.

양자 컴퓨터의 특성을 이용해 여러 경로를 동시에 탐색하긴 하지만, 안개가 너무 짙어서 우리가 찾는 보물이 정확히 어디 있는지 알기 어렵습니다. 운이 좋으면 찾겠지만, "이 버튼을 누르면 반드시 보물이 나온다"라고 장담할 수 없는 '확률적인' 방식이었죠.

3. 이 논문의 핵심 아이디어: "모든 방을 다 열 수 있는 마스터키"

이 논문의 저자들은 이 문제를 완전히 다르게 접근했습니다. 그들은 **"안개를 걷어내는 대신, 모든 정답을 다 열 수 있는 마스터키 세트를 만들자!"**라고 제안합니다.

이들이 만든 새로운 방식의 특징은 두 가지입니다:

1. "정답만 골라내기" (Feasibility-respecting): 배달 경로를 찾는데, 갑자기 도시를 두 번 방문하거나 길을 잃는 '말도 안 되는 경로'는 아예 쳐다보지도 않습니다. 오직 '가능한 경로'들만 다룹니다.
2. "반드시 정답에 도달하기" (Exhaustive): 이 마스터키(양자 회로)는 어떤 값을 입력하든, 이론적으로 모든 가능한 정답 경로를 단 한 번의 시도로 정확하게 만들어낼 수 있습니다. 즉, "운 좋으면 찾는다"가 아니라 "이 키를 돌리면 반드시 그 방(정답)이 열린다"는 뜻입니다.

4. 어떻게 만들었나? : "레고 블록과 수학적 마법" (Group Theory)

저자들은 수학의 **'군론(Group Theory)'**이라는 도구를 사용했습니다.

비유하자면, 모든 도시의 경로를 **'레고 성'**이라고 합시다. 이 성을 만드는 방법은 수만 가지지만, 아주 기본적인 **'레고 블록 몇 개(Generating Sequence)'**만 있으면 어떤 모양의 성이든 조립할 수 있습니다.

저자들은 이 '기본 블록'을 수학적으로 찾아냈습니다.

• 버블 정렬 방식: 아주 단순한 블록들을 엄청나게 많이 써서 모든 경로를 만드는 방법 (블록이 너무 많음).
• 이진 삽입 방식: 훨씬 적은 수의 똑똑한 블록만 사용해서 효율적으로 모든 경로를 만드는 방법 (이게 훨씬 똑똑한 방법입니다).

5. 결론: "이론은 완벽하지만, 연습이 더 필요해!"

저자들은 실제로 9개 도시 문제를 가지고 실험해 보았습니다. 결과는 놀라웠습니다. 기존 방식보다 훨씬 더 좋은 경로를 찾아냈거든요!

하지만 저자들은 겸손하게 덧붙입니다. "키(회로)를 만드는 법은 알아냈지만, 그 키의 수많은 구멍 중 어떤 구멍을 돌려야 보물이 나오는지(파라미터 최적화)를 찾는 것은 여전히 어려운 숙제입니다."

즉, **"모든 문을 열 수 있는 완벽한 마스터키 세트를 발명했지만, 그 키를 어떻게 돌려야 보물 상자가 열리는지 알아내는 연습은 계속해야 한다"**는 것이 이 논문의 결론입니다.

---

요약하자면:
이 논문은 양자 컴퓨터가 복잡한 문제를 풀 때, **"정답이 아닌 길은 아예 가지 않고, 정답이라면 반드시 찾아낼 수 있는 수학적인 설계도"**를 완성했다는 점에서 매우 의미 있는 연구입니다.

기술 요약

[기술 요약] TSP에 적용된 포괄적 매개변수화 및 실행 가능성 준수 양자 회로 연구

1. 문제 배경 (Problem Statement)

현재 양자 근사 최적화 알고리즘(QAOA) 및 그 변형인 QAOA(Quantum Alternating Operator Ansatz)는 조합 최적화 문제를 해결하는 데 널리 사용되고 있습니다. 그러나 기존 방식에는 두 가지 주요 한계가 있습니다.

• 도달 가능성 문제 (Reachability Issues): 기존 QAOA 회로는 매개변수(parameter)의 개수가 고정되어 있을 때, 최적해(optimum)를 포함한 모든 실행 가능한 해(feasible solution)에 도달할 수 있다는 보장이 없습니다. 최적해에 도달하려면 매개변수의 개수가 무한히 많아져야 한다는 점근적(asymptotic) 보장만 존재합니다.
• 제약 조건 처리의 비효율성: 외적 제약 조건(hard constraints)이 있는 문제(예: TSP)의 경우, 기존 방식은 제약 조건을 위반하는 상태(infeasible states)를 탐색 공간에 포함시켜 계산 자원을 낭비하거나, 페널티 항을 사용하여 최적화 난이도를 높입니다.

2. 핵심 방법론 (Methodology)

본 논문은 이러한 문제를 해결하기 위해 "포괄적 매개변수화(Exhaustively Parametrised)" 및 **"실행 가능성 준수(Feasibility-Respecting)"**라는 두 가지 개념을 도입합니다.

A. 핵심 개념 정의

• 포괄적 매개변수화 (Exhaustively Parametrised): 유한한 수의 매개변수만으로도 모든 실행 가능한 해(최적해 포함)를 정확하게(exactly) 생성할 수 있는 회로.
• 실행 가능성 준수 (Feasibility-Respecting): 회로가 생성하는 모든 양자 상태가 반드시 실행 가능한 해의 중첩(superposition)이어야 하며, 실행 불가능한 상태는 절대 생성하지 않는 회로.

B. 추상적 파이프라인 (Abstract Pipeline)

저자들은 군론(Group Theory)을 활용하여 이러한 회로를 설계하는 일반적인 프레임워크를 제안합니다.

1. 이행적 군 작용 (Transitive Group Action): 문제의 실행 가능한 해 집합($F$) 위에서 모든 해 사이를 이동할 수 있는 군(Group, $G$)의 작용을 식별합니다.
2. 생성 수열 (Generating Sequence): 군 $G$의 모든 원소를 특정 순서와 중복을 허용하여 만들어낼 수 있는 원소들의 수열 $(h_i)$를 찾습니다. 특히, 각 원소가 **인볼루션(Involution, $h^2=I$)**인 경우를 활용합니다.
3. 회로 구성: 생성 수열의 각 원소를 양자 게이트(Unitary operator)로 변환하고, 이를 매개변수 $\theta$와 함께 지수 함수 형태($e^{-i\theta H}$)로 결합하여 회로를 구축합니다.

C. TSP에 대한 구체적 적용

외판원 문제(TSP)의 실행 가능한 해는 대칭군($S_n$)의 원소와 일치합니다. 이를 바탕으로 두 가지 회로를 설계했습니다.

• 버블 정렬 수열 (Bubble Sort Sequence): 인접한 두 도시를 교환하는 방식을 사용하여 $O(n^2)$개의 매개변수를 가집니다.
• 이진 삽입 수열 (Binary Insertion Sequence): 재귀적 구조를 활용하여 $O(n \log n)$개의 매개변수만으로도 모든 해에 도달할 수 있는 훨씬 효율적인 수열을 제안했습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 회로 설계 패러다임 제시: 기존 QAOA의 점근적 도달 가능성을 넘어, 유한한 매개변수로 모든 해를 보장하는 '포괄적 매개변수화' 개념을 정립했습니다.
2. 군론 기반의 일반적 프레임워크: 특정 문제에 국한되지 않고, 군론의 '이행적 작용'과 '생성 수열'을 이용해 제약 조건이 있는 최적화 문제를 위한 양자 회로를 설계하는 수학적 파이프라인을 구축했습니다.
3. 효율적인 TSP 회로 도출: TSP 문제에 대해 매개변수 개수를 획기적으로 줄인($n \log n$) 새로운 양자 회로 구조를 이론적으로 증명하고 제시했습니다.

4. 연구 결과 (Results)

9개 도시의 TSP 인스턴스를 대상으로 수치적 검증(Numerical Proof-of-principle)을 수행한 결과는 다음과 같습니다.

• 성능 우위: 기존의 Hadfield et al. 방식의 QAOA 믹서보다 본 논문에서 제안한 두 가지 방식(Bubble sort, Binary insertion)이 더 높은 근사 비율(Approximation Ratio)을 기록했습니다.
• 매개변수 효율성: $O(n \log n)$ 매개변수를 사용하는 이진 삽입 기반 회로가 $O(n^2)$을 사용하는 버블 정렬 기반 회로보다 더 높은 성능(약 0.91의 근사 비율)을 보였습니다. 이는 매개변수 공간의 차원이 낮을수록 고전적 최적화 도구(COBYLA)가 최적의 매개변수를 찾기가 더 용이함을 시사합니다.
• 한계점 확인: 이론적으로는 최적해에 도달할 수 있음이 보장되지만, 실제 수치 실험에서는 고전적 최적화 알고리즘이 복잡한 매개변수 지형(landscape) 때문에 최적의 매개변수를 완벽히 찾아내지는 못했습니다. 즉, **"도달 가능성(Reachability)이 곧 학습 가능성(Trainability)을 의미하지는 않는다"**는 중요한 통찰을 제공합니다.

5. 의의 및 결론 (Significance)

본 논문은 양자 최적화 알고리즘 설계에 있어 표현력(Expressivity)의 한계를 수학적으로 극복하려는 시도입니다. 제약 조건을 회로 구조 자체에 내재시킴으로써 불필요한 탐색을 차단하고, 모든 해에 대한 접근성을 보장하는 설계 방식을 제안했습니다. 이는 향후 TSP뿐만 아니라 다양한 조합 최적화 문제(시설 입지 문제, 차량 경로 문제 등)를 위한 맞춤형 양자 알고리즘을 설계하는 데 중요한 이론적 토대가 될 것입니다.