⚛️ 양자물리학

QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts

본 논문은 제어된 $R_y$ 회전을 통해 그래프의 에지를 인코딩하는 시프트 위상(shift-phase) 회로인 QASPA-MaxCut를 소개하며, 다양한 무가중치 그래프에 대한 정밀 시뮬레이션을 통해, 고정 각도 접근 방식이 고전적 선택 단계를 포함함으로써 여러 번의 고전적 재시작을 사용하는 depth-one QAOA보다 성능이 우수함을 입증한다.

원저자: Dmytro Sapozhnyk

게시일 2026-11-05

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Dmytro Sapozhnyk

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

과학자들이 다르게 생각하는 기계를 만들기 위해 노력하고 있는 컴퓨팅의 조용한 구석에서, 맥스컷(Max-Cut) 문제라고 알려진 지속적인 과제가 존재합니다. 파티에 온 사람들이 두 개의 별도 방으로 나뉘어야 하는 상황을 상상해 보십시오. 목표는 사람들 사이의 우정이 방 내부가 아니라 두 방 사이에 최대한 많이 존재하도록 배치하는 것입니다. 이 단순해 보이는 작업은 사람의 수가 늘어남에 따라 가능한 배열의 수가 인간의 정신이 계산할 수 있는 속도보다 더 빠르게 폭발하기 때문에 믿기 힘들 정도로 어려워집니다. 수십 년 동안 고전 컴퓨터가 이를 해결하기 위한 최선의 도구였지만, 연구자들은 이제 새로운 종류의 기계인 양자 컴퓨터를 테스트하고 있습니다. 이 장치들은 아원자 세계의 기묘한 규칙을 사용하여 많은 가능성을 동시에 탐색합니다. 그러나 이러한 초기 양자 기계들은 여전히 취약하고 오류가 발생하기 쉬우므로, 과학자들은 그들에게 문제를 어떻게 풀도록 요청할지에 대해 매우 신중해야 합니다. 그들은 단순히 양자 기계가 좋은 답을 찾을 수 있는지뿐만 아니라, 그곳에 도달하기 위해 얼마나 많은 노력이 드는지, 그리고 그 노력이 우리가 이미 사용 중인 신뢰할 수 있는 컴퓨터와 비교했을 때 그만한 가치가 있는지도 알아야 합니다.

드미트로 사포즈닉(Dmytro Sapozhnyk)의 최근 연구는 작은 양자 컴퓨터에게 맥스컷 문제를 해결하도록 요청하는 두 가지 서로 다른 방식을 비교함으로써 이 질문을 다룹니다. 첫 번째 방법은 QAOA라고 불리는 잘 알려진 접근 방식으로, 이는 안개 낀 풍경 속에서 가장 높은 봉우리를 찾으려는 등산객과 같습니다. 등산객은 한 걸음을 내딛고, 높이를 확인한 다음, 그 정보를 바탕으로 경로를 조정합니다. 이 과정은 시행착오를 많이 필요로 하며, 컴퓨터는 매번 약간씩 다른 추측에서 시작하여 최선의 해결책을 우연히 발견하기를 바라며 동일한 계산을 반복해서 실행합니다. 저자가 개발하여 QASPA라고 이름 붙인 두 번째 방법은 다른 접근 방식을 취합니다. 등산객이 안개 속을 헤매는 대신, 이 방법은 높은 봉우리를 향해 직접적으로 이어지도록 설계된 특정한 경로를 구축합니다. 이는 변하지 않는 고정된 지침 세트를 사용하여, 문제 자체의 구조에 의존하여 양자 기계를 안내합니다.

연구진은 점들 사이의 연결 지도를 본질로 하는 작은 비가중치 그래프 모음에서 이 두 가지 방법을 테스트했습니다. 그들은 8개의 점을 가진 작은 시스템을 시뮬레이션했는데, 이는 표준 컴퓨터로 완벽하게 계산할 수 있을 만큼 작아서 노이즈나 오류의 간섭 없이 양자 기계가 정확히 무엇을 할지 볼 수 있게 해줍니다. 그들은 제한된 시도 횟수의 예산을 가지고 "등산객" 방식인 QAOA를 실행했습니다. 그들은 단 하나의 추측으로 시작하여 시도 횟수를 10회까지 점진적으로 늘려가며, 매번 답변이 얼마나 좋아지는지를 기록했습니다. 또한 그들은 단 한 번, 변하지 않는 단일한 지침 세트를 사용하여 고정 경로 방식인 QASло를 실행했습니다. 결과는 두 방법의 성능 차이를 명확히 보여주었습니다. 등산-객 방식인 QAOA는 더 많은 시도가 허용됨에 따라 최선의 배치를 찾아 높이 올라가며 점진적으로 개선되었습니다. 그러나 10번의 시도 후에도 그 평균 성능은 새로운 QASPA 방식의 단 한 번의 고정 실행보다 낮았습니다.

QASPA 방식이 눈에 띈 이유는 그것이 매번 절대적인 완벽한 답을 찾아냈기 때문이 아니라, 가장 가능성 높은 결과들의 맨 윗부분에 최선의 답들을 배치했기 때문입니다. 연구진이 QASPA가 생성한 가장 확률 높은 네 가지 결과들을 살펴보았을 때, 최선의 배치가 거의 항상 그 안에 있다는 것을 발견했습니다. 실제로 많은 테스트 케이스에서 최선의 배치는 단일한 가장 확률 높은 결과였습니다. 이는 사용자가 상위 몇 가지 제안 중에서 최선의 옵션을 선택하기만 하면, 다른 방식이 요구하는 복잡하고 시간이 많이 걸리는 탐색 과정을 거치지 않고도 훌륭한 결과를 얻을 수 있음을 의미합니다. 연구는 또한 물리적인 기계의 실제 제약을 시뮬레이션하여 컴퓨터가 제한된 횟수의 측정을 수행하도록 강제되었을 때도 이 결과가 유지되는지 확인했습니다. 이러한 제한 상황에서도 고정 경로 방식은 안정적이고 신뢰할 수 있었으며, 일관되게 높은 품질의 후보들을 전달했습니다.

연구진은 이러한 발견이 매우 작은 시스템의 시뮬레이션에서 나온 것이며, 이 방식이 아직 더 크고 실제적인 문제나 실제 양자 하드웨어에서 더 잘 작동할 것임을 증명하는 것은 아니라는 점을 주의 깊게 언급했습니다. 그들은 모든 상황에 대해 맥스컷 문제를 해결했다고 주장하거나, 그들의 방식이 고전 컴퓨터를 쓸모없게 만드는 마법의 탄환이라고 제안하지 않았습니다. 대신, 그들은 문제의 구조를 양자 지침에 직접 삽nel링하는 것이 반복적인 탐색 과정에 의존하는 것보다 더 효율적이라는 것을 보여주는 통제된 비교를 제공했습니다. 이 연구는 양자 회로를 설계할 때 문제의 특정 모양을 존중한다면, 오늘날의 불완전한 기계에서도 더 적은 노력으로 더 나은 결과를 얻을 수 있다는 통찰을 제공합니다. 이 통찰은 지속적인 튜닝에 덜 의존하고 해결하려는 문제의 내재된 기하학적 구조에 더 집중하는 양자 알고리즘을 구축하는 방향으로 미래 연구의 새로운 길을 제시합니다.

기술 요약: 비가중치 그래프에 대한 QASPA-MaxCut

문제 정의
본 논문은 NISQ(Noisy Intermediate-Scale Quantum) 환경에서 양자 근사 최적화 알고리즘(QAOA)이 겪는 성능 병목 현상을 다룬다. QAOA는 조합 최적화(특히 Max-Cut)를 위한 대표적인 변분적 접근 방식이지만, 보고된 성능은 변분 파라미터에 대한 클래식 외부 루프 최적화에 크게 의존한다. 실제로 제한된 게이트 깊이, 노이즈, 그리고 반복적인 회로 평가의 계산 비용은 최적의 파라미터를 찾는 능력을 제약한다. 저자는 표준 깊이-1 QAOA와 새로운 회로 구조인 QASPA-MaxCut을 비교함으로써 클래식 탐색 예산(classical search budgets)의 영향을 격리하고자 한다. QASPA-MaxCut은 그래프 구조를 회로 안사(ansatz)에 직접 내장하여 파라미터 튜닝에 대한 의존도를 줄인다.

방법론
본 연구는 비가중치 그래프를 위해 설계된 시프트 페이즈(shift-phase) 회로인 QASPA-MaxCut을 도입한다. 전역 문제 유니터리( $e^{-i\gamma H_C}$ )와 전역 횡방향 자기장 믹서( $e^{-i\beta \sum X_i}$ )를 교대로 적용하는 표준 QAOA와 달리, QASPA는 전역 믹서 대신 에지 국소 제어 회전(edge-local controlled rotations)을 사용한다.

회로 구성: QASPA 안사는 균일한 중첩 상태를 만들기 위한 하다마드 층(Hadamard layer)으로 시작한다. 그래프의 각 에지 $(i, j)$ 에 대해 특정 블록이 적용된다: $CX_{i,j} R_y^{(j)}(\theta_{ij}) CX_{i,j}$ .
에지 인코딩: 회전각 $\theta_{ij}$ 는 비가중치 케이스의 경우 모든 에지에 대해 $\alpha = \pi/4$ 로 전역적으로 고정된다. 이 블록은 대수적으로 $\exp(-i \frac{\alpha}{2} Z_i Y_j)$ 로 작용하며, 이는 대각 위상을 적용하는 대신 특정 에지 쌍에 대해 컷(cut) 및 미컷(uncut) 구성 사이의 진폭을 재분배한다.
실험 프로토콜:
- 그래프: 본 연구는 작은 인스턴스( $n=8$ 정점)에 대해 정확한 상태 벡터 시뮬레이션을 사용한다. 그래프에는 연결된 백본 보강 무작위 그래프(추가 에지 확률 $p_{edge} \in \{0.1, 0.3, 0.5, 0.7\}$ 포함)와 19개의 수동 지정 커스텀 토폴로지가 포함된다.
- QAOA 베이스라인: 깊이-1 QAOA 회로는 로컬 넬더-미드(Nelder-Mead) 최적화 도구를 사용하여 최적화된다. 성능은 "best-of- $k$ " 곡선으로 측정되며, 여기서 $k$ 는 독립적인 무작위 재시작(random restarts) 횟수(1에서 10까지)를 나타낸다.
- QASPA 평가: QASPA는 외부 루프 탐색 없이 고정된 각도 $\alpha = \pi/4$ 로 실행된다. 보고되는 점수는 **클래식 선택 비율(classical selection ratio)**이다. 즉, 알고리즘이 출력이 가장 높은 상위 4개의 비트 문자열을 선택하고, 이를 Max-Cut 목적 함수에 대해 평가한 후, 그중 발견된 최적의 컷을 보고한다.
- 판독(Readout): 커스텀 토폴로지에 대해서는 샘플링 노이즈 하에서의 안정성을 검증하기 위해 적응형 샷 예산( $N_{shots} = \lceil 0.03047 \cdot 2^n + 1016.2 \rceil$ )을 사용하여 유한 샷 판독 체크를 수행한다.

주요 기여

대수적 유도: 본 논문은 QASPA 에지 블록의 정확한 2-큐비트 대수를 제공하여, $CX-R_y-CX$ 시퀀스가 어떻게 진폭을 재분배하고 믹싱 단계에 에지 구조를 효과적으로 내장하는지 입증한다.
작업 예시: 4개 정점을 가진 비가중치 그래프에 대한 완전하고 추적 가능한 수학적 및 수치적 워크스루를 제공하여, 에지 스케줄, 상태 진화, 출력 확률을 상세히 기술함으로써 구성을 검증한다.
통제된 비교: 투명한 클래식 탐사 예산을 가진 변분 베이스라인(QAOA)과 고정 각도 구조 내장 회로(QASPA)를 비교하는 재현 가능한 실험 프레임워크를 구축한다. 이를 통해 "재시작 효과(restart effect)"를 격리하여, 고정 각도 방식과 경쟁하기 위해 얼마나 많은 클래식 최적화가 필요한지 결정한다.

결과

후보 품질: 테스트된 작은 인스턴스들에서, 고정 각도 QASPA 상태는 최적(또는 최적에 가까운) Max-Cut 솔루션을 상위 4개의 최고 확률 비트 문자열 안에 배치한다. 결과적으로 QASPA의 클래식 선택 비율은 매우 높으며, 그래프 그룹 전체에서 0.955에서 1.000 사이의 범위를 보인다.
QAOA 민감도: 깊이-1 QAOA의 성능은 클래식 재시작 횟수에 매우 민적하다. 기대 근사 비율(expected approximation ratio)은 추가적인 재시작에 따라 개선되지만(예: 희소 그래프의 경우 ~0.71에서 ~0.79로 상승), 테스트된 10회의 재시작 예산 내에서는 일관되게 QASPA 선택 점수보다 낮게 유지된다.
안정성: 커스텀 토폴로지에 대한 유한 샷 판독 체크 결과, QASPA 선택 점수는 규정된 샷 예산 하에서 안정적(평균 1.000, 표준 편차 0)임을 보여주며, 이는 해당 인스턴스들에 대한 후보 선택 규칙의 견고함을 확인시켜 준다.
에지 순서 민감도: 연구는 비가환(non-commuting) 에지 블록들로 인해 QASPA가 순서 불변(order-invariant)이 아님을 언급한다. 그러나 테스트에서 에지 순서의 무작위 순열을 사용했을 때 정형화된 고정 순서 값과 유사한 그룹 평균을 나타냈으며, 이는 소규모 테스트에서의 일정 수준의 탄력성을 시사한다.

의의 및 주장
본 논문은 점근적 우월성이나 하드웨어 지배력을 주장하기보다는, 통제된 범위 내에서 완만한 주장을 펼친다. 주요 발견은 작은 비가중치 그래프의 경우, 고정 각도 QASA 회로가 값비싼 외부 루프 파라미터 탐색 없이도 고품질의 Max-Cut 솔루션을 포함하는 후보 집합을 생성할 수 있다는 것이다. 반면, 표준 깊이-1 QAOA는 유사한 성능에 도달하기 위해 상당한 클래식 최적화 예산(다수의 재시작)이 필요하며, 보고된 평균치에서도 QASPA의 선택 점수를 능가하지 못한다.

저자는 인스턴스의 구조를 회로 안사에 직접 내장하는 것(에지 국별 믹싱을 통해)이 클래식 파라미터 튜닝의 부담을 줄일 수 있음을 보여주는 데 초점을 맞춘다. 이 연구는 얕은 깊이에서의 회로 구조와 클래식 탐색 예산 간의 트레이드오프를 이해하기 위한 베이스라인 역할을 한다. 본 논문은 하드웨어 지향적인 결론을 내리기 전 필요한 단계로서, 대규모 $n$ 으로의 확장성, 가중치 그래프에 대한 성능, 또는 노이즈가 있는 하드웨어에서의 동작에 관한 명시적인 주장을 피하며 이를 향후 과제로 남겨두었다.

유사한 논문