양자 컴퓨터 양자 이점 입증 새로운 접근

양자 컴퓨팅의 주요 목표 중 하나는 양자 기계가 고전 컴퓨터보다 더 빠르게 계산 작업을 수행할 수 있음을 실험적으로 입증하는 것이다.

프랑스와 영국에 기반을 둔 연구팀은 이제 간단한 양자 광자 실험 설정을 사용해 이를 수행했다. 그들의 연구는 양자 컴퓨터가 소위 대화형 증명 프로토콜과 솔루션에 대한 최소한의 확인되지 않은 정보만을 사용하여 NP-완전(NP-complete)으로 분류된 문제에 대한 솔루션을 검증(NP verification)할 수 있음을 보여준다.

이 작업은 양자 이점(quantum advantage)을 입증하는 데 있어 최근 몇 가지 이정표 중 하나다. 2019년 구글(Google)은 53 개의 프로그래밍 가능한 초전도 큐비트(양자 비트) 설정을 통해 최초로 양자 우위 달성을 주장했다. 최근에 중국 과학자팀은 레이저를 활용한 광학 기반 양자 컴퓨터로 고전 컴퓨터로는 불가능에 가까운 작업인 “보손 샘플링(boson sampling)”을 성공적으로 수행했다고 발표했다.

이러한 앞선 결과와 달리 네이처 커뮤니케이션즈(Nature Communications)에 발표된 새로운 연구는 양자 이점을 입증할 뿐만 아니라 보안 양자 클라우드 컴퓨팅(Quantum cloud computing)과 같은 응용 프로그램에서도 유용할 것이라고 약속한다.

NP 검증

NP-complete 문제는 효율적으로 해결하기 어렵지만 일단 솔루션을 찾으면 간단하게 검증할 수 있다. 프랑스 국립 과학 연구 센터(CNRS)와 에든버러 대학(University of Edinburgh) 연구팀이 중점을 두었던 과제는 그 사이의 중간 지점을 차지한다. 해당 솔루션의 일부만 제공되었을 때 NP 완전 문제에 대한 솔루션을 검증하는 것이다.

부분 솔루션 또는 증명을 포함하는 메시지의 크기가 고정되면 솔루션을 확인하는 기존 프로토콜이 메시지 크기에 따라 기하급수적으로 확장되는 시간이 걸린다는 것을 알 수 있다. 반대로 양자 프로토콜의 경우 스케일링은 다항식이다. 즉, 메시지 크기가 큰 경우 양자 컴퓨터는 솔루션을 확인하는 데 몇 분이 걸리지만 기존 컴퓨터는 몇 년이 걸릴 수 있다.

연구자들이 이를 증명하기 위해 사용하는 알고리즘은 상호 작용 증명 프로토콜로 알려져 있다. 여기에서 실험 설정의 한 구성 요소는 결맞음 광 펄스(coherent light pulses)를 사용해 양자 상태의 형태로 NP- 완전 문제에 대한 부분 솔루션을 보내는 “입증자(prover)” 역할을 한다. 두 번째 구성 요소는 “검증자(verifier)”의 역할을 수행해 주어진 제한된 정보를 기반으로 솔루션이 올바른지 여부를 높은 정확도로 결정한다. 검증 자의 예상 정확도와 상호 작용을 통해 전달될 수 있는 정보의 양 측면에서 프로토콜의 속도 및 효율성에 특정 경계가 설정되면 양자 알고리즘이 기존 시도를 훨씬 능가한다는 것을 입증할 수 있다.

양자 클라우드 컴퓨팅

양자 알고리즘이 NP- 완전 문제에 대한 솔루션을 효율적으로 검증할 수 있음을 보여줌으로써 결과는 안전한 원격 양자 컴퓨팅의 새로운 응용 프로그램을 가능하게 수 있다. 예를 들어 초보적인 양자 기계를 사용하는 클라이언트는 전체 솔루션에 액세스하지 않고도 강력한 양자 서버에서받은 정보를 확인할 수 있다. 이러한 증명 시스템은 미래의 양자 인터넷에서 보안 식별, 인증 또는 블록 체인과 같은 프로토콜에 기여할 수 있다.

에든버러대 연구원이자 논문 공동 저자 니라 쿠마르(Niraj Kumar)는 “데이터 프라이버시 및 보안 컴퓨팅에 대한 관심이 증가하는 현재 시대에 이번 데모는 양자 컴퓨터가 보안 솔루션을 달성하는 데 있어 기존 컴퓨터보다 성능이 우수하다는 또 다른 강력한 증거를 제공한다”고 밝혔다.

* NP-완전

NP-완전(NP-complete)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다.

* NP

NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(Non-deterministic Polynomial time)의 약자이다.

*Centrone, F., Kumar, N., Diamanti, E. et al. Experimental demonstration of quantum advantage for NP verification with limited information. Nat Commun 12, 850 (2021). https://doi.org/10.1038/s41467-021-21119-1