Pennylane을 활용한 Amazon Braket에서의 maxcut 문제의 해결 (1부) – Max-Cut 개념 및 QAOA 구현

문제 상황

• 그래프 정점을 두 집합으로 분할해 집합 사이 간선 수 또는 가중치 합을 최대화하는 Max-Cut 최적화 문제
• 정점 수 증가에 따른 분할 경우의 기하급수적 증가와 브루트포스 탐색 한계

구조와 흐름

• Max-Cut 목적함수의 음수를 비용 해밀토니언으로 변환해 에너지 최소화 문제로 재구성
• Hadamard 초기화 뒤 비용 레이어와 믹서 레이어를 p회 반복하는 QAOA 회로 구성
• 양자 회로의 비용 기댓값과 고전 경사 하강법을 결합한 γ·β 파라미터 최적화 루프

선택 이유

• 얕은 회로 기반의 양자-고전 하이브리드 근사 알고리즘으로서 NISQ 환경 적용 가능성
• 비용 기댓값 최소화를 통한 좋은 분할의 측정 확률 집중 방식

적용해볼 점

• NetworkX 무작위 그래프와 인접 리스트 파일을 QAOA 입력으로 활용
• PennyLane의 qml.qaoa 레이어, qnode, 확률 분포 계산을 이용한 maxcut_qaoa 구현
• device_arn 분리를 통한 로컬 시뮬레이터·Amazon Braket 시뮬레이터·QPU 실행 전환