상상해 보세요. 한 명의 세일즈맨이 100 개의 도시를 한 번씩만 방문하고 다시 출발점으로 돌아와야 한다고 칩시다. 이때 가장 짧은 길을 찾아야 합니다.
고전적인 방법: 모든 가능한 경로를 하나하나 계산해 봅니다. 하지만 도시가 10 개만 되어도 경로의 수는 수백만 개, 20 개가 되면 우주의 별 개수보다 많아집니다.
핵심 난제 (작은 순환 고리): 컴퓨터가 "A→B→C→A"처럼 3 개 도시만 돌고 나머지는 무시하는 엉뚱한 경로를 찾아낼 수 있습니다. 이를 **'작은 순환 고리 (Subtour)'**라고 합니다. 이걸 막기 위해 "어떤 도시 집합도 고립되어서는 안 된다"는 규칙을 수천, 수만 개 만들어야 하는데, 이 규칙 자체가 너무 많아서 컴퓨터가 미쳐버립니다.
2. 이 연구의 해결책: "두 가지 전략의 합작"
저자들은 이 거대한 문제를 해결하기 위해 두 가지 똑똑한 전략을 썼습니다.
전략 1: "필요할 때만 규칙 추가하기" (Cutting-Plane Approach, CPA)
비유: 집을 지을 때, 처음부터 "화재, 도둑, 지진, 폭풍우" 등 모든 재해에 대한 안전 규칙을 다 포함해서 설계하면 설계도가 너무 두꺼워져서 짓기 어렵습니다.
해결책: 처음엔 기본 규칙 (각 도시를 한 번만 방문) 만 적용하고 집을 짓습니다. 만약 "도둑이 들 수 있는 구멍"이 생기면 그때그때 그 구멍만 막는 규칙을 추가합니다.
효과: 처음부터 모든 규칙을 다 넣지 않고, 문제가 생길 때만 필요한 규칙을 추가하므로 컴퓨터가 훨씬 가볍게 문제를 풀 수 있습니다.
전략 2: "불필요한 길 미리 걷어내기" (Cost-based Arc Filtering, CAF)
비유: 도시 간 거리가 너무 멀어서 절대 최단 경로가 될 수 없는 길들은 아예 지도에서 지워버리는 겁니다.
해결책: 각 도시에서 가장 가까운 이웃 도시들만 남기고, 너무 먼 길들은 미리 삭제합니다.
효과: 풀어야 할 길의 수가 확 줄어듭니다.
3. 양자 컴퓨터의 등장: "새로운 도구의 활용"
이제 이 정제된 문제를 **양자 컴퓨터 (D-Wave)**에 맡깁니다. 양자 컴퓨터는 고전 컴퓨터와 달리 여러 가능성을 동시에 탐색하는 '중첩'과 '터널링'이라는 능력을 가졌습니다.
하지만 양자 컴퓨터도 한계가 있습니다.
직접 실행 (Direct QPU): 양자 컴퓨터 자체에 문제를 바로 넣는 방식입니다. 하지만 규칙이 너무 많으면 양자 컴퓨터의 '메모리 (큐비트)'가 부족해져서 실패합니다.
하이브리드 방식 (Hybrid): 고전 컴퓨터와 양자 컴퓨터가 팀을 이루는 방식입니다. 고전 컴퓨터가 큰 그림을 잡고, 어려운 부분만 양자 컴퓨터에게 맡겨 정교하게 다듬는 식입니다.
4. 실험 결과: "어떤 방식이 이겼나?"
연구팀은 다양한 도시 수 (5 개에서 30 개까지) 로 실험을 했습니다.
고전 컴퓨터만 쓸 때:
규칙을 처음부터 다 넣으면 (CILP) 도시가 20 개만 되어도 계산이 멈춥니다.
하지만 **'필요할 때만 규칙 추가 (CPA)'**와 **'불필요한 길 제거 (CAF)'**를 쓰면 도시가 45 개가 되어도 1 초 만에 해결됩니다.
양자 컴퓨터 (직접 실행) 를 쓸 때:
규칙을 처음부터 다 넣으면 도시가 8 개만 되어도 실패합니다.
하지만 **'필요할 때만 규칙 추가 (CPA)'**를 쓰면 도시가 10 개까지도 꽤 잘 풀립니다. (규칙을 줄여주니까 양자 컴퓨터가 숨 쉴 공간이 생긴 겁니다.)
하이브리드 방식 (고전 + 양자 팀):
최고의 성과! 도시가 25 개까지는 100% 최적의 답을 찾았고, 30 개 도시에서도 거의 완벽한 답 (오차 1% 이내) 을 찾았습니다.
이는 양자 컴퓨터가 아직 완벽하지 않지만, 고전 컴퓨터와 잘 섞으면 실용적인 문제를 풀 수 있다는 것을 보여줍니다.
5. 결론: "왜 이 연구가 중요한가?"
이 논문은 **"양자 컴퓨터가 아직은 작고 단순한 문제만 푼다"**는 통념을 깨뜨리는 중요한 시도입니다.
핵심 메시지: 양자 컴퓨터 자체의 성능이 부족해도, **문제를 어떻게 잘게 쪼개고 (CPA), 불필요한 부분을 미리 정리 (CAF)**하느냐에 따라 훨씬 큰 문제를 풀 수 있습니다.
미래: 이 방법은 양자 컴퓨터가 더 발전하기 전, 지금 당장 실생활 (물류, 배송 경로 최적화 등) 에 양자 기술을 적용할 수 있는 가장 현실적인 길입니다.
한 줄 요약:
"양자 컴퓨터라는 새 장비를 쓰려면, 먼저 문제를 아주 깔끔하게 정리하고 (불필요한 길 제거), 문제가 생길 때만 규칙을 추가하는 지혜 (Cutting-Plane) 를 써야만, 비로소 큰 도시의 배송 문제를 해결할 수 있다!"
이 논문은 여행하는 세일즈맨 문제 (TSP, Traveling Salesman Problem) 를 해결하기 위해 고전적 최적화 기법과 양자 최적화 (Quantum Optimization) 기법을 결합한 새로운 프레임워크를 제안하고 있습니다. 특히, TSP 모델링의 주요 병목 현상인 부분 경로 제거 제약 (Subtour Elimination Constraints, SEC) 의 지수적 증가 문제를 해결하기 위해 절단 평면 방법론 (Cutting-Plane Methodology) 과 전처리 기법 을 양자 어닐링 (Quantum Annealing) 환경에 적용한 것이 핵심입니다.
다음은 논문의 상세 기술 요약입니다.
1. 문제 정의 및 배경
문제: TSP 는 n개의 도시를 정확히 한 번씩 방문하고 출발지로 돌아오는 최단 경로를 찾는 NP-난제 (NP-hard) 입니다.
주요 난제: TSP 를 정수 선형 계획법 (ILP) 으로 모델링할 때, 모든 도시를 한 번만 방문한다는 조건 (차수 제약) 외에 부분 경로 (Subtour) 가 형성되지 않도록 하는 제약 조건이 필요합니다.
부분 경로 제거 제약의 수는 도시 수 n에 대해 지수적으로 증가 (O(2n)) 합니다.
모든 제약을 초기 모델에 명시적으로 포함하면 (Complete ILP, CILP), 중규모 문제조차도 계산적으로 처리 불가능해집니다.
양자 컴퓨팅의 한계: 현재 D-Wave 와 같은 양자 어닐러는 제한된 큐비트 수와 연결성, 그리고 제약 조건을 목적함수의 페널티 항으로 변환해야 하는 QUBO(Quadratic Unconstrained Binary Optimization) 모델의 특성상, 복잡한 TSP 제약 조건을 직접 처리하는 데 어려움을 겪고 있습니다.
2. 제안된 방법론 (Methodology)
저자들은 TSP 의 복잡성을 줄이고 양자 하드웨어의 한계를 극복하기 위해 두 가지 핵심 전략을 결합한 반복적 프레임워크 를 제안했습니다.
A. 절단 평면 접근법 (Cutting-Plane Approach, CPA)
동적 제약 생성: 초기 모델에는 부분 경로 제거 제약을 포함하지 않고, 오직 차수 제약 (각 도시를 한 번 방문) 만 포함하여 문제를 풉니다.
반복 과정:
솔버가 해를 구하면, 그 해에 분리된 사이클 (부분 경로) 이 있는지 확인합니다.
발견된 각 부분 경로에 대해 해당 제약 조건을 모델에 추가 (Cutting) 합니다.
부분 경로가 사라질 때까지 이 과정을 반복합니다.
효과: 필요한 제약 조건만 동적으로 추가하므로, 초기 모델의 크기를 크게 줄이고 계산 효율성을 극대화합니다.
B. 비용 기반 아크 필터링 (Cost-based Arc Filtering, CAF)
전처리 단계: 최적 해에 포함될 가능성이 낮은 아크 (간선) 를 사전에 제거합니다.
작동 원리: 각 도시에서 출발하는 아크들을 비용 순으로 정렬하여, 가장 비용이 낮은 이웃 도시들만 후보 아크로 남깁니다.
효과: 결정 변수 (Decision Variables) 의 수를 줄여 모델의 밀도를 낮추고, 양자 하드웨어에 매핑할 때 필요한 리소스를 절감합니다.
C. 양자 최적화 전략
제안된 프레임워크는 다음 세 가지 방식으로 실행 및 평가되었습니다.
고전적 최적화 (Classical): 상용 솔버 (Gurobi) 를 사용하여 CILP 와 CPA 를 비교.
직접 양자 실행 (Direct QPU): D-Wave QPU 에서 직접 실행. 문제를 QUBO 모델로 변환하여 페널티 항을 통해 제약 조건을 처리.
하이브리드 양자 - 고전 (Hybrid): D-Wave 의 CQM (Constrained Quadratic Model) 및 하이브리드 솔버 (LeapCQMHybrid) 사용. 제약 조건을 명시적으로 표현하고, 고전적 메타휴리스틱과 양자 어닐링을 결합하여 대규모 문제를 해결.
3. 주요 기여 (Key Contributions)
양자 프레임워크 내 CPA 최초 적용: TSP 해결을 위해 양자 어닐링 환경에서 반복적 지연 제약 생성 (Lazy Constraint Generation) 기법을 적용한 최초의 연구 중 하나로, 양자 최적화의 확장성을 입증했습니다.
모델 복잡도 감소 전략의 통합: CAF 전처리 (변수 감소) 와 CPA (제약 조건 동적 생성) 를 결합하여, 기존 QUBO 기반 접근법보다 훨씬 컴팩트한 모델을 구축했습니다.
실용적 규모 문제 해결: 기존 양자 연구가 8~15 개 노드 수준에 머물렀던 반면, 제안된 방법은 최대 30 개 노드까지의 표준 벤치마크 (TSPLIB) 문제를 해결할 수 있음을 보였습니다.
4. 실험 결과 (Results)
A. 모델 복잡도 및 고전적 성능
변수 감소: CAF 적용 시 모든 인스턴스에서 약 20~35% 의 결정 변수가 감소했습니다.
제약 조건 감소: CPA 는 CILP 대비 제약 조건을 95% 이상 (대규모 인스턴스에서는 100% 에 가까움) 줄였습니다.
고전적 솔버 성능: CPA + CAF 조합은 45 개 노드 인스턴스를 0.1 초 미만으로 해결하는 반면, CILP 는 20 개 노드 이상에서 모델 생성조차 불가능했습니다.
B. 직접 양자 실행 (Direct QPU) 결과
CILP 한계: CILP 는 5 개 노드 이상에서 실행 불가능하거나 해를 찾지 못했습니다 (제약 조건이 너무 많아 QUBO 모델이 너무 복잡해짐).
CPA 우위: CPA 를 적용한 경우, 8 개 노드까지는 100% 실행 가능하고 최적해를 찾았으며, 10 개 노드까지도 40% 이상의 실행 가능성 (Feasibility) 을 보였습니다. 이는 동적 제약 생성이 양자 하드웨어의 리소스 한계를 극복하는 데 필수적임을 보여줍니다.
C. 하이브리드 양자 - 고전 결과
성능: 하이브리드 솔버를 사용한 CPA + CAF 접근법은 12~25 개 노드 인스턴스에서 0% 최적성 갭 (Optimality Gap) 을 기록하며 최적해를 찾았습니다.
확장성: 30 개 노드 인스턴스에서도 1% 의 매우 작은 갭 (Optimality Gap) 만 발생하여 높은 품질의 해를 제공했습니다.
의의: 순수 양자 방법 (Direct QPU) 이나 기존 고전적 방법보다 훨씬 효율적으로 확장성을 입증했습니다.
5. 의의 및 결론
이론과 실전의 간극 해소: 양자 최적화가 실제 TSP 와 같은 복잡한 조합 최적화 문제에 적용 가능하다는 것을 보여주었습니다.
하이브리드 접근법의 우위: 현재 기술 수준에서는 순수 양자 알고리즘보다는 고전적 전처리 (CAF) 와 반복적 제약 생성 (CPA) 을 결합한 하이브리드 양자 - 고전 솔버가 가장 효과적이고 확장 가능한 전략임을 입증했습니다.
미래 전망: 이 연구는 양자 하드웨어의 발전과 함께 더 큰 규모의 TSP 문제를 해결할 수 있는 기반을 마련했으며, 향후 적응형 파라미터 튜닝 및 더 정교한 인코딩 전략 연구의 방향을 제시합니다.
요약하자면, 이 논문은 "TSP 의 지수적 제약 조건 문제를 CPA 와 CAF 로 해결하여, 현재 양자 하드웨어의 한계 내에서 실용적인 규모의 최적화 문제를 성공적으로 해결할 수 있는 새로운 패러다임" 을 제시한 연구입니다.