IBM Q Experiment 시뮬레이션을 이용한순환 판매원 문제 해결

Abstract

순환 판매원 문제는 잘 알려진 미해결문제이다. 최근 순환 판매원 문제를 양자알고리즘에 기반하여 해결하려는 시도들이 있어왔다. 본 연구에서는 현재 사용할 수 있는 IBM Q Experiment를 통해 순환 판매원 문제를 접근하려한다. 이를 위해 순환 판매원 문제를 위한 양자 알고리즘을 IBM Q Experiment에 사용할 수 있는 형태로 만드는 작업이 필요하다. 본 연구에서는 순환 판매원 문제를 위한 양자 알고리즘을 분해하여 실제 양자 컴퓨터에 대해 실행할 수 있는 모델을 구현한다. 지금까지의 제안된 모델은 이론적 또는 행렬 계산으로만 이루어져 있었다. 이러한 문제에 대해 양자 컴퓨터에서 실행시키도록 IBM Q Experiment에 사용할 수 있는 형태로 분해를 제공하였다. 구현된 알고리즘을 실제 양자 컴퓨터에서의 실행함을 통해 현재 사용할 수 있는 양자컴퓨터의 성능을 평가하였다. |Traveling Salesman Problem(TSP) is a well-known unsolved problem. Recently, there have been attempts to solve the traveling salesman problem based on the quantum algorithm. This work attempts to approach the traveling salesman problem through the IBM Q Experiment currently available. It is necessary to make the quantum algorithm for traveling salesman problems into forms that can be used for IBM Q Experience. In this research, a model that can be executed on an actual quantum computer is implemented by decomposing a quantum algorithm for the traveling salesman problem. The decomposition is provided in a form that can be used for IBM Q Experiment. The performance of a quantum computer that can be currently used is evaluated by executing the implemented algorithm on a real quantum computer.