출처 검증됨레벨 3
QAOA (양자 근사 최적화 알고리즘)
QAOA는 조합 최적화를 위한 양자-고전 하이브리드 알고리즘입니다: 양자 회로에서 매개변수화된 비용 층과 믹서 층을 번갈아 적용하고, 고전 최적화기가 기대 해의 품질을 최대화하도록 매개변수를 조정합니다.
무슨 뜻인가요
QAOA(Farhi, Goldstone, Gutmann, 2014)는 MaxCut 같은 조합 문제를 대상으로 합니다.균등 중첩 |+>^n에서 시작하여 두 연산을 p개 층으로 번갈아 적용합니다: 목적 함수를 인코딩하는 비용 해밀토니안 C에 의한 진화 exp(-i*gamma_k*C), 그리고 믹서 해밀토니안 B(보통 파울리-X 항들의 합)에 의한 진화 exp(-i*beta_k*B).고전 최적화기가 2p개의 각도(gamma, beta)를 조정하여 C의 측정 기대값을 최대화합니다.최종 상태를 측정하면 후보 비트열이 나오며, 좋은 것들이 최적해를 근사합니다.p가 커질수록 달성 가능한 근사 품질은 감소하지 않으며, p 무한대 극한에서 단열 알고리즘의 거동을 회복할 수 있습니다.VQE처럼 얕은 깊이에서도 의미가 있어 근미래 잡음 하드웨어를 염두에 두고 설계되었습니다.일상 비유
반죽을 여러 번 치대는 것과 같아요: 한 번은 원하는 모양 쪽으로 꾹 누르고(비용 층), 다음엔 접어서 섞고(믹서 층), 몇 번 반복하면 반죽이 원하는 모양에 훨씬 가까워져요.
고전 최적화기는 코치, 양자 회로는 선수라고 생각하세요: 선수가 정해진 설정으로 연기를 하면 코치가 점수를 보고 다음 시도의 설정을 조정합니다.
흔한 오해
- QAOA가 고전 최적화 알고리즘을 능가한다는 보장은 없습니다 -- 조합 최적화에 대한 일반적 증명된 속도향상은 알려져 있지 않으며, 일부 설정에서는 고전 알고리즘이 낮은 깊이 QAOA와 대등하거나 더 낫습니다.
- 유한한 깊이 p의 QAOA는 근사적 방법입니다 -- 인증된 최적해가 아니라 확률적으로 좋은 후보해를 반환합니다.
- QAOA는 순수 양자가 아니라 VQE처럼 고전 최적화기가 필요한 하이브리드 루프입니다.
핵심 정리
- |+>^n에서 시작해 비용 층 exp(-i*gamma*C)와 믹서 층 exp(-i*beta*B)를 p번 번갈아 적용.
- 고전 최적화기가 2p개의 각도를 조정하여 기대 목적값을 최대화.
- 근사 품질은 p에 대해 감소하지 않으며, p 무한대에서 단열 알고리즘과 연결.
이해했는지 확인해 보세요
QAOA의 각 층에서 번갈아 적용되는 두 연산은?
- A.오라클과 확산
- B.비용 해밀토니안 진화와 믹서 해밀토니안 진화
- C.QFT와 역 QFT
- D.인코딩과 오류 정정
정답 보기
정답: B. 비용 해밀토니안 진화와 믹서 해밀토니안 진화
이유: 각 층은 목적을 인코딩하는 비용 해밀토니안 C의 진화와 믹서 해밀토니안 B(보통 파울리-X 합)의 진화를 적용하며, 각도 gamma와 beta는 고전적으로 조정됩니다.
먼저 알아야 할 개념
원 출처: Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014)
Graded 2026-07-10 (human sign-off): established per Farhi, Goldstone, Gutmann arXiv:1411.4028 (2014).