3개의 도시를 여행하는 순서는 몇가지일까요? 맞습니다, 6가지(=3x2x1)입니다. 그렇다면 10개의 도시를 여행하는 순서는?  놀랍게도 약 3백만 가지(≈10x9x8…x2x1)나 됩니다. 이처럼 여러 개의 도시를 여행하는 수많은 조합들 중에서 최단경로를 찾는 것이 컴퓨터 과학의 유명한 “외판원 순회 문제” (Traveling salesman problem) 입니다. 재미 있는 점은 실생활의 많은 조합 문제들을 “외판원 순회 문제”로 바꾸어 풀 수 있다는 점입니다 (마치 컴퓨터의 모든 데이터를 0과 1로 바꾸어 표현할 수 있듯). DNA 염기서열의 분석이나 택배배송의 최적화 등이 대표적인 예입니다. 따라서 “외판원 순회 문제”를 효율적으로 풀기위한 많은 노력들이 있었습니다. 하지만 도시의 수가 늘면 고려해야 할 경우의 수는 기하급수적으로 늘기 때문에 냉장고 만한 슈퍼컴퓨터들이 사용되어 왔습니다.

  저희 DGIST와 KAIST 합작 연구팀은 “외판원 순회 문제”를 슈퍼컴퓨터 보다 빠르게 푸는 칩을 스마트폰에 심을 수 있는 크기로 만들려고 합니다. 이 목표를 달성하기 위해 빛이 흐르는 반도체를 이용해 인공신경망을 제작할 계획입니다 (그림).

그동안 “외판원 순회 문제”를 효율적으로 풀기 위해 양자 컴퓨터를 비롯한 다양한 방식의 컴퓨터들이 제안되었지만 기존의 슈퍼 컴퓨터의 성능을 뛰어넘기는 어려웠습니다. 저희 연구가 성공한다면 자율주행차, 드론, 스마트폰 등에서 실시간으로 “외판원 순회 문제”를 풀 수 있게 되어 실생활에 많은 임팩트가 있을 것으로 기대 하고 있습니다 (예: 자율주행차의 최적의 경로를 교통상황의 변화에 맞춰 실시간으로 업데이트, 스마트폰으로도 안전하게 암호화폐를 거래).  그런 날을 조금이라도 앞당기 위해 저희 연구팀은 최선을 다하겠습니다.