지난 블로그 시리즈에서는 Amazon Braket으로 양자-고전 하이브리드 알고리즘을 실행하는 기본적인 방법을 소개했습니다.
이번 블로그 시리즈에서는 Max-Cut problem(최대 절단 문제)를 해결하기 위해 PennyLane으로 구현한 QAOA(Quantum Approximate Optimization Algorithm, 양자 근사 최적화 알고리즘)를 Amazon Braket Hybrid Jobs에서 실행하는 방법을 두 편으로 나누어 소개합니다. Max-Cut 문제는 네트워크를 두 그룹으로 나눠 연결을 최대화하는 최적화 문제로, 실생활에서는 물류 경로 최적화, 전력망 분할, VLSI 회로 설계, 소셜 네트워크 커뮤니티 분리, 금융 사기 탐지 등 다양한 분야에 적용할 수 있습니다. 이번 1부에서는 Max-Cut 문제와 QAOA의 개념을 살펴본 뒤, 그래프 생성부터 해밀토니언, 양자 회로, 비용 함수 최적화, 디바이스 선택까지 QAOA를 구현한 maxcut_qaoa 모듈의 코드를 단계별로 설명합니다. 이어지는 2부에서는 이 코드를 로컬 시뮬레이터, 하이브리드 잡의 임베디드 시뮬레이터, 온디맨드 시뮬레이터(SV1)라는 세 가지 방식으로 실행하며 그 차이를 비교합니다. 참고로 이 블로그의 코드는 Amazon Braket 예제 노트북 “Using PennyLane with Braket Hybrid Jobs”(GitHub의 amazon-braket-examples 저장소)과 Amazon Braket 개발자 가이드의 QAOA 예제를 바탕으로 재구성한 것입니다. 이 글의 코드는 Amazon Braket 노트북 인스턴스의 conda_braket 커널(PennyLane 0.45.1, Amazon Braket SDK 1.127.0)에서 실행이 정상 동작함을 확인했습니다.
이 블로그 시리즈의 구성은 다음과 같습니다.
PennyLane을 활용한 Amazon Braket에서의 maxcut 문제의 해결 (1부): Max-Cut 개념 및 QAOA 구현
PennyLane을 활용한 Amazon Braket에서의 maxcut 문제의 해결 (2부): 세 가지 실행 방식 비교
Max-Cut 문제의 정의
Max-Cut 문제란, 그림1과 같이 주어진 무방향 그래프에서 정점(노드) 집합을 두 부분 집합 S와 Sc로 나누었을 때, 두 집합 사이를 연결하는 간선(즉, 절단되는 간선, cut)의 개수 또는 가중치 합이 최대가 되도록 하는 분할을 찾는 최적화 문제입니다.
<그림1. 주어진 그래프에서 Max-Cut 문제>
먼저 집합 S는 정점 집합 V의 부분 집합입니다. 예를 들어 그림1에서는 S = {1, 2, 3} ⊂ V 입니다. 다음으로 컷(cut)은 S와 그 여집합 Sc를 잇는 간선들의 가중치 합으로 정의됩니다. 그림1에서 두 집합을 가로지르는 간선은 {(2, 4), (1, 4), (1, 6), (3, 5), (3, 6)} 이므로, 집합 S에 대한 컷은 다음과 같이 계산됩니다.
cut(S) = e24 + e14 + e16 + e35 + e36
Max-Cut 문제의 목적은 이 컷을 최대로 만드는 집합 S를 찾는 것입니다. 이 문제를 수식으로 표현하기 위해 다음과 같이 변수 x를 정의합니다.
xi: 노드 i가 집합 S에 속하는지를 나타내는 변수(속하면 +1, 속하지 않으면 -1)
이렇게 정의하면 xi와 xj가 서로 다른 집합에 있을 때 xixj = -1, 같은 집합에 있을 때 xixj = +1이 됩니다. 예를 들어 그림1에서 x5x4 = +1이고, x5x1 = -1입니다.
이제 이 최적화 문제는 다음과 같이 수식으로 나타낼 수 있습니다.
여기서 (i,j)∈E는, 그래프의 모든 간선(즉, 두 정점 i와 j를 연결하는 모든 쌍)을 의미합니다. 즉, 합산 기호 ∑(i,j)∈E는 그래프 내 모든