러시아 과학자들이 구글 양자 컴퓨팅 알고리즘의 근본적인 한계를 지적했다.

구글(Google)은 양자역학 효과를 사용해 데이터 처리 속도를 향상시키는 양자 프로세서를 개발하기 위해 경쟁하고 있다.

최근 구글은 현실적인 노이즈가 있을 때 작동하는 새로운 양자 강화 알고리즘을 고안했다. 소위 양자 근사 최적화 알고리즘( quantum approximate optimisation algorithm, QAOA)은 노이즈 내성 양자 알고리즘 개발의 초석이다.

QAOA에서 구글이 채택한 이 접근 방식은 광범위한 상업적 관심을 불러 일으켰다. 전 세계 연구 기관들도 새로운 응용 프로그램 탐색을 시작했다. 그러나 구글의 QAOA 알고리즘의 궁극적 성능 제한에 대해서는 알려진 바가 거의 없다.

그래프는 문제 밀도가 증가하는 임의로 생성된 MAX-SAT 인스턴스에서 고정 깊이 QAOA 회로의 성능 (QAOA 옵티마와 정확한 옵티마의 차이)을 나타낸다. 깊이가 더 큰 버전은 더 나은 성능을 달성하지만 여전히 도달 가능성이 부족하다. credit : Physical Review Letters.

러시아 모스크바에 위치한 스콜코브 과학기술연구소(Skolkovo Institute of Science and Technolog, Skoltech)의 딥 퀀텀 랩(Deep Quantum Laboratory) 과학자 팀이 이 현대적인 과제를 해결했다.

제이콥 비에몬트(Jacob Biamonte) 교수가 이끄는 Skoltech 연구팀은 구글이 채택한 접근 방식에서 근본적인 한계로 보이는 것을 발견하고 정량화했다.

피지컬리뷰레터스(Physical Review Letters)에 발표한 연구결과*에서 저자들은 소위 도달 가능성 결손(reachability deficits)의 발견에 대해 상세하게 설명했다. 저자는 이러한 결손이 QAOA가 문제에 대한 해결책을 근사화하는 능력에 근본적인 한계를 두고 있음을 보여준다.

Skoltech 팀의 연구 결과에 따르면 변형 QAOA 양자 알고리즘의 명확한 한계가 제시됐다. QAOA 및 기타 변형 양자 알고리즘은 내부 양자-고전적 피드백 프로세스로 인해 알려진 수학적 기법을 사용해 분석하기가 매우 어려운 것으로 입증됐다.

즉, 주어진 양자 계산은 정해진 시간 동안만 실행될 수 있다. 이 정해진 시간 내에, 고정 된 수의 양자 연산이 실행될 수 있다. QAOA는 목적 함수를 최소화하기 위해 점점 더 최적의 근사치 시퀀스를 형성함으로써 이러한 양자 연산을 반복적으로 활용하려고 한다.

연구는 이 과정에 새로운 한계를 두었다. 저자들은 고정 깊이 양자 회로에 대한 최적의 솔루션을 근사화하는 QAOA의 능력이 근본적으로 “밀도”문제에 의존한다는 것을 발견했다. MAX-SAT라는 문제의 경우, 소위 밀도는 문제의 제한과 변수 개수의 비율로 정의할 수 있다. 이를 단절 밀도라고도 한다.

연구 결과, QAOA 실행 시간에 관계없이 보장된 성공을 근사화할 수 없는 최적 솔루션에서 문제가 있는 고밀도 인스턴스를 발견했다.

* Reachability Deficits in Quantum Approximate Optimization