양자 알고리즘을 통한 외판원 문제 해결

Abstract

외판원 문제(Traveling Salesman Problem, TSP)는 모든 도시를 방문하고 원래 도시로 돌아오는 최단 순환(cycle)을 찾는 문제다. 최근 Srinivasan el al. (2018)은 양자 위상추정(Quantum Phase Estimation, QPE)으로 외판원 데이터베이스(TSP database)를 만드는 방법을 제안하였다. 외판원 데이터베이스에서 최단 순환을 찾아 외판원 문제를 풀 수 있다. 한편, 외판원 데이터베이스에서 최단 순환을 찾기 위해 그로버 연산자(Grover operator)를 구성해야 한다. 그러나 그들의 연구에서 그로버 연산자를 구성하는 체계적인 방법은 논의되지 않았다. 여기에 더해, 그들은 오직 순환 하나에 대응하는 고유벡터 하나를 고려하여 가장 단순한 외판원 문제를 시뮬레이션하였다. 본 논문에서는 외판원 데이터베이스에서 최단 순환 상태를 양자 알고리즘으로 찾는 방법을 제안한다. 먼저 주어진 길이 보다 짧은 순환을 표적(target)으로 그로버 연산자를 구성한다. 다음으로 양자 카운팅 알고리즘(Quantum Counting Algorithm, QCA)으로 주어진 길이 보다 짧은 순환이 있는지 판단한다. 만약 주어진 길이 보다 짧은 순환이 있으면 그로버 검색 알고리즘(Grover’s Search Algorithm, GSA)으로 찾는다. 본 연구의 검증을 위해, 도시가 4곳인 외판원 문제의 세부적인 해결과정을 시뮬레이션한다.; Traveling Salesman Problem(TSP) is a problem that find the optimum cycle for visiting every city and returning to starting city. In order to find the solution for TSP, there have been many approaches. Recently, Srinivasan et al. (2018) discussed a quantum algorithm for TSP, using Quantum Phase Estimation(QPE). Their approach uses TSP database corresponding to every cycle and its cycle length. Even though the optimum cycle should be found in TSP database, they could not provide the systematic way to construct Grover operator for it. Furthermore, they considered only a eigenvector for one cycle. In this paper, we provide a method of finding the optimum cycle state in the superposition by running quantum algorithm. Specially, by applying Quantum Counting Algorithm(QCA) we determine whether there is a cycle shorter than the given length . If a cycle shorter than exists, by performing a Grover Search Algorithm(GSA), we find the cycle. By considering the 4-City TSP, we show the effectiveness of our proposal.