본 학과의 안재욱, 문은국 교수 연구팀이 20큐비트급 리드버그 양자컴퓨터를 개발해 계산과학의 난제인 최대독립집합 문제를 계산했다고 밝혔다.
양자컴퓨터는 양자역학의 원리를 사용하여, 디지털컴퓨터로는 불가능한 계산을 수행할 것으로 예상되는 대표적 미래기술이다. 20큐비트급 양자컴퓨터는 기존 컴퓨터가 백만회 순차 처리해야 하는 계산량을 한 번에 처리하는 계산성능을 갖는다.
세계 주요국들은 양자컴퓨팅을 전략기술로 분류해, 국가적 연구역량을 집중하고 있으며 글로벌 대기업, 기술벤처, 국가연구소와 주요 대학의 막대한 시설과 인력, 연구비가 동원되고 있다. 우리나라 정부도 양자기술을 10대 전략기술의 하나로 선정해 투자를 확대하고 있다.
소형(20~50큐비트급)의 양자컴퓨터가 속속 개발되고 있는 현시점에서, 가장 중요한 이슈 중 하나는 `디지털컴퓨팅 알고리즘으로는 비효율적인 계산 문제(NP-문제로 분류됨)를 양자컴퓨터가 계산할 수 있는지'이다.
따라서, KAIST가 20큐비트급의 양자컴퓨터를 개발해 NP-완전문제를 계산했다는 것은 한국의 양자컴퓨팅 연구가 세계적 양자컴퓨터 개발경쟁에 진입하였음을 의미한다.
KAIST 물리학과 안재욱, 문은국 교수 연구팀은 리드버그 원자들을 이용해, 조합 최적화 문제를 계산하는 양자 단열 컴퓨팅 방식의 양자컴퓨터를 개발했다. KAIST 연구팀은 초고진공 공간에 배치한 극저온 리드버그 원자를 사용해, 20큐비트급 그래프의 조합 최적화 문제를 실험적으로 계산하는 데 성공했다.
KAIST 물리학과 김민혁, 김강흔 대학원생 연구원과 황재용 학부생 연구원이 참여한 이번 연구는 국제 학술지 `네이처 피직스(Nature Physics)' 6월 18권 7호에 출판됐다. (논문명 : Rydberg quantum wires for Maximum Independent Set problems).
한편 리드버그 원자란 높은 에너지 상태의 원자로서, 일반 원자보다 만 배 정도 큰 마이크로미터 크기의 지름을 갖고, 리드버그 원자들간의 상호작용은 일반 원자들보다 1022배 정도로 강하다.
양자 단열형 양자컴퓨팅은 양자 회로형(또는 양자디지털형), 측정기반형과 함께 범용양자컴퓨팅 방식으로 알려져 있다. 대표적인 양자 단열형 양자컴퓨터인 D-wave 社의 양자컴퓨터는 고정 큐비트를 사용한다는 결정적 단점이 있다. 하지만 KAIST의 리드버그 양자 단열형 양자컴퓨터는 재배치 또는 이동이 가능한 큐비트를 사용하기 때문에 주목을 받는다.
KAIST 리드버그 양자컴퓨터는 초고진공 상태에 최대 126개의 리드버그 원자들을 임의로 배치해 양자 단열형 양자컴퓨팅을 수행한다. 이번에 발표한 최근 연구에서는 꼭지점이 최대 20개인 그래프의 최대독립집합을 계산하는데 성공했다. 또한 원거리 꼭지점들을 잇는 리드버그 양자선 개념을 최초로 개발해 모든 꼭지점들을 임의로 연결하는 초기하학적 그래프를 계산할 수 있음을 보였다.
참고로, 디지털 컴퓨팅에서 모든 계산 문제들을 계산복잡도에 따라 P-문제(결정 다항)와 NP-문제(비결정적 다항)로 분류한다. 여행자 문제(Traveling Salesman Problem), 최대독립집합 문제 등으로 대표되는 NP-문제들은 디지털 컴퓨팅의 알고리즘으로는 효율적으로 계산할 수 없음이 잘 알려져 있다. 따라서, 양자컴퓨터가 NP-문제들을 계산할 수 있을지가 큰 관심사다.
최대독립집합 문제는 대표적인 NP-완전문제의 하나이며, 주어진 그래프(꼭지점과 간선의 집합)에서 서로 연결되지 않는 꼭지점들의 최대집합을 알아내는 계산 문제다. 그래프의 크기가 커지면, 디지털컴퓨팅 알고리즘으로는 계산량이 지수적으로 증가해 효과적인 계산을 할 수 없다. 이러한 문제를 효과적으로 계산하게 되면 산업적으로 물류, 생산관리, 작업관리, 네트워크 디자인 등에서 혁명적 경제가치를 창출하게 된다.
<그림 1>
<그림 1> 은 리드버그 양자선(각각 빨강, 주황, 노랑 꼭지점들)을 이용하여 간선으로 연결되지 않는 데이터 큐비트(하얀 꼭지점들)를 연결하는 3차원 큐비트 구조체의 모식도이다. 이 구조는 쿠라토프스키 그래프로 잘 알려진 K(3:3) 그래프이다. 참고로 쿠라토프스키 K(3:3)와 K(5) 그래프쌍은 상대적으로 만들기 쉬운 평면그래프와 조합하여 모든 그래프를 만들 수 있다. KAIST 연구진은 본 연구에서 K(3:3)와 K(5)를 실험적으로 최초 구현하였다.
연구를 주도한 KAIST 물리학과 안재욱 교수는 “이번 연구는 리드버그 양자컴퓨터의 활용 가능성을 보였다는 데 의의가 있다”라고 자평하며 “아직은 큐비트 개수가 충분하지 않지만, 차 단계 연구를 통해 실 활용이 가능한 꿈의 양자컴퓨터를 개발할 수 있을 것”이라는 포부를 밝혔다.
한편 이번 연구는 삼성미래기술재단과 한국연구재단의 지원으로 수행됐다.