A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

논문 요약: 여행하는 세일즈맨 문제 (TSP) 를 위한 양자 인코딩

1. 문제 정의 (Problem)

여행하는 세일즈맨 문제 (TSP) 는 $n$개의 도시가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 해밀턴 사이클을 찾는 조합 최적화 문제입니다.

• 난이도: 유효한 투어 (tour) 의 수는 도시 수 $n$에 따라 계승 (factorial, $n!$) 으로 증가하여, 고전 컴퓨터에서 해결하기 매우 어렵습니다.
• 기존 접근법의 한계: 양자 어닐링이나 변분 알고리즘에 주로 사용되는 에지 기반 (edge-based) 인코딩은 QUBO/Ising 모델과 호환되지만, 양자 회로 모델에서 순열 (permutation) 구조를 명시적으로 다루기에는 비효율적일 수 있습니다.

2. 방법론 (Methodology)

저자들은 TSP 를 해결하기 위해 시간 레지스터 (time-register) 기반의 경로 중심 인코딩을 제안합니다. 이 방법은 양자 회로 모델에서 유효한 경로를 직접 표현하고, 비용 정보를 위상 (phase) 으로 인코딩합니다.

2.1 인코딩 구조 (Encoding)

• 고정된 시작점: 도시 $n-1$을 시작점이자 종점으로 고정합니다.
• 경로 레지스터: 나머지 $n-1$개의 도시를 방문하는 순서를 $T = n-1$개의 시간 단계에 걸쳐 인코딩합니다.
• 큐비트 수: 각 도시 레이블을 이진수로 표현하기 위해 $b = \lceil \log_2(n-1) \rceil$개의 큐비트가 필요하며, 전체 경로 레지스터는 $T \times b \approx n \log_2 n$개의 큐비트를 사용합니다.
• 초기 상태: 모든 경로 레지스터에 할로 (Hadamard) 게이트를 적용하여 유효한 순열과 무효한 할당 (중복 도시 방문 등) 을 모두 포함하는 균일 중첩 상태 ($|\psi_{unif}\rangle$) 를 생성합니다.

2.2 핵심 오라클 구성 요소
구성은 세 가지 주요 오라클로 이루어집니다:

1. 균일 경로 생성 (Uniform Route Generation): 모든 가능한 도시 시퀀스를 중첩 상태로 만듭니다.
2. 유효성 오라클 (Validity Oracle, $O_{valid}$):
   • 목적: 비시작 도시들의 순열 (각 도시가 정확히 한 번씩 등장) 인지를 판별합니다.
   • 구현: 각 도시 레이블에 대한 보조 큐비트 (ancilla) 를 사용하여, 모든 시간 단계에서 해당 레이블이 등장한 횟수의 홀짝성 (parity) 을 계산합니다. 모든 레이블의 등장 횟수가 홀수 (정확히 1 회) 일 때만 유효 플래그를 1 로 설정합니다.
   • 복잡도: $O(n^2 \log n)$ 개의 CNOT 게이트 및 T 게이트가 소요됩니다.
3. 비용 오라클 (Cost Oracle, $O_{cost}$):
   • 목적: 각 후보 경로의 총 이동 거리를 양자 상태의 위상 ($e^{iL(x)/\Lambda}$) 으로 인코딩합니다.
   • 구현: 시작 간선, 중간 간선, 복귀 간선의 비용을 조건부 위상 회전 (controlled phase rotation) 으로 합산합니다.
   • 복잡도: 단순 구현 (naive implementation) 의 경우 $O(n^3)$ 개의 다중 제어 위상 게이트가 필요하며, 병렬 실행을 고려할 때 회로 깊이는 $O(n^2 \log n)$ 수준입니다.

3. 주요 기여 (Key Contributions)

• 컴팩트한 양자 인코딩: TSP 를 시간 순서대로 도시 레이블의 시퀀스로 직접 표현하는 새로운 양자 회로 설계를 제시했습니다.
• 가역적 오라클 설계: 유효한 순열을 식별하는 오라클과 경로 비용을 위상으로 변환하는 오라클을 명확하게 정의하고 구현했습니다.
• 자원 분석: 필요한 큐비트 수 ($O(n \log n)$) 와 게이트 복잡도 (CNOT: $O(n^3 \log n)$, T 게이트: $O(n^3(\log n + \log(1/\epsilon)))$) 를 정량적으로 분석했습니다.
• 확장성: 이 인코딩은 진폭 증폭 (Amplitude Amplification) 이나 양자 특이값 변환 (QSVT) 과 같은 양자 알고리즘과 호환되도록 설계되었습니다.

4. 결과 및 성능 분석 (Results & Performance)

• 유효 상태의 비율: 전체 가능한 할당 $(n-1)^{n-1}$ 중 유효한 순열 $(n-1)!$의 비율은 스텔링 근사 (Stirling's approximation) 에 따라 $O(e^{-(n-1)})$로 지수적으로 감소합니다.
• 복잡도 한계:
  • 진폭 증폭을 사용하여 유효한 상태만 선택하더라도, 유효 상태의 비율이 지수적으로 작기 때문에 전체 알고리즘의 복잡도는 여전히 **지수적 (Exponential)**입니다.
  • 비용 오라클의 게이트 수가 $O(n^3)$ 수준으로 높아, 현재 제안된 '단순 구현 (naive implementation)'은 실제 대규모 문제 해결에 비효율적입니다.
• 시뮬레이션: 5 개 도시의 작은 예시에서 유효한 투어와 무효한 투어를 구분하고 비용을 위상으로 인코딩하는 것이 가능함을 시연했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용적 속도 향상 아님: 이 연구는 TSP 를 다항 시간 내에 해결하는 양자 알고리즘을 제시하는 것이 아니라, 작은 규모의 시뮬레이션이나 후속 양자 알고리즘 (진폭 증폭, QSVT 등) 을 위한 명확한 베이스라인 인코딩을 제공하는 것을 목표로 합니다.
• 향후 과제:
  • 오라클 최적화: 가역 연산 (reversible arithmetic) 이나 블록 인코딩 (block-encoding) 기법을 사용하여 비용 오라클의 게이트 복잡도를 줄여야 합니다.
  • 유효 상태 비율 증가: 유효한 상태의 비율을 높이는 대체 인코딩 방식을 모색해야 합니다.
  • 스펙트럴 방법: 명시적인 유효성 투영 없이 저비용 투어로 상태를 편향시키는 QSVT 와 같은 스펙트럴 방법의 적용이 유망한 방향입니다.

요약하자면, 이 논문은 TSP 를 양자 회로 모델에 효율적으로 매핑하기 위한 체계적인 프레임워크를 제시했으나, 유효한 해의 희소성과 높은 게이트 복잡도로 인해 현재로서는 지수적 복잡도를 피할 수 없음을 인정하고 있습니다. 이는 향후 더 효율적인 오라클 설계와 하이브리드 양자 알고리즘 개발을 위한 중요한 기초 작업으로 평가됩니다.