Parallel variational quantum algorithms with gradient-informed restart to speed up optimisation in the presence of barren plateaus

위대한 양자 보물 찾기

당신은 거대하고 안개가 자욱한 산맥에서 가장 깊은 골짜기를 찾으려 한다고 상상해 보세요. 이것은 단순한 산맥이 아닙니다. 바로 "변분 양자 알고리즘(Variational Quantum Algorithm, VQA)"이라는 특별한 종류의 수학적 문제로 설계된, 최신형이자 가장 강력한 양자 컴퓨터에서 실행되는 지형입니다. 이 컴퓨터들은 화학, 물리학, 물류와 같은 까다로운 퍼즐을 일반 컴퓨터보다 훨씬 빠르게 해결할 수 있는 초스마트 탐험가와 같습니다. 하지만 여기에는 함정이 있습니다. 그들이 사용하는 지도는 종종 "바렌 플레이토(Barren Plateau, 황량한 고원)"로 가득 차 있다는 점입니다.

바렌 플레이토를 산봉우리가 아니라, 거대하고 평평하며 특징 없는 평원이라고 생각하세요. 일반적인 산을 걷고 있다면 땅의 경사를 느낄 수 있고 골짜기 아래로 향하는 길을 따라갈 수 있습니다. 하지만 바렌 플레이토 위에서는 지면이 너무 평평해서 당신의 나침반(즉, "그래디언트/기울기")이 제멋대로 돌거나 아무 방향도 가리키지 못합니다. 당신은 안개 속에 갇혀, 어디로 가는지 알 수 없는 발걸음을 옮치며 시간과 에너지를 낭비하게 됩니다. 이것은 매우 큰 문제입니다. 만약 컴퓨터가 이러한 평평한 지형에 갇히게 되면, 결코 "글로벌 옵티멈(Global Optimum, 전역 최적해)"—즉, 절대적인 최적의 해답—에 도달할 수 없습니다. 과학자들은 탐험가들을 이 평평한 지형에서 벗어나게 하여 다시 보물이 있는 경사면으로 되돌려 보내는 방법을 알아내기 위해 노력해 왔습니다.

논문의 핵심 아이디어: 무모한 탐험가 팀

이 논문은 "안개 속에 갇힌 문제"를 해결하기 위해 영리하면서도 약간은 혼란스러운 해결책을 제안합니다. 단 한 명의 탐험가를 산을 헤매게 하는 대신, 저자들은 여러 명의 탐험가 팀을 동시에 보내는 것을 제안합니다. 그들은 이를 **플레밍-비오트 과정(Fleming-Viot process)**이라는 생물학적 개념에서 영감을 얻은 "병렬 변분 양자 알고리즘"이라고 부릅니다.

이 시스템이 어떻게 작동하는지는 다음과 같은 재미있는 비유로 설명할 수 있습니다.

당신에게 골짜기 바닥을 찾는 10명의 탐험가 팀(논문에서는 10개의 입자를 사용함)이 있다고 상상해 보세요. 그들은 모두 산 아래로 내려가기 시작합니다. 규칙은 간단합니다. 만약 탐험가가 어느 방향이 아래인지 알 수 없는 평평하고 안개 낀 평지(바렌 플레이토)에 발을 들이면, 그 탐험가는 즉시 "사망(중단)" 처리됩니다. 하지만 그들은 그냥 사라지는 것이 아닙니다!

대신, 팀에게는 마법 같은 리스폰(부활) 메커니즘이 있습니다. 탐험가가 길을 잃으면, 그들은 즉시 새로운 장소로 순간 이동합니다. 논문은 이 새로운 장소를 선택하는 두 가지 방법을 테스트했습니다:

1. "따라쟁이" 전략 (Exploitation, 착취): 길을 잃은 탐험가는 현재 성공적으로 움직이고 있는 다른 팀원이 서 있는 정확한 위치로 순간 이동합니다. 저자들은 만약 그 팀원이 여전히 움직이고 있다면, 그곳은 평지가 아니라 경사가 있는 곳임이 분명하다고 기대합니다.
2. "롤러코스터" 전략 (Exploration, 탐색): 길을 잃은 탐험가는 지도상의 완전히 무작위적이고 새로운 장소로 순간 이동합니다. 이것은 무모한 추측이지만, 운 좋게 해답 바로 옆에 착륙할 수도 있습니다.

저자들은 탐험가들을 끊임없이 재활용하고 새로운 곳으로 보내는 것이, 단 한 명의 탐험가(또는 포기하지 않고 계속 뱅뱅 도는 팀)보다 시간을 낭비할 가능성이 훨씬 낮다고 제안합니다.

연구 결과: 탐색 속도의 가속화

저자들은 단순히 이 방법이 작동할 것이라고 추측만 한 것이 아니라, 수학적 모델을 구축하고 시뮬레이션을 실행하여 이를 증명했습니다.

먼저, 그들은 수학적 모델을 만들었습니다. 넓은 영역이 평평하고 쓸모없는 부분(바렌 플레이토)인 지형에서, "시뮬레이티드 어닐링(Simulated Annealing)"이라는 표준 방식을 사용하는 단일 탐험가는 매우 오랫동안 갇혀 있게 된다는 것을 보여주었습니다. 그러나 그들의 팀 기반 방식(플레밍-비오트)은 훨씬 더 빠르게 골짜기 바닥을 찾을 것으로 예측되었습니다. 평평하고 쓸모없는 땅이 많을수록, 이 방법의 이점은 더 커집니다. 이는 "지도의 80%가 안개라면, 포기하지 않고 계속 걷는 한 사람보다 계속 리셋하며 움직이는 팀이 훨씬 낫다"는 말과 같습니다.

이를 테스트하기 위해 두 가지 유형의 실험을 수행했습니다:

1. 합성 산맥 (Synthetic Mountains): 특정 양의 "안개"(25%, 50%, 80%의 면적)를 가진 컴퓨터 생성 가상 지형을 만들었습니다.
2. 맥스 컷 문제 (Max-Cut Problem): QAOA라는 양자 알고리즘을 사용하여 8개 노드로 구성된 그래프에서 "맥스 컷" 문제(네트워크의 노드들을 두 그룹으로 나누어 연결을 최대화하는 문제)에 이 방법을 적용했습니다.

결과:
시뮬레이션 결과, 그들의 팀 기반 접근 방식이 표준적인 "단일 탐험가" 방식보다 일관되게 우수한 성능을 보였습니다.

• 더 나은 결과: 팀은 실제 최적의 답에 더 가까운 해답을 찾아냈습니다.
• 더 빠른 속도: 안개(바렌 플레이토)가 많은 합성 테스트(80%)에서, 팀은 표준 방식이 끝까지 갇혀 있곤 했던 것(50단계)에 비해 약 절반의 시간(약 25단계) 만에 해답을 찾아냈습니다.
• 일관성: 결과가 더 신뢰할 수 있었습니다. "단일 탐험가" 방식은 운이 좋기도 했지만 완전히 길을 잃기도 하는 등 기복이 심했던 반면, 팀 방식은 꾸준했습니다.

흥미롭게도, 논문은 "롤러코스터" 전략(무작위 지점으로 순간 이동)이 "따라쟁이" 전략(다른 사람을 복제)보다 약간 더 효과적이라는 것을 발견했습니다. 이는 지면이 완전히 평평하고 혼란스러울 때는, 누군가를 따라 하기보다는 완전히 새로운 구역으로 과감하게 추측하며 이동하는 것이 더 낫다는 것을 시사합니다.

결론

이 논문은 양자 컴퓨팅의 문제를 영원히 "해결했다"고 주장하는 것이 아닙니다. 대신, 현재 양자 컴퓨터의 속도를 늦추는 까다롭고 평평한 지형을 항해하는 유망한 새로운 방법을 제안합니다. 병렬 탐색을 수행하며, 언제 멈추고 언제 새로 시작해야 할지 아는 팀을 사용함으로써, 우리는 유용한 양자 해답을 찾는 속도를 높일 수 있을 것입니다. 이는 때때로 최선의 답을 찾는 과정에서, 멈춰 서서 완전히 다른 길을 시도하는 것이 가장 현명한 선택이 될 수 있음을 상기시켜 줍니다.