← 최신 논문
⚛️ 양자물리학

Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery

본 논문은 더 적은 상호작용을 갖는 MinLA 기반 대리 모델을 구축함으로써 하드웨어 네이티브가 아닌 그래프에서의 QAOA 회로 깊이를 줄이고, 이후 고전적 정밀화 전략을 통해 원래의 MAX-CUT 문제에 대한 근사 최적해를 복구하는 하이브리드 양자-고전 워크플로우를 제안한다.

원저자: K. Bharati, Nathan Earnest-Noble, Ritajit Majumdar

게시일 2026-11-16
📖 5 분 읽기🧠 심층 분석

원저자: K. Bharati, Nathan Earnest-Noble, Ritajit Majumdar

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

유용한 양자 컴퓨터를 구축하기 위한 경쟁 속에서, 과학자들은 현재 어려운 중간 지대를 항해하고 있습니다. 그들은 전통적인 컴퓨터보다 훨씬 빠르게 특정 계산을 수행할 수 있는 기계를 보유하고 있지만, 이 기계들은 여전히 취약하고 규모가 제한적입니다. 이들을 사용하는 가장 유망한 방법 중 하나는 수백만 개의 선택지 중에서 최적의 배치를 찾는 최적화 문제라고 알려진 복잡한 퍼즐을 해결하는 것입니다. 이를 수행하기 위한 주요 방법은 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm)이라 불립니다. 이 알고리즘은 한 번에 많은 가능한 답을 나타내는 양자 상태를 준비한 다음, 이를 정교하게 다듬어 최선의 답을 찾는 방식으로 작동합니다. 그러나 큰 장애물이 존재합니다. 실제 양자 칩은 모든 유형의 퍼즐을 직접 처리할 수 있도록 설계되지 않았습니다. 칩은 미세한 프로세싱 단위들 사이에 특정하고 희소한 연결 구조를 가지고 있는 반면, 흥로운 많은 문제들은 이 구조에 맞지 않는 조밀한 연결망을 포함하고 있습니다. 맞지 않는 문제를 칩에 강제로 적용하기 위해, 엔지니어들은 정보가 먼 단위들 사이를 이동하도록 하는 추가적인 단계들을 삽嵌入해야 하며, 이 과정은 복잡성과 노이즈를 더합니다. 이 노이즈는 답을 찾기도 전에 섬세한 양자 정보를 파괴하여, 기계가 본래 해결하고자 했던 문제를 해결할 수 없게 만듭니다.

IBM 리서치와 인도 공과대학교 마드라스(IIT Madras)의 연구진은 이러한 병목 현상을 우회하여 양자 컴퓨터가 이전보다 더 크고 복잡한 그래프 문제를 해결할 수 있게 하는 새로운 전략을 개발했습니다. 156-큐비트 프로세서에서 테스트된 이들의 접근 방식은 양자 기계가 할 수 있는 것과 고전 컴퓨터가 수정할 수 있는 것 사이의 균형을 맞추는 영리한 2단계 워크플로우를 포함합니다. 전체 복잡한 문제를 한꺼번에 칩에 강제로 주입하는 대신, 연구팀은 먼저 칩의 물리적 한계 내에 들어맞는 단순화된 '대리(surrogate)' 버전의 문제를 만듭니다. 그들은 문제의 구성 요소들을 재정렬하여 가장 중요한 연결들이 짧고 국부적이 되도록 함으로써 이를 달성하며, 오류를 유발하는 라우팅 단계를 과도하게 늘리지 않고 실행할 수 있는 연결들만을 선택합니다. 이를 통해 양자 컴퓨터는 훨씬 더 짧고 깨끗한 회로를 실행하고 일련의 후보 솔루션들을 생성할 수 있습니다.

진정한 혁신은 그 다음에 일어나는 일에 있습니다. 연구진은 단순히 양자 컴퓨터의 출력을 최종 답으로 받아들이지 않습니다. 대신, 그들은 단순화된 양자 회로에서 생성된 가장 좋은 후보 솔루션들을 가져와 고전 컴퓨터에 입력합니다. 그러면 이 고전 컴퓨터는 단순화 과정에서 누락된 정보를 복구하기 위해 엄격하고 단계적인 정교화 과정을 수행합니다. 이 컴퓨터는 후보들을 원래의 전체적이고 복잡한 문제와 대조하여 평가하고, 거의 완벽한 상태에 도달할 때까지 체계적으로 개선합니다. 양자 샘플링의 무거운 작업과 답의 최종 다듬기 작업을 분리함으로써, 연구팀은 최대 100개의 정점(vertex)을 가진 클래식 그래프 문제인 MAX-CUT 문제를 성공적으로 해결했습니다. 이 그래프들은 너무 조밀하여 하드웨어에서 직접 실행하기에는 무리가 있었으나, 이 하이브리드 방식은 이론적인 최적의 답에 거의 근접한 솔루션을 만들어냈습니다.

이 방법의 핵심은 문제 데이터가 양자 칩에 도달하기 전, 특정한 방식으로 조직되는 방식에 달려 있습니다. 연구진은 그래프의 정점들을 재정렬하기 위해 '최소 선형 배치(Minimum Linear Arrangement)'라는 수학적 기법을 사용했습니다. 문제를 도시들이 도로로 연결된 지도라고 상상해 보십시오. 목표는 도시들을 두 그룹으로 나누어 그룹 사이를 가로지르는 도로의 수를 최대화하는 것입니다. 표준 양자 칩에서 도시 간의 연결은 고정되어 있고 희소합니다. 만약 문제 속의 도시들이 지도상에서 서로 멀리 떨어져 있다면, 칩은 그들을 연결하기 위해 길고 구불구불한 다리를 건설해야 하며, 이는 오류를 유발합니다. 연구진의 정렬 기술은 서로 많이 연결된 도시들이 시퀀스 상에서 바로 옆에 위치하도록 재배치합니다. 이를 통해 그들은 오류를 일으키기 쉬운 많은 단계를 요구하는 긴 연결들을 버리고, 모두 가까이 모여 있는 '밴드(band)' 형태의 상호작용들을 선택할 수 있습니다.

이 선택 과정은 회로의 깊이(depth), 즉 양자 컴퓨터가 연속적으로 수행해야 하는 단계의 척도에 대한 엄격한 예산에 의해 안내됩니다. 연구진은 특정 하드웨어의 이 깊이 제한 내에 들어갈 수 있는 가장 넓은 범위의 연결 밴드를 결정했습니다. 그들은 일부 연결이 일시적으로 무시되더라도 모든 도시가 단순화된 모델의 일부로 남아 있도록 보장했습니다. 이는 양자 컴퓨터가 실제로 실행할 수 있는 문제의 에너지 지형인 '대리 해밀토니안(surrogate Hamiltonian)'을 생성했습니다. 이 단순화된 회로를 IBM 프로세서에서 실행했을 때, 전체 문제를 실행하려고 할 때와 비교하여 필요한 단계 수를 절반 이상 줄이면서도 원래 그래프 구조의 상당 부분을 유지할 수 있음을 발견했습니다. 수천 개의 연결을 가진 가장 큰 그래프들의 경우, 이 방법은 상호작용의 약 절반을 유지했는데, 이는 그래프를 단순한 사슬 형태로 축소해 버리는 기존 기술로는 불가능했던 성과였습니다.

그 후 양자 컴퓨터는 이 단순화된 지형으로부터 수천 개의 잠재적 솔루션들을 샘플링했습니다. 회로가 더 짧고 깨끗했기 때문에, 이들이 생성한 솔루션은 노이즈가 많은 전체 깊이 시도에서 얻은 솔루션보다 품질이 높았습니다. 그러나 이 솔루션들은 여전히 불완전한 그림에 기반하고 있었습니다. 이를 해결하기 위해 팀은 두 가지 뚜렷한 고전적 복구 전략을 채택했습니다. 첫 번째는 각 도시를 개별적으로 살펴보고, 그렇게 하는 것이 전체 가로지르는 도로의 수를 개선한다면 해당 도시의 그룹 할당을 바꾸는 탐욕적(greedy) 접근 방식이었습니다. 두로, 더 정교한 두 번째 전략은 도시들의 쌍을 살펴보고 네트워크의 최소 컷(minimum cut)을 찾는 것과 관련된 기술을 사용하여, 이들이 함께 재배치될 최적의 방법을 찾는 최적화 문제를 해결했습니다. 이 두 번째 방법은 단일한 변화로는 도움이 되지 않지만 협력적인 변화로는 도움이 되는 '지역적 함정(local traps)'에서 벗어날 수 있게 해주었습니다.

이 하이브리드 워크플로우의 결과는 놀라웠습니다. 100개의 정점을 가진 그래프에 대해, 단순화된 후의 순수 양자 출력물은 이미 꽤 괜찮은 수준이었습니다. 하지만 고전적 복구 단계 이후, 솔루션의 품질은 극적으로 뛰어올랐습니다. 복구 후 발견된 최상의 솔루션들은 거의 0.997의 근사 비율(approximation ratio)을 달로 달성했는데, 이는 절대적인 최적의 답과 0.3% 이내의 차이밖에 나지 않음을 의미합니다. 이는 양자 컴퓨터가 원래 문제에 필요한 전체 상호작용을 한 번도 실행하지 않았음에도 불구하고 달성된 결과였습니다. 연구진은 이 개선이 전적으로 고전적 정교화로부터 온 것임을 확인했는데, 복구 과정은 양자 프로세서에서 추가적인 시간을 소요하지 않고 각 후보 솔루션에 대해 독립적으로 실행되었기 때문입니다.

이 연구는 현재의 양자 하드웨어의 한계가 거대하고 복잡한 문제를 해결하는 것을 반드시 막지는 않는다는 점을 보여줍니다. 하드웨어의 제약을 인정하고 이를 존중하는 워크플로우를 설계함으로써, 연구진은 단순화된 양자 실행으로부터 유용한 신호를 추출하고 이를 고전적 계산을 통해 증폭할 수 있음을 보여주었습니다. 이 방법은 특히 확장성이 뛰어납니다. 양자 프로세서가 개선되어 더 깊은 회로를 견딜 수 있게 되면, 더 많은 원래 문제를 포함하도록 상호작용의 '밴드'를 넓힐 수 있어 고전 컴퓨터의 작업량을 줄일 수 있습니다. 반대로, 오늘날의 노이즈가 많은 기계들에 대해 이 방법은 실질적인 경로를 제공하며, 하드웨어 인지적 단순화와 고전적 복구의 결합이 이전에는 도달할 수 없었던 고품질의 솔루션을 제공할 수 있음을 입증했습니다. 이 연구는 양자 최적화의 미래가 완벽하고 오류 없는 기계를 기다리는 데 있는 것이 아니라, 현재 가용한 불완전한 도구들을 효과적으로 다룰 줄 아는 스마트한 하이브리드 시스템을 구축하는 데 있음을 확인시켜 줍니다.

연구 분야의 논문에 파묻히고 계신가요?

연구 키워드에 맞는 최신 논문의 일일 다이제스트를 받아보세요 — 기술 요약 포함, 당신의 언어로.

Digest 사용해 보기 →