Reductions of QAOA Induced by Classical Symmetries: Theoretical Insights and Practical Implications

양자 컴퓨팅이라는 신흥 분야에서 과학자들은 가장 강력한 고전적 슈퍼컴퓨터조차 해결하기 어려운 복잡한 문제들을 풀기 위해 노력하고 있습니다. 이 과업을 위한 가장 유망한 도구 중 하나는 양자 근사 최적화 알고리즘(QAOA)이라 불리는 알고리즘입니다. 이 알고리즘을 방대한 가능한 답들의 풍경을 탐색하여 가장 최선의 답을 찾아내는 정교한 검색 엔진이라고 생각해보십시오. 이 알고리즘이 작동하려면 섬세한 균형이 필요합니다. 즉, 탐색은 완벽한 해답을 찾을 수 있을 만큼 충분히 넓어야 하지만, 컴퓨터가 길을 잃고 신호가 감지하기 어려울 정도로 약해질 만큼 혼란스러워져서도 안 됩니다. 이 과정의 주요 장애물은 문제가 커짐에 따라 알고리즘의 학습 능력이 급격히 저하되어 훈련을 어렵게 만드는 현상입니다. 연구자들은 많은 현실 세계의 문제들이 숨겨진 대칭성, 즉 문제의 특정 부분을 서로 바꾸어도 최종 결과가 변하지 않는 패턴을 가지고 있다는 것을 오래전부터 알고 있었습니다. 고전 컴퓨팅에서 이러한 패턴을 인식하는 것은 문제의 크기를 줄이는 간단한 방법입니다. 그러나 지금까지는 이러한 단순화를 양자 알고리즘에 적용하는 것이 물리적 구성 요소를 단 한 단위 줄이는 정도의 아주 적은 공간만 절약할 뿐, 기계가 사고하는 방식 자체를 근본적으로 바꾸지는 못할 것이라고 널리 추정되어 왔습니다.

새로운 연구는 이러한 가설에 도전하며, 문제를 양자 컴퓨터에 입력하기 전에 어떻게 단순화하느냐가 기계의 내부 논리를 완전히 재구성할 수 있음을 밝혀냈습니다. 연구진은 네트워크의 점들을 두 그룹으로 나누어 그 사이의 연결을 최대화하는 MaxCut 문제라는 고전적인 퍼즐에 집중했습니다. 이 문제는 특정한 대칭성을 가지고 있는데, 모든 점을 한 그룹에서 다른 그룹으로 뒤집더라도 해답은 정확히 동일하게 유지됩니다. 고전 컴퓨터에서 이 대칭성을 깨기 위해 한 점을 특정 그룹에 고정하는 것은 단순히 중복된 옵션을 제거하는 사소한 단계에 불과합니다. 하지만 연구팀은 양자 컴퓨터의 경우, 이와 동일한 단순한 단계가 변혁적이라는 사실을 발견했습니다. 네트워크의 단 하나의 점을 고정함으로써, 그들은 단순히 변수를 하나 제거한 것이 아니라, 솔루션 공간을 통과하는 알고리즘의 움직임을 지배하는 수학적 구조를 근본적으로 변화시켰습니다. 어떤 점을 선택하느냐에 따라, 이 작은 변화는 나머지 전체 가능성의 공간을 열어주어 컴퓨터가 필요로 하는 모든 해답에 도달할 수 있게 하거나, 혹은 작업의 복잡성을 극도로 단순화하여 지수적으로 어려웠던 문제를 이차 함수적으로 성장하는 문제로 바꿀 수도 있었습니다.

연구진은 이러한 감소가 단순히 부품 하나를 아끼는 문제가 아님을 입증했습니다. 대신, 이는 양자 알고리즘의 행동을 설계하는 설계 도구로서 작용합니다. 그들은 특정 유형의 네트워크에 대해, 단 하나의 점을 고정하는 것이 알고리즘의 기저에 깔린 대수적 복잡성을 관리하기 매우 까다로운 지수적 규모에서 훨씬 다루기 쉬운 이차 함수적 규모로 붕괴시킨다는 것을 증명했습니다. 이러한 변화가 중요한 이유는 알고리즘의 내부 구조의 복잡성이 '배런 플래토(barren plateaus)'라고 알려진 주요 훈련 문제, 즉 알고리즘의 학습 신호가 사라지는 현상과 직접적으로 연결되어 있기 때문입니다. 연구진은 적절한 점을 고정함으로써, 해결하려는 실제 문제는 바꾸지 않으면서도 알고리즘을 훨씬 더 훈련하기 쉽게 만들 수 있음을 보여주었습니다. 또한, 연결된 모든 네트워크에 대해, 이 단순화가 완벽하게 작동하는 약간 더 큰 버전의 네트워크를 구축할 수 있음을 보여주었으며, 이를 통해 알고리즘이 높은 정밀도로 최적의 해답에 도달할 수 있도록 보장했습니다.

이러한 아이디어를 테스트하기 위해 연구팀은 중심 허브에서 여러 경로가 바깥쪽으로 뻗어 나가는 형태인 스파이더 그래프(spider graphs)라고 불리는 특정 계열의 네트워크 형태를 조사했습니다. 표준적인 미축소 버전의 문제에서 이 그래프들의 수학적 복량은 점의 개수에 따라 지수적으로 증가하여 해결하기 매우 어렵습니다. 그러나 연구진이 중심 허브를 고정하자, 그래프는 독립적인 경로들로 분리되었고, 양자 알고리즘의 복잡도는 이차 함수적 성장률로 떨어졌습니다. 이는 단 하나의 단순한 결정이 문제의 성격을 다루기 힘든 것에서 다룰 수 있는 것으로 변화시킨 구체적인 사례를 제공했습니다. 연구팀은 또한 명확한 대칭성이 없는 다양한 불규칙 네트워크에 대해서도 수치 실험을 수행했습니다. 이 시뮬레이션에서 그들은 적절한 고정 지점을 선택하는 것이 원래의 미축소 버전에 비해 일관되게 더 훈련하기 쉬운 알고리즘과 더 강한 학습 신호를 결과로 가져온다는 것을 발견했습니다.

이러한 발견은 문제를 양자 컴퓨터에 표현하는 방식의 선택이 기존에 생각했던 것보다 훨씬 더 강력하다는 것을 시사합니다. 고전적 단순화가 단순히 공간을 절약하는 방법으로 여겨졌던 반면, 이 연구는 그것이 양자 역학적 동역학을 재설계하여 알고리즘의 표현력과 훈련 가능성을 제어할 수 있음을 보여줍니다. 연구진은 과학자들이 양자 컴퓨터를 실행하기 전에 간단한 그래프 분석을 사용하여 최적의 축소 시작점을 선택할 수 있는 실용적인 워크플로우를 제안합니다. 이 접근 방식은 알고리즘이 많은 해답을 탐색하는 능력과 그로부터 학습하는 능력 사이의 어려운 절충안을 헤쳐 나가는 새로운 방법을 제시합니다. 변수를 신중하게 선택함으로써, 연구자들은 잠재적으로 알고리즘을 배런 플래토로부터 멀어지게 하고 고품질의 해답으로 유도할 수 있으며, 이를 통해 단순한 고전적 관찰을 강력한 양자 우위의 지렛대로 바꿀 수 있습니다.