QAOA란? 양자최적화를 Max-Cut 문제로 이해하기

양자 최적화는 ‘수많은 경우의 수 중에서 가장 좋은 선택을 찾는 문제’를 목표로 하며, QAOA는 이 중에서도 조합 최적화 문제를 NISQ 시대에 맞게 풀기 위한 대표적인 양자 알고리즘입니다. QAOA는 정답을 한 번에 찾아주는 마법 같은 최적화 알고리즘이 아닙니다. 양자회로와 고전 최적화 알고리즘을 함께 사용하는 variational hybrid algorithm입니다.

왜 ‘최적화’가 양자컴퓨터의 핵심 응용일까?

현실의 중요한 문제들 대부분은 이렇게 생겼습니다.

• 선택지가 매우 많고
• 모든 경우를 다 보기엔 너무 크며
• “완벽한 정답”보다 “충분히 좋은 해”가 필요

예를 들면:

• 물류 경로 선택
• 스케줄링
• 포트폴리오 구성
• 네트워크 분할

이런 문제들을 최적화 문제라고 부릅니다.

 

기본 흐름은 다음과 같습니다.

초기 양자 상태 준비 → Cost Hamiltonian 적용 → Mixer 적용 → 측정 → 고전 컴퓨터가 파라미터 조정 → 다시 실행

이 과정을 반복하면서 목적함수 값이 좋은 파라미터를 탐색합니다.

중요한 점은 현재 QAOA가 모든 조합최적화 문제에서 고전 알고리즘보다 우수하다고 입증된 것은 아니라는 것입니다. 따라서 실제 비교에서는 문제 규모, 회로 깊이, 샘플 수, 고전 최적화 방법과의 성능 비교가 필요합니다.

Q. 양자 최적화란 무엇인가요? ✅

A. 양자 최적화는 최적화 문제를 ‘양자 상태의 에너지 최소화 문제’로 바꿔 풀려는 접근입니다.

핵심 아이디어는:

• 해 후보 → 양자 상태
• 좋은 해 → 낮은 에너지
• 나쁜 해 → 높은 에너지

즉,

“가장 낮은 에너지를 갖는 상태를 찾자”
로 문제를 바꿉니다.

QAOA란 무엇인가? 

QAOA(Quantum Approximate Optimization Algorithm)는 양자 회로와 고전 최적화를 결합한 ‘하이브리드 알고리즘’입니다. 

구조는 다음과 같습니다.

1️⃣ 양자 회로가 해 후보들을 중첩 상태로 준비
2️⃣ 매개변수(각도)를 가진 회로로 해의 ‘품질’을 조정
3️⃣ 측정 결과를 고전 컴퓨터가 평가
4️⃣ 고전 최적화가 매개변수를 업데이트
5️⃣ 반복

👉 양자는 탐색,
👉 고전은 조정 역할을 합니다.

고전 최적화와 뭐가 다를까?

고전 최적화

• 휴리스틱, 탐욕법, 메타휴리스틱
• 지역 최적해(local minimum)에 잘 갇힘

QAOA의 기대 포인트

• 중첩과 간섭으로
• 여러 해 후보를 구조적으로 탐색

⚠️ 하지만

“항상 고전 알고리즘보다 낫다”는 보장은 없습니다.

QAOA가 특히 잘 맞는 문제들

1️⃣ 조합 최적화 문제 ⭐

QAOA는 특히 다음과 같은 문제에 맞춰 설계되었습니다.

• Max-Cut (그래프 분할)
• Ising / QUBO 형태 문제
• Knapsack, Scheduling의 단순화 버전

이 문제들의 공통점:

• 해가 비트 문자열로 표현 가능
• 비용 함수가 비교적 단순

2️⃣ 그래프 기반 문제

그래프 문제는 QAOA의 대표적인 실험 무대입니다.

• 노드 분할
• 네트워크 커뮤니티
• 배치 문제

이유:

• 그래프 구조 → 양자 회로로 자연스럽게 매핑 가능

3️⃣ “정확한 답”보다 “괜찮은 답”이 중요한 문제

QAOA는 이름 그대로:

• Approximate(근사) 최적화 알고리즘입니다.

따라서:

• 항상 최적해 ❌
• 하지만 실무적으로 쓸 만한 해 ✅

QAOA가 잘 맞지 않는 경우

1️⃣ 연속 최적화 문제

• 실수값 변수
• 미분 기반 최적화

👉 QAOA 구조와 잘 맞지 않음

2️⃣ 아주 정밀한 최적해가 필요한 문제

• 금융 규제
• 안전 임계 시스템

👉 현재의 노이즈 수준에서는 부적합

3️⃣ 문제 크기가 너무 작은 경우

• 고전 알고리즘이 이미 매우 빠름
• 양자 오버헤드가 더 큼

현실적인 한계

• QAOA의 성능은 **회로 깊이(p)**에 크게 의존
• p가 커질수록:
  • 성능은 좋아질 수 있지만
  • 현재 기기에서는 노이즈 급증
    [pennylane.ai]

그래서:

“이론적 잠재력”과
“현재 실험 결과” 사이의 간격이 큼

 

양자컴퓨터란? 큐비트부터 오류정정까지 한 번에 이해하기

 

양자오류정정(QEC)이 왜 핵심인가

중첩(Superposition) vs 확률: 사람들이 가장 많이 헷갈리는 포인트 완전 정리