⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

이 논문은 깊이 $p \geq 2$ 인 MaxCut 문제에 대해 정확하거나 지수적으로 정밀한 QAOA 기댓값을 평가하는 것이 #P-어렵다는 것을 입증하며, 계산의 난도가 단순한 최적화를 넘어 최적해를 세는 문제로 전이됨을 보여준다.

원저자: Stuart Hadfield

게시일 2026-08-13

📖 6 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Stuart Hadfield

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

컴퓨터가 단순히 숫자를 계산하는 것을 넘어 확률과 함께 춤을 추는 세상을 상상해 보십시오. 이것이 바로 양자 컴퓨팅의 영역입니다. 이 분야는 오늘날의 슈퍼컴퓨터가 우주의 나이보다 더 오랜 시간을 들여야 풀 수 있는, 매우 복잡하고 얽혀 있는 문제들을 해결할 것을 약속합니다. 이 춤의 중심에는 '양자 근사 최적화 알고리즘(QAOA)'이라 불리는 인기 있는 루틴이 있습니다. QAOA를 첨단 기술이 적용된 보물 찾기라고 생각해 보십시오. 당신은 많은 가능한 경로가 담긴 지도(문제)를 가지고 있으며, 가장 많은 금을 발견할 수 있는 단 하나의 경로를 찾고자 합니다. 양자 컴퓨터는 모든 가능한 경로가 동시에 섞여 있는 마법 같은 상태인 '중첩' 상태를 준비한 다음, '레이어' 또는 '깊이(depth)'라고 불리는 일련의 단계들을 통해, 마침내 당신이 들여다보았을 때 최적의 경로가 가장 밝게 빛나도록 확률을 기울입니다.

보물 찾기가 잘 진행되고 있는지 알기 위해, 과학자들은 '기댓값(expectation value)'을 확인해야 합니다. 쉬운 말로 설명하자면, 이것은 매번 동전을 하나하나 세기 위해 춤을 멈추는 대신, 양자 컴퓨터의 춤을 살짝 엿봄으로써 얼마나 금에 가까워졌는지 확인하는 것과 같습니다. 오랫동안 연구자들은 춤이 단 한 단계(깊이 $p=1$ )만 있다면 이 점수를 확인하는 것이 간단한 레시피를 읽는 것처럼 쉽다는 것을 알고 있었습니다. 하지만 춤이 두 단계 이상의 더 복잡한 단계로 넘어가면 어떻게 될까요? Wang과 동료들의 최근 연구는 이러한 더 깊은 춤의 점수를 확인하는 것이 믿기 힘들 정도로 어렵다는 것을 보여주었습니다. 즉, 원래의 보물 찾기 문제를 푸는 것만큼이나 어렵다는 것입니다. 그런데 이것이 단지 하나의 좋은 경로를 찾는 것만큼 어려운 것일까요, 아니면 그보다 더 어려운 것일까요?

Stuart Hadfield가 작성한 이 논문은 그 질문을 깊이 파고듭니다. 저자는 $p \ge 2$ 인 QAOA의 경우, 점수를 확인하는 것이 단순히 하나의 최적의 해를 찾는 것만큼 어려운 것이 아니라, 존재하는 모든 최적의 해를 '세는 것'만큼 어렵다는 것을 증명합니다. 컴퓨터 과학의 세계에서 하나의 해를 찾는 것도 힘든 도전이지만, 그것들을 모두 세는 것은 훨씬 더 거대한 차원의 문제이며, 종종 고전 컴퓨터가 처리하기에 더욱 불가능한 것으로 간 اعتبار됩니다. Hadfield는 두 번째 레이어를 추가하는 순간 이 '계산의 괴물'이 나타난다는 것을 보여줍니다. 이 논문은 단순히 이를 제안하는 데 그치지 않고, 어떤 컴퓨터라도 QAOTA 점수를 계산하려고 하면 본질적으로 불가능한 계산 문제를 풀어야만 하도록 만드는 특정한 유형의 문제 그래프를 구축함으로써 엄밀한 수학적 증명을 제공합니다. 이는 이러한 깊은 양자 알고리즘의 경우, 최악의 시나리오에서 점수가 얼마나 잘 나오고 있는지 확인하는 행위 자체가, 우리가 완벽한 양자 기계를 가지고 있더라도 고전 컴퓨터의 능력으로는 근본적으로 도달할 수 없는 작업이 될 수 있음을 의미합니다.

보물 찾기가 복잡해지다

이 마술의 트릭을 파헤쳐 봅시다. QAOA 알고리즘은 'MaxCut' 문제를 해결하도록 설계되었습니다. 친구들이 파티를 하고 있다고 상상해 보십시오. 당신은 이들을 두 팀(레드 팀과 블루 팀)으로 나누어 게임을 하게 하려고 합니다. 목표는 두 팀 사이의 우정(연결)이 최대한 많이 끊어지도록 팀을 배치하는 것입니다. 이것이 바로 'MaxCut'입니다. 어떤 배치는 다른 배치보다 더 낫습니다. 그리고 절대적인 최적의 배치를 찾는 것은 친구 수가 늘어날수록 점점 더 어려워지는 고전적인 퍼즐입니다.

QAOA 알고리즘은 양자 동전을 던짐으로써 이 최적의 배치를 찾으려 노력합니다. 먼저 모든 사람을 중첩 상태(레드와 블루가 동시에 존재하는 상태)로 만든 다음, 일련의 '비틀기(layers)'를 적용합니다. 더 많은 비틀기를 추가할수록 춤은 더욱 정교해집니다. 춤이 제대로 작동하는지 확인하기 위해 과학자들은 '기댓값'을 계산합니다. 이것을 '점수'라고 생각하십시오. 점수는 양자 춤 속에서 평균적으로 얼마나 많은 우정이 끊어지는지를 알려줍니다.

단 한 번의 비틀기( $p=1$ )의 경우, 이 점수를 계산하는 것은 쉽습니다. 냅킨 위에 적을 수 있을 정도죠. 하지만 두 번째 비틀기( $p=2$ )를 추가하면 상황이 이상해집니다. 이전 연구는 이 점수를 계산하는 것이 'NP-hard'라고, 즉 단 하나의 최적의 팀 배치를 찾는 것만큼 어렵다고 보여주었습니다. 하지만 Hadfield의 논문은 이렇게 말합니다. "잠깐, 사실 그보다 더 심각합니다."

계산의 괴물

Hadfield의 주요 발견은 우리가 이해하는 난이도의 급격한 격상입니다. 그는 $p \ge 2$ 인 QAOA의 점수를 계산하는 것이 단순히 'NP-hard'(하나의 해를 찾는 것)인 것이 아니라, #P-hard임을 증명합니다.

그 차이를 이해하기 위해 당신이 탐정이라고 상상해 보십시오.

NP-hard는 "범죄를 저지른 용의자 '한 명'을 찾을 수 있습니까?"라는 질문을 받는 것과 같습니다. 어렵지만, 운이 좋거나 충분히 노력한다면 한 명을 찾을 수도 있습니다.
#P-hard는 "범죄를 저지른 용의자가 '총 몇 명'입니까?"라는 질문을 받는 것과 같습니다. 당신은 모든 용의자를 찾아내어 그 수를 세어야 합니다.

컴퓨터 과학의 세계에서, 수를 세는 것은 일반적으로 단순히 하나를 찾는 것보다 훨씬 더 어려운 것으로 간주됩니다. Hadfield는 두 개 이상의 레이어를 가진 QAOA의 경우, 점수를 계산하는 과정이 최적의 해의 개수를 세도록 강제한다는 것을 보여줍니다.

마법의 도구 (Gadget)

그는 어떻게 이것을 증명했을까요? Hadfield는 컴퓨터를 잡기 위해 설계된 함정과 같은 영리한 '가젯(gad-get)'을 만들었습니다. 그는 표준 MaxCut 문제를 가져와 그 주변에 거대하고 복잡한 그래프를 구축했습니다. 이 그래프는 특별한 '앵커(anchor)' 지점과 '변수(variable)' 블록을 가지고 있습니다.

트릭은 설계에 있습니다. 양자 컴퓨터가 이 특정 그래프 위에서 춤을 출 때, 최종 점수(기댓값)는 '로랑 다항식(Laurent polynomial)'이라는 거대한 수학적 표현식으로 변합니다. 이 식은 각 항이 서로 다른 변수의 거듭제곱(예: $z^1, z^2, z^3...$ )을 가진 긴 문자열과 같습니다.

Hadfield는 이 문자열에서 가장 높은 차수(extreme coefficient)가 비밀을 간직하고 있음을 보여주었습니다. 만약 당신이 이 점수를 완벽하게 계산할 수 있다면, 이 가장 높은 차수를 추출해 낼 수 있습니다. 그리고 여기서 핵심은, 그 특정 숫자의 크기가 원래 문제의 전체 최적 해의 개수에 직접적으로 비례한다는 것입니다.

따라서, 만약 당신이 이 그래프에 대한 QAOA 점수를 쉽게 계산할 수 있다면, 당신은 즉시 '계산의 괴물' 문제에 대한 답을 알게 됩니다. 계산하는 것이 고전 컴퓨터에게는 효율적으로 불가능하다고 여겨지므로, QAOA 점수를 계산하는 것 또한 고전 컴퓨터에게는 불가능함이 틀림없습니다.

"단 하나의 엣지"라는 놀라움

논문은 더욱 놀라운 결론으로 향합니다. 당신은 이렇게 생각할지도 모릅니다. "알겠습니다, '전체' 점수를 계산하는 것은 어렵겠지만, 혹시 '특정 하나의 우정(단 하나의 엣지)'에 대한 점수를 계산하는 것은 쉽지 않을까요?"

Hadfield는 그렇지 않다고 말합니다. 그는 심지어 양자 컴퓨터에게 두 사람 사이의 상관관계(예: $\langle Z_r Z_s \rangle$ 와 같은 '두 큐비트 상관관계')만을 알려달라고 요청하더라도, 문제가 여전히 #P-hard로 남는다는 것을 증명합니다. 어려움은 단지 큰 그림에만 있는 것이 아니라, 알고리즘의 가장 작은 세부 사항에도 깊게 박혀 있습니다.

이것이 미래에 의미하는 바

이 논문은 명확한 선을 긋습니다.

깊이 $p=1$ : 쉽습니다. 우리는 점수를 효율적으로 계산할 수 있습니다.
깊이 $p \ge 2$ : 어렵습니다. 점수를 계산하는 것은 모든 최적의 해를 세는 것만큼 어렵습니다.

이는 엄청난 함의를 갖습니다. 많은 현대 알고리즘은 더 나은 점수를 얻기 위해 '비틀기(매개변수)'를 조정하며 QAOA를 훈련시키는 데 사용됩니다. 만약 점수를 계산하는 것이 이토록 어렵다면, 고전 컴퓨터로 이러한 알고리즘을 훈련하는 것(양자 기계가 얼마나 잘하고 있는지 확인하는 것)은 깊은 회로의 경우 불가능할 수도 있습니다.

저자는 또한 이것이 양자 컴퓨터가 쓸모없다는 뜻은 아니라고 언급합니다. 사실, 이는 양자 컴퓨터가 더 유용할 수 있음을 의미할 수도 있습니다. 만약 고전 컴퓨터가 점수조차 확인할 수 없다면, 아마도 양자 컴퓨터만이 이를 할 수 있는 유일한 존재일 것이기 때문입니다. 그러나 이 논문은 이러한 '어려움'이 최악의 경우(worst-case scenario)라는 점을 경고합니다. 이는 모든 그래프가 해결 불가능하다는 뜻이 아니라, 수학적 계산이 무너지는 특정한 까다로운 그래프들이 존재한다는 것을 의미합니다.

결론

Stuart Hadfield의 논문은 양자 커뮤니티에 던지는 경종입니다. 이 논문은 우리가 더 많은 레이어를 추가하여 QAOA를 더 강력하게 만들수록, 단순히 문제를 풀기 어렵게 만드는 것이 아니라, 우리가 '제대로 하고 있는지 확인하는 작업' 자체를 기하급수적으로 더 어렵게 만들고 있다는 사실을 알려줍니다. 우리는 양자 춤을 쉽게 검증할 수 있었던 세상에서, 그 춤을 검증하기 위해 컴퓨터 과학에서 가장 어려운 문제 중 하나인 '계산 퍼즐'을 풀어야 하는 세상으로 넘어온 것입니다. 이는 양자의 영역에서, 더 깊이 들어갈수록 수학이 더욱 신비로워진다는 사실을 상기시켜 줍니다.

기술 요약: QAOA 기댓값 평가의 #P-Hard 성질

문제 정의
본 논문은 MaxCut 문제에 적용된 양자 근사 최적화 알고리즘(QAOA)의 기댓값을 평가하는 것의 계산 복잡도를 다룬다. 비용 기댓값 $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ 를 평가하는 것은 임의의 그래프에 대해 깊이 $p=1$ 인 경우 효율적으로 계산 가능한 것으로 알려져 있으나, 최근 연구에서는 고정된 깊이 $p \ge 2$ 에 대해 정확한 평가가 NP-hard가 됨을 밝혀냈다. 본 연구에서 조사하는 핵심 질문은 $p \ge 2$ 에서의 어려움이 최적화(해를 찾는 것)에 국한되는지, 아니면 계수(해의 개수를 결정하는 것)로 확장되는지 여부이다. 저자는 QAOA 기댓값을 계산하는 것이 제약 충족 문제(CSP)의 해의 개수를 세는 것의 난이도에 대응하는 복잡도 클래스인 #P-hard인지 묻고 있다.

방법론
저자는 최대 컷 값을 가장 큰 지수로부터 복원하기 위해 로랑 다항식(Laurent polynomials)을 활용했던 Wang 등[5]의 하드니스 증명 메커니즘을 정교화한다. 저자의 접근 방식은 다음과 같은 단계로 구성된다:

그래프 구축 (균형 잡힌 계수 가젯): 이전 연구에서 사용된 비대칭 가젯 대신, 저자는 입력 그래프 $H$ 로부터 특정 그래프 $G(H)$ 를 구축한다. 이 구축법은 다음을 포함한다:
- 변수 가젯 (Variable Gadgets): $H$ 의 각 정점에 대해, $L = O(n)$ 인 균형 잡힌 완전 이분 그래프 $K_{L,L}$ 이 생성된다.
- 동기화 엣지 (Synchronous Edges): 인접한 $H$ 의 정점들에 대응하는 $K_{L,L}$ 가젯들 사이를 연결하여 원래 그래프의 구조를 보존한다.
- 앵커 정점 (Anchor Vertices): 모든 변수 가젯의 정점들과 서로 연결되어 있으며, 서로 또한 연결된 두 개의 유니버설 정점 $r$ 과 $s$ 를 배치한다.
  이 구축법은 그래프 $G(H)$ 가 지름 2를 갖도록 보장하며, 그 최대 컷(maximum cuts)을 엄격하게 제한한다: 즉, $K_{L,L}$ 가젯들은 완전히 잘려야 하며, 앵커들은 서로 반대편에 있어야 한다.
로랑 다항식 분석: 비용 기댓값(또는 특정 2-큐비트 상관 함수 $\langle Z_r Z_s \rangle$ )은 위상 변수 $z = e^{i\phi}$ 에 대한 로랑 다항식으로 표현된다. 저자는 이 다항식의 계수를 분석한다.
- 저자는 가장 높은 차수의 지수 $D^*$ 에 대응하는 "극단적 계수(extreme coefficient)"를 식별한다.
- "축소된 경로 합(reduced path sum)" 분석을 통해, 계수 $a_{D^*}$ 가 0이 아니며 원래 그래프 $H$ 의 최대 컷의 개수 $|\# \text{MC}(H)|$ 에 직접 비례함을 증명한다.
- 구체적으로, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ 이며, 여기서 $\kappa$ 는 믹서 각도와 그래프 크기에 의존하는 알려진 0이 아닌 대수적 인자이다.
보간을 통한 환원 (Reduction via Interpolation): 저자는 다항 개의 서로 다른 위상 값(단위근)에서 QAOA 기댓값 오라클을 쿼리함으로써, 역 이산 푸리에 변환(inverse discrete Fourier transform)을 사용하여 로랑 계수를 정확하게 복구할 수 있음을 보여준다. 극단적 계수가 최대 컷의 개수를 인코딩하므로, 정확한 평가(또는 지수적으로 정밀한 평가)가 가능한 오라클은 이 개수를 복구할 수 있게 하며, 이를 통해 최대 컷의 개수를 세는 #P-hard 문제로부터 QAOA 기댓값 평가 문제로의 결정론적 다항 시간 튜링 환원을 확립한다.

주요 기여 및 결과

복잡도 이분법 (Complexity Dichotomy): 본 논문은 가중치 없는 단순 그래프에 대한 QAOA 기댓값의 날카로운 복잡도 전이를 확립한다:
- $p=1$ : 문제는 FP(다항 시간 계산 가능)에 속한다.
- $p \ge 2$ : 문제는 결정론적 다항 시간 튜링 환원 하에서 #P-hard이다.
계수 vs 최적화 (Counting vs. Optimization): 최대 컷의 값을 복구했던 이전의 NP-hardness 결과와 달리, 본 연구는 기댓값을 평가함으로써 최대 컷의 개수를 복구할 수 있음을 보여준다. 이는 어려움의 수준을 최적화에서 계수로 격상시킨다.
제한된 어려움 (Restricted Hardness): #P-hardness는 다음과 같은 상당한 제약 조건 하에서도 유지된다:
- 이는 전역 비용 함수가 아닌, 지정된 단일 2-큐비트 상관 함수 $\langle Z_r Z_s \rangle$ 의 평가에 적용된다.
- 이는 매우 제한된 알고리즘 파라미터 세트(고정된 믹서 각도 $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , 그리고 결합된 비용 각도 $\gamma_1 = \gamma_2 = \phi$ ) 하에서도 성립한다.
- 이는 지름이 2인 그래프(높은 차수를 가진 그래프들)에도 적용된다.
도함수 및 헤시안 (Derivatives and Hessians): 저자는 이러한 결과를 확장하여, 파라미터에 대한 QAOA 비용 함수의 정확한 그래디언트(gradient) 및 헤시안(Hessian)을 계산하는 것 또한 #P-hard임을 보여준다.
지수적 정밀도 (Exponential Precision): 이 어려움은 지수적으로 작은 가산 오차( $2^{-\alpha N}$ )로 기댓값을 근사하는 문제까지 확장된다. 이 정밀도는 극단적 계수를 구별하고 정수 형태의 개수를 반올림을 통해 복구하기에 충분하다.

의의 및 주장
본 논문은 QAOA 기댓값에 대한 "깔끔하고 정확한 복잡도 분류"를 제공한다고 주장한다. 주요 의의는 $p=1$ 에서 $p=2$ 로의 전이가 단순히 계산 가능성에서 최적화 어려움(NP-hard)으로의 변화가 아니라, 계수 어려움(#P-hard)으로의 변화임을 입증했다는 점에 있다.

저자는 자신들의 결과가 특정 고차수 그래프 군에 대한 최악의 경우(worst-case)에 대한 진술이며, 이것이 모든 그래프나 일반적인 인스턴스에 대해 QAOA 평가가 어렵다는 것을 의미하지는 않는다고 강조한다. 저자들은 어려움이 정확한 평가 또는 지수적으로 정밀한 평가에 의존한다는 점을 명시하며, 현재의 노이즈가 있는 중간 규모 양자(NISQ) 장치와 더 관련이 깊은 상수 또는 다항 수준의 가산 오차 영역에서의 어려움을 주장하는 것이 아님을 밝힌다.

또한, 본 논문은 샘플링과 관련된 양자 우위 결과와 자신의 연구를 구분한다. $p=1$ 에서 QAOA 출력으로부터 샘플링하는 것은 특정 조건 하에서 이미 고전적으로 어렵지만, 본 연구는 $p=2$ 에서 기댓값을 평가하는 것만으로도 #P-hard한 계수 문제를 해결하기에 충분함을 보여준다. 저자는 결론적으로, 만약 QAOA 기댓값을 지수적 정밀도로 효율적으로 평가할 수 있다면, 다항 계층(polynomial hierarchy)이 최저 수준($P=PH$)으로 붕괴될 것임을 시사한다. 이는 양자 기댓값을 고전적으로 처리하는 하이브리드 알고리즘에 대한 함의를 가지며, 높은 정밀도가 요구될 경우 이러한 접근 방식이 최악의 경우 근본적인 계산적 장벽에 직면할 수 있음을 시사한다.

보물 찾기가 복잡해지다

계산의 괴물

마법의 도구 (Gadget)

"단 하나의 엣지"라는 놀라움

이것이 미래에 의미하는 바

결론

유사한 논문