우리 학교 물리학과 안재욱, 문은국 교수 공동 연구팀이 20큐비트급 리드버그* 양자 컴퓨터를 개발해 계산과학의 난제인 최대독립집합 문제를 계산했다고 밝혔다. 
양자 컴퓨팅의 핵심 중 하나는 양자 상태를 정확하게 조절하는 것이다. 다만 물리적으로 바로 인접하지 않은 큐비트끼리의 상호작용을 통제하기 어려웠다. 연구팀은 서로 떨어져 있는 원자들을 ‘양자선’으로 연결하여 이 문제를 해결했다. 비유하자면 가까운 원자들이 모두 ‘손에 손을 잡게' 하여 멀리 떨어진 원자끼리도 상호작용이 가능하게 했다. 

 연구팀은 초고진공 공간에 극저온 리드버그 원자를 배치하고, 언급한 양자선 개념을 도입했다. 최종적으로는 20큐비트급 그래프의 조합 최적화 문제를 실험적으로 계산하는 데 성공했다.

양자 컴퓨터의 역사와 발전

 양자 컴퓨터는 양자 중첩과 양자 얽힘과 같은 양자역학적 현상을 이용하여 자료를 처리하는 계산 기계다. 양자 컴퓨터는 기존의 디지털컴퓨터가 다항 시간 안에 해결하지 못하는 문제를 빠르게 해결할 수 있으리라 전망된다.

 이는 양자 컴퓨터의 정보 단위인 큐비트가 보이는 특성 때문이다. 기존 컴퓨터의 정보 단위인 비트의 경우 1비트당 1개의 값만 가진다. 이에 반해, 양자 컴퓨터의 정보 단위인 큐비트는 1큐비트당 0과 1의 상태를 동시에 가진다. 따라서 이론적으로는 비트에 비해 큐비트는 배로 빠르며, 큐비트 수가 증가할수록, 속도는 지수적으로 증가한다.

 양자 컴퓨터는 20세기 후반 리처드 파인만 등이 이론적으로 제안했고, 이후 2000년대에 들어서면서 세계적인 기업들이 상용화에 총력을 다하고 있다. 

 이러한 양자 컴퓨터의 발전은 크게 두 가지로 평가할 수 있다. 첫 번째는 ‘큐비트 수를 얼마나 많이 늘릴 수 있을 것인가’이다. 두 번째는 ‘얽힘과 같은 양자 상태를 얼마나 잘 구현할 수 있는가’이다. 특히 양자 상태의 정확한 구현을 위해서는 큐비트끼리의 자유로운 상호작용이 필수적이다. 하지만 대표적인 양자 단열형 양자 컴퓨터 중 하나인 D-wave 사의 양자 컴퓨터는 고정 큐비트를 사용한다는 결정적 단점이 있다.

소형 리드버그 양자 컴퓨터로 최대 독립집합 문제 해결

 연구팀의 리드버그 양자 단열형 양자 컴퓨터는 유동적인 큐비트를 사용하기 때문에 주목받는다. 다시 말해 큐비트의 재배치나 이동이 가능하다. 
연구팀의 리드버그 양자 컴퓨터는 초고진공 상태에 최대 126개의 리드버그 원자들을 임의로 배치해 양자 단열형 양자 컴퓨팅을 수행한다. 본 연구에서는 이를 이용하여 꼭짓점이 최대 20개인 그래프의 최대독립집합을 계산하는데 성공했다. 

 계산 문제는 그 복잡도에 따라 P-문제(결정 다항)와 NP-문제(비결정적 다항)로 분류된다. 여기서 NP-문제들은 기존의 컴퓨팅 알고리즘으로는 효율적으로 계산할 수 없다고 알려져 있다. 최대독립집합 문제는 대표적인 NP-문제 중 하나로, 주어진 그래프(꼭짓점과 간선의 집합)에서 서로 연결되지 않는 꼭짓점들의 최대집합을 알아내는 문제다. 계산할 그래프의 크기가 커지면, 디지털컴퓨팅 알고리즘으로는 계산량이 지수적으로 증가해 효과적인 계산을 할 수 없다. 

 연구팀은 원거리 꼭지점들을 잇는 리드버그 양자선 개념을 최초로 개발했다. 이는 가까운 원자들을 옆에 있는 원자들과 연결시켜, 멀리 떨어진 원자끼리도 상호작용이 가능하게 한다. 연구팀은 멀리 떨어진 원자끼리의 모든 꼭짓점들을 임의로 연결하는 초기하학적 그래프를 계산할 수 있음을 보였고, 해당 구조를 활용해 최종적으로 최대독립집합 문제를 실험적으로 계산하는 데 성공했다.

 한편, 학부생 신분으로 연구에 참여한 황재용 학우는 “처음에 연구실에 왔을 때 아무것도 이해할 수 없었지만 따라다니며 계속 질문하다보니 성장한 것 같다”며 다른 학우들의 도전을 독려했다. 김강흔 박사과정은 “좋은 연구실은 따로 존재하는 것이 아니다. 본인과 얼마나 잘 맞는지를 기준으로 생각해야 한다”는 조언을 전했다. 김민혁 연구원은 “뭐든지 혼자 앓기보다는 같이 나누는 게 효과적인 것 같다. 연구도 동일하다”고 덧붙였다. 

리드버그 원자*
높은 에너지 상태의 원자로서, 일반 원자보다 만 배 정도 큰 마이크로미터 크기의 지름을 갖고, 리드버그 원자들 간의 상호작용은 일반 원자들보다 1022배 정도로 강하다.