⚛️ quantum physics

Solving The Travelling Salesman Problem Using A Single Qubit

이 논문은 양자 병렬성과 양자 브라키스토크론 접근법에 기반한 최적 제어 방법을 활용하여 단 하나의 큐비트로 최대 9개 도시의 외판원 문제를 해결하는 자원 효율적인 양자 알고리즘을 제시하며, 기존의 양자 및 고전적 방법보다 우수한 정확도와 잠재적인 다항 시간 가속을 입증한다.

원저자: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

게시일 2026-01-28

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

큰 문제: 지친 여행가

당신이 도시들의 지도를 들고 있는 외판원이라고 상상해 보세요. 당신의 임무는 모든 도시를 정확히 한 번씩 방문하고 집으로 돌아오는 것이지만, 당신은 가장 짧은 거리를 사용하여 이동하고 싶어 합니다.

이것이 바로 그 유명한 **외판원 문제(Traveling Salesman Problem, TSP)**입니다. 이는 매우 빠르게 난도가 높아지는 고전적인 퍼즐입니다. 도시가 4개라면 쉽습니다. 10개라면 감당할 수 있습니다. 하지만 도시가 20개가 되면, 가능한 경로의 수가 너무 방대해져서 세계에서 가장 빠른 슈퍼컴퓨터조차 그 경로들을 하나하나 확인하는 데 우주의 나이보다 더 긴 시간을 소요하게 됩니다.

기존의 양자 방식: "너무 많은 열쇠" 접근법

보통 과학자들이 이 문제를 양자 컴퓨터로 해결하려고 할 때, 그들은 이 문제를 수많은 턱(tumbler)이 있는 거대한 자물쇠처럼 취급합니다. 그들은 모든 도시와 모든 가능한 연결마다 별도의 "턱"(큐비트)이 필요합니다.

문제점: 단 9개나 10개의 도시 문제를 풀기 위해서도, 기존의 양자 방식은 수백 개 또는 수천 개의 큐비트를 필요로 합니다.
현실: 현재의 양자 컴퓨터는 노이즈가 많고 취약합니다. 그 많은 큐비트들이 함께 작동하도록 유지하는 데 어려움을 겪으며, 작은 지도에 대해서조차 완벽한 답을 찾는 데 자주 실패합니다.

새로운 아이디어: "단 하나의 원더" 큐비트

이 논문은 단 하나의 큐비트(양자 정보의 기본 단위)만을 사용하여 TSP를 해결하는 혁신적이고 새로운 방법을 제안합니다. 이 단일 큐비트를 단순한 작은 스위치가 아니라, 3차원 공간의 어떤 방향으로도 가리킬 수 있는 마법의 팽이라고 생각해 보세요.

그들이 이 방식을 구현하는 방법은 다음과 같습니다.

1. 지도는 지구본이다 (블로흐 구체)

저자들은 도시들을 평면 종이 위에 그리는 대신, 이들을 구(sphere)의 표면(지구본과 같은) 위에 배치합니다.

도시들: "실제" 도시들은 이 지구본의 적도를 따라 배치됩니다.
거리: 두 도시 사이의 거리는 마일(mile)로 측정되는 것이 아니라, 한 도시 지점에서 다른 도시 지점으로 가기 위해 팽이를 얼마나 돌려야 하는지로 측정됩니다.
목표: 외판원은 적도의 모든 지점을 한 번씩 방문하고 집으로 돌아오면서, 전체 "회전 노력"을 최소화하며 팽이를 돌려야 합니다.

2. 중첩의 초고속도로 (Superposition Super-Highway)

기존 방식에서는 경로 A, 경로 B, 경로 C를 하나씩 차례대로 확인합니다.
이 새로운 방식에서 저자들은 **양자 중첩(quantum superposition)**을 사용합니다. 이 팽이가 동시에 여러 곳에 존재할 수 있는 마법의 여행가라고 상상해 보세요.

하나의 경로를 걷는 대신, 이 "팽이"는 모든 가능한 경로를 동시에 탐색합니다.
이것은 마치 수천 명의 탐험가를 수천 개의 서로 다른 길로 동시에 보내는 것과 같지만, 그들은 모두 동일한 탐험가이며, 단지 "중첩" 상태로 모든 경로에 존재하는 것입니다.

3. "브라키스토크론" 지름길

이 논문은 물리학의 브라키스토크론(Brachistochrone) 문제라는 개념을 사용합니다. 역사적으로 이 문제는 "두 점 사이를 공이 가장 빠르게 굴러 내려가는 경로는 무엇인가?"를 묻습니다.

저자들은 TSP를 이 문제의 한 버전으로 변환했습니다. 그들은 경로 찾기를 시간과의 싸움으로 취급합니다.
그들은 단일 큐비트를 부드럽게 밀고 회전시키기 위해 최적 제어(Optimal Control) 기술(매우 똑똑한 자동 조종 장치라고 생각하세요)을 사용합니다.
이 자동 조종 장치는 너무 긴 경로들은 서로 상쇄되고(노이즈 캔슬링 헤드폰처럼), 가장 짧은 경로가 증폭되어 두드러지도록 "회전"을 미세하게 조정합니다.

4. 최종 확인

큐비트가 모든 경로를 동시에 "여행"한 후, 과학자들은 팽이의 최종 위치를 측정합니다.

그들은 모든 경로를 일일이 확인하지 않습니다. 그들은 여정의 맨 마지막을 봅니다.
최종 상태를 분석함으로써, 그들은 역으로 추적하여 승리한 경로를 재구성할 수 있습니다.
이것은 마술사가 카드를 섞는 트릭을 수행할 때, 마지막 카드를 봄으로써 전체 덱의 순서를 알아내는 것과 같습니다.

결과: 그들은 무엇을 발견했는가?

연구팀은 이 "단일 큐비트" 방식을 테스트하기 위해 컴퓨터 시뮬레이션을 실행했습니다.

테스트: 그들은 4개에서 9개의 도시를 가진 TSP 퍼즐을 해결했습니다.
성공: 90% 이상의 문제에서 그들의 방식은 완벽하고 최단인 경로를 찾아냈습니다.
안전장치: 완벽한 답을 얻지 못한 드문 경우에도, 그들은 여전히 매우 훌륭한 근사치(최적의 답 대비 약 90% 수준)를 얻었습니다.
효율성: 그들은 이 모든 것을 단 하나의 큐비트로 해냈습니다. 반면 다른 방식들은 수십 개 또는 수백 개의 큐비트가 필요했을 것입니다.

핵심 요약

이 논문은 내일 당장 백만 개의 도시를 위한 TSP를 해결하겠다고 주장하는 것이 아닙니다. 대신, 강력한 개념을 증명합니다: 복잡한 경로 문제를 해결하기 위해 거대한 양자 컴퓨터가 반드시 필요한 것은 아닙니다.

문제를 단일 회전하는 구체 위의 기하학적 퍼즐로 다루고 "여러 곳에 동시에 존재할 수 있는 힘"을 활용함으로써, 그들은 단 하나의 큐비트가 복잡한 미로를 효율적으로 항해할 수 있음을 보여주었습니다. 이는 큐비트를 정확하게 회전시킬 수 있는 어떤 양자 플랫폼에서도 구축될 수 있는, 자원 소모가 적은 새로운 양자 최적화 사고방식입니다.

기술 요약: 단일 큐비트를 이용한 외판원 문제(Travelling Salesman Problem)의 해결

문제 정의
외판원 문제(TSP)는 일련의 도시들을 정확히 한 번씩 방문하고 출발지로 돌아오는 가장 짧은 경로를 찾는 것을 요구하는 근본적인 NP-어려움(NP-hard) 조합 최적화 문제이다. 고전적 알고리즘이 존재하지만, 정확한 해법은 도시 수에 따라 지수적으로 확장되며, 휴리스틱 방법은 최적성을 보장하지 못한다. 이차 무제약 이진 최적화(QUBO)를 Ising 해밀토니안에 매핑하거나 위상 추정 회로를 사용하는 기존의 양자 접근 방식은 자원 집약적이다. 이러한 방식은 일반적으로 많은 수의 큐비트(예: 10개 도시 문제에 대해 수천 개의 물리적 큐비트)를 필요로 하며, 현재의 노이즈가 있는 하드웨어에서 성공 확률이 낮은 경우가 많다.

방법론
저자들은 얽힘(entanglement) 대신 양자 병렬성(quantum parallelism)의 원리를 활용하여 임의의 TSP를 단일 큐비트에 매핑하는 알고리즘을 제안한다. 핵심 방법론은 세 가지 주요 단계로 구성된다:

이산 브라키스토크론(Discrete Brachistochrone) 문제로의 매핑:
TSP는 먼저 유한 이산 브라키스토크론 문제로 재구성된다. 이 고전적 비유에서 도시는 2D 평면 위의 점들로 표현되며, 경로는 선형 조각 함수(piece-wise functions)가 된다. 목적 함수는 총 이동 거리와 대응하는 시간 범함수 $Q$ 를 최소화하는 것이다. 경로는 반드시 초기 도시로 돌아와야 한다는 제약 조건이 있으며, 이는 최종 지점 $F$ 로 향하는 추가적인 선형 세그먼트에 의해 인코딩된다.
블로흐 구(Bloch Sphere) 상의 인코딩:
이산 브라키스토크론 문제는 단일 큐비트의 블로흐 구 기하학으로 매핑된다.

상태 표현: 도시( $c_i$ )는 블로흐 구의 적도에 위치한 양자 상태 $|P_{ii}\rangle$ 로 표현된다.
거리 인코딩: 도시 간의 상대적 거리는 구 위의 기하학적 거리(측지선)로 인코딩된다. 중간 상태 $|P_{ij}\rangle$ 는 적도 상태와 극점 $P_0$ 를 잇는 측지선 곡선 위에 배치된다. 상태 간의 각거리(angular distance)는 도시 간의 유클리드 거리와 대응한다.
이동(Traversal): 도시 간의 이동은 회전 연산자( $U^u$ 및 $U^d$ )를 통해 이루어진다. 도시 $i$ 에서 도시 $j$ 로의 "단계(step)"는 적도에서 중간 상태 $|P_{ij}\rangle$ (극점에 더 가까운 상태)로의 "업(up)" 회전에 이어, $|P_{jj}\rangle$ (적도 상태)로의 "다운(down)" 회전을 포함한다.

중첩을 통한 양자 최적화:
경로를 순차적으로 탐색하는 브루트 포스(brute-force) 방식과 달리, 제안된 알고리즘은 양자 중첩을 활용하여 여러 경로를 동시에 탐색한다.

중첩 생성: 시스템은 시작 도시를 나타내는 상태로 초기화된다. 일련의 조절 가능한 회전 연산자는 라우팅 차트의 각 레이어에서 중첩 상태를 생성하며, 이는 모든 유효한 경로와 유효하지 않은 경로를 동시에 탐색하게 한다.
최적화: 알고리즘은 회전 연산자를 튜닝하기 위해 특정 섭동 스토캐스틱 근사(SPSA)라는 최적 제어 방법을 채택한다.
목적 함수: 브루트 포스 양자 접근 방식은 시간 범함수 $T$ 를 최소화할 수 있지만, 중첩 기반 접근 방식은 고전적 비용 함수 $D$ (총 거리)를 최소화한다. 이는 중첩에 유효한 해밀턴 사이클을 형성하지 않는 "고전적으로 금지된" 경로들이 포함되어 있기 때문이다. 최적화는 최종 상태에서 유효한 해밀턴 사이클의 인구(population)를 최대화하는 것을 목표로 한다.
측정 및 후처리: 알고 отда적인 상태(penultimate state)의 투영 측정(projective measurement)을 통해 알고리즘이 종료된다. 양자 상태 토모그래피를 통해 인구 분포를 분석하여 최적의 TSP 경로에 해당하는 지배적인 경로를 식별한다.

주요 결과
저자들은 4개에서 9개의 도시를 가진 TSP 인스턴스를 단일 큐비트로 해결하는 수치 시뮬레이션을 제시한다.

정확도: 테스트된 문제 규모에 대해, 알고리즘은 테스트된 문제 인스턴스의 90% 이상에서 정확한 해(근사 비율 $\sim 1$ )를 얻었다.
근사: 정확한 해를 찾지 못한 경우에도 높은 근사 비율( $\sim 0.90$ )을 달acia했다.
자원 효율성: 이 방법은 단 하나의 큐비트만을 필요로 하며, 이는 유사한 규모의 문제를 위해 수백 또는 수천 개의 큐비트를 요구하는 기존 양자 알고리즘과 극명한 대조를 이룬다.
플랫폼 불가지론(Platform Agnosticism): 이 알고로리즘은 초전도 큐비트, 트랩 이온, 질소-공석 중심(NV center), 리드베리 원자 등 고충실도 임의 큐비트 회전 및 상태 토모그래피가 가능한 모든 양자 플랫폼에 구현될 수 있도록 설계되었다.

의의 및 주장
이 논문은 이 접근 방식이 소규모 내지 중규모 TSP 인스턴스에 대해 기존 양자 알고리즘보다 더 자원 효율적이고 정확한 대안을 제공한다고 주장한다. 단일 큐비트 상의 중첩 원리를 활용함으로써, 이 방법은 대규모 얽힘과 방대한 큐비트 수를 피할 수 있으며, 이는 현재 양자 하드웨어의 주요 병목 현상을 해결한다.

저자들은 고전적 알고리즘에 대해 다항 시간(polynomial time)의 속도 향상을 제공할 가능성을 논의하며, 경로의 중첩에 내재된 양자 병렬성이 시간과 정확도 모두에서 실질적인 이점을 제공할 수 있음을 시사한다. 이 연구는 TSP를 단순한 라우팅 문제가 아니라 양자 제어를 통해 해결 가능한 특정 제약 조건이 있는 브라키스토크론 문제의 사례로 위치시키며, 근미래 양자 장치(NISQ)를 위한 확장 가능한 양자 최적화의 경로를 열어준다.