부호 문제

계산물리 수치해석 통계 마지막 수정: 2026-09-14 04:49:31

1. 개요[편집]

부호 문제 Sign Problem
증상	경로 가중치가 음수·복소수 → 확률로 해석 불가
우회	$\|w\|$ 로 표집하고 부호를 관측량에 얹는 재가중
대가	평균 부호 $\langle s\rangle\sim e^{-\beta N\Delta f}$ — 필요 표본수가 $e^{2\beta N\Delta f}$
등장처	페르미온 · 좌절 스핀계 · 유한 밀도 QCD · 실시간 동역학
복잡도	일반적 해결은 NP-난해 (트로이어·비제, 2005)
핵심 성질	표현 의존적 — 기저를 바꾸면 사라질 수 있다
흔한 오해	"답이 틀린다" ✗ / "비용이 지수적이다" ○

몬테카를로는 “가중치가 곧 확률”이라는 한 줄 위에 서 있다. 양자 다체 문제는 그 한 줄을 아주 자주, 아주 태연하게 어긴다.

부호 문제(sign problem)는 양자 몬테카를로에서 경로적분 가중치가 음수나 복소수가 되어 확률분포로 해석할 수 없고, 절댓값으로 표집한 뒤 부호를 보정하면 통계오차가 계의 크기와 역온도에 대해 지수적으로 폭발하는 현상이다. 강상관 전자계·양자 색역학의 고밀도 영역·좌절 자성체가 수십 년째 정면 계산을 못 하는 이유가 전부 이것 하나다.

먼저 오해 하나를 털어 내고 가자. 부호 문제가 있는 계산은 틀린 답을 주지 않는다. 재가중 추정량은 여전히 불편(unbiased)이며, 표본을 충분히 쌓으면 참값으로 수렴한다. 문제는 “충분히”가 $e^{\beta N}$ 규모라는 것. 정확도의 문제가 아니라 비용의 문제이고, 이 구분이 왜 중요한지는 아래에서 다시 나온다.

2. 어디서 부호가 나오는가[편집]

몬테카를로가 다루는 분배함수는 배위 $C$ 에 대한 합

Z=\sum_C w(C)

이고, 관측량은 $\langle O\rangle=\sum_C O(C)w(C)/Z$ 다. 마르코프 연쇄 몬테카를로는 $w(C)/Z$ 를 확률로 삼아 배위를 뽑는데, 이것이 성립하려면 모든 $w(C)$ 가 0 이상이어야 한다. 고전 통계역학에서는 $w=e^{-\beta E}$ 라 자동으로 양수다. 양자계에서는 그렇지 않다.

페르미온의 교환 반대칭. 파동함수가 입자 교환에 부호를 바꾸므로, 경로적분에서 입자 궤적이 서로 자리를 바꾸는 배위에 음의 가중치가 붙는다. 행렬식 표현으로 가면 $\det M$ 의 부호가 그대로 문제가 된다. 실공간 양자 몬테카를로에서는 파동함수의 마디면을 워커가 넘나드는 형태로 같은 문제가 나타난다.

좌절된 스핀계. 페르미온이 아니어도 생긴다. $e^{-\beta H}$ 를 트로터 분해해 전개하면 비대각 행렬요소가 가중치에 들어오는데, 양의 비대각 요소(반강자성 $XY$ 항이 좌절된 삼각 격자에 얹힌 경우 등)가 있으면 항의 부호가 갈린다. 이분 격자에서는 부분격자마다 스핀을 회전시켜 부호를 통째로 흡수할 수 있지만, 삼각·카고메 격자에서는 그 변환이 존재하지 않는다.

복소 작용. 격자 QCD에 유한 바리온 화학퍼텐셜 $\mu_B$ 를 넣으면 페르미온 행렬식이 아예 복소수가 된다. 중성자별 내부나 QCD 임계점을 다루지 못하는 이유다. 위상 문제(phase problem)라고 따로 부르기도 하지만 본질은 같다.

실시간 동역학. 민코프스키 시간의 가중치는 $e^{iS/\hbar}$ 다. 절댓값이 1이고 위상만 돈다 — 부호 문제의 극단 형태이며, 허수 시간에서 계산한 뒤 해석적 연속으로 돌아오려는 시도가 부적절 문제가 되는 것도 여기서 온다.

반대로 보손계는 대체로 안전하다. 보스-허바드 모형의 호핑 항은 비대각 요소가 전부 음수( $-J$ )라 전개의 모든 항이 양수가 되고, 그래서 웜 알고리즘이 수천 자리 격자를 유한온도에서 돌릴 수 있다. 같은 격자, 같은 상호작용인데 입자 통계 하나로 난이도가 갈린다.

3. 왜 지수적으로 나빠지는가[편집]

가중치의 부호를 $s(C)={\rm sgn}\,w(C)$ 로 두고 $|w|$ 를 확률로 삼는 재가중을 하면

\langle O\rangle=\frac{\sum_C O(C)s(C)|w(C)|}{\sum_C s(C)|w(C)|} =\frac{\langle Os\rangle_{|w|}}{\langle s\rangle_{|w|}}

이 된다. 수식으로는 아무 문제가 없다. 문제는 분모다. 분모는 두 분배함수의 비이고

\langle s\rangle_{|w|}=\frac{Z}{Z_{|w|}}=e^{-\beta V(f-f_{|w|})}\equiv e^{-\beta V\Delta f}

인데, 자유에너지 밀도가 크기 변수이므로 지수의 어깨에 부피 $V$ (또는 입자 수 $N$ )와 역온도 $\beta$ 의 곱이 올라간다. 그리고 $Z\le Z_{|w|}$ 이므로 $\Delta f\ge0$ 이다. 즉 평균 부호는 항상 지수적으로 죽는다.

오차를 보자. $s=\pm1$ 이라 $\langle s^2\rangle=1$ 이므로 표본 $N_s$ 개에서 분모의 상대오차는

\frac{\delta\langle s\rangle}{\langle s\rangle} =\frac{\sqrt{1-\langle s\rangle^2}}{\sqrt{N_s}\,\langle s\rangle} \;\xrightarrow{\ \langle s\rangle\ll1\ }\; \frac{1}{\sqrt{N_s}}\,e^{+\beta V\Delta f}

목표 정밀도를 유지하려면 $N_s\sim e^{2\beta V\Delta f}$ 가 필요하다. 비용이 부피에 대해서도, 온도를 내리는 데 대해서도 지수적이다. 저온의 큰 계 — 정확히 우리가 알고 싶은 영역 — 가 통째로 막힌다.

실무 감각은 이렇다. $\langle s\rangle$ 가 0.1 이면 표본을 100배 더 쌓으면 되니 참을 만하다. 0.01 이면 1만 배다. $10^{-3}$ 아래로 내려가면 그 계산은 끝난 것이고, 논문에는 ” $\langle s\rangle$ 가 접근 가능한 범위를 벗어났다”는 문장이 들어간다. 그래서 부호 문제가 있는 코드는 평균 부호를 상시 관측량으로 찍어 두는 것이 국룰이다. 오차막대만 보고 있으면 무엇이 잘못됐는지 모른 채로 자원을 태우게 된다.¹

여기에 자기상관이 겹치면 상황이 더 나쁘다. 마르코프 연쇄의 유효표본크기가 명목 표본 수보다 훨씬 작으므로, 위 식의 $N_s$ 에 넣어야 할 값도 그만큼 줄어든다. 자기상관 시간을 제대로 세지 않으면 부호 문제로 죽은 결과에 예쁜 오차막대가 붙는다.

4. 표현 의존성 — 물리가 아니라 좌표의 문제[편집]

부호 문제에서 가장 자주 오해되는 성질이 이것이다. 부호 문제는 물리계의 성질이 아니라 우리가 고른 기저·분해·표현의 성질이다. 같은 해밀토니안을 다른 기저로 쓰면 가중치가 전부 양수가 될 수도 있다.

이분 격자 반강자성 하이젠베르크 모형은 한쪽 부분격자를 $\pi$ 회전시키면 부호가 사라진다. 회전이 존재하지 않는 좌절 격자에서만 남는다.
반채움의 이분 격자 허바드 모형은 입자-정공 대칭 때문에 보조장 QMC 의 가중치가 두 스핀 성분의 행렬식 곱, 즉 $\det M_\uparrow \det M_\downarrow = (\det M)^2\ge0$ 이 되어 부호 문제가 없다. 도핑하면 그 대칭이 깨지고 즉시 터진다. 모트 절연체 물리의 핵심 영역이 하필 여기다.
특정 대칭(시간 역전·크라머스 축퇴, 마요라나 표현의 반유니터리 대칭 등)을 만족하는 모형군은 부호 문제가 없음을 증명할 수 있다. 이런 조건을 찾아 모형을 설계하는 것 자체가 하나의 연구 분야다.

그래서 “이 모형은 부호 문제가 있다”는 문장은 엄밀히는 **“이 표현에서는 있다”**로 읽어야 한다. 어딘가에 부호 없는 표현이 존재할 가능성은 열려 있고, 실제로 찾아낸 사례가 계속 나온다. 동시에 이것이 바로 다음 절의 정리가 말하는 바 — 일반적으로 그것을 찾는 일이 어렵다는 것이다.

5. NP-난해라는 결과[편집]

2005년 트로이어와 비제는 부호 문제의 일반적 해결이 NP-난해임을 보였다. 논증의 얼개는 이렇다. 부호 문제가 있는 어떤 양자계의 분배함수를 계산하는 문제를, 3차원 스핀글라스의 바닥상태를 찾는 문제로 환원할 수 있다. 후자는 NP-완전으로 알려져 있다. 따라서 모든 계에 통하는 다항 시간 알고리즘이 존재한다면 $NP\subseteq BPP$ 가 되고, 이는 널리 믿어지는 추측에 반한다.

이 결과가 말하는 것과 말하지 않는 것을 구분해야 한다.

말한다: 만능 해법을 찾는 시도는 합리적인 복잡도 가정 아래 헛수고다.
말하지 않는다: 특정 모형의 부호 문제를 푸는 것이 불가능하다. 오히려 개별 모형에서는 계속 풀리고 있다.
말하지 않는다: 양자계 시뮬레이션이 근본적으로 불가능하다. 부호 문제는 한 가지 알고리즘 부류의 한계이지 자연의 금지 조항이 아니다.

마지막 항목에는 재미있는 반전이 있다. 부호 문제는 고전 컴퓨터로 확률 표집을 한다는 전제에서 나온 것이다. 양자 시뮬레이터나 양자 컴퓨터는 애초에 표집을 하지 않고 계를 직접 발전시키므로 이 장애를 겪지 않는다. 광격자의 페르미온 실험이나 초전도 회로 기반 양자 시뮬레이션이 주목받는 이유의 상당 부분이 여기에 있다.

6. 완화책[편집]

고정노드·구속경로. 가장 널리 쓰이는 실용 처방이다. 실공간 확산 QMC에서는 시행파동함수가 정하는 마디면을 워커가 넘지 못하게 막아 각 영역의 부호를 고정한다. 보조장 QMC 에서는 구속경로(CPMC)나 위상 없는(phaseless) 근사가 같은 역할을 한다. 비용이 다항식으로 내려가는 대신 편향이 들어오며, 그 편향은 시행파동함수의 품질에 달렸다. 고정노드 DMC 의 에너지는 참값에 대한 엄밀한 상한이라 변분적 통제가 가능하다는 것이 이 근사의 미덕이다. 자세한 것은 양자 몬테카를로 문서 참고.

기저·표현 바꾸기. 앞 절의 성질을 공략적으로 쓰는 방향. 메론 클러스터 알고리즘은 클러스터 갱신을 설계해 부호가 다른 배위들이 쌍으로 상쇄되도록 만들어, 살아남는 배위만 표집한다. 페르미온 백 방법이나 마요라나 양성 조건 탐색도 같은 계열이다. 성공하면 지수 비용이 통째로 사라지므로 보상이 크지만, 모형마다 새로 찾아야 한다.

복소 랑주뱅. 장 변수를 복소화해 확률미분방정식으로 진화시키는 확률 양자화 기법. 표집을 포기하므로 부호를 다룰 필요 자체가 없다. 문제는 잘못된 답으로 수렴할 수 있다는 것 — 복소 궤적이 무한대로 새거나(경계항) 극점 근처에 들러붙으면 결과가 틀린다. 그래서 수렴의 정당성을 사후에 검사하는 판정 기준(드리프트 항 분포의 꼬리 등)이 함께 개발됐고, 정칙화를 얹은 변형이 여럿 있다. 복소 랑주뱅 방법이 유한 밀도 QCD 에서 계속 시도되는 이유는 다른 방법이 더 나쁘기 때문이다.

레프셰츠 심블. 적분 경로를 복소 공간으로 변형해 허수 작용이 일정한 초곡면(안정 다양체) 위로 옮기는 방법. 경로 위에서는 위상이 상수라 뽑아낼 수 있다. 대가는 둘이다 — 야코비안에서 잔여 위상이 나오고, 심블이 여러 개면 그 사이의 상대 가중치를 알아야 한다. 안장점 구조를 파악해야 하므로 차원이 큰 실제 계에 적용하기가 만만치 않지만, 원리가 깨끗해서 연구가 활발하다.

외삽·해석적 연속. 부호 문제가 없는 영역에서 계산한 뒤 밀고 나간다. 격자 QCD 에서 $\mu_B^2$ 로 테일러 전개하거나 허상 화학퍼텐셜에서 계산해 해석적으로 연속하는 방식이 표준이다. 근처에서만 믿을 만하고, 상전이선을 넘어가면 무효다.

밀도 상태 방법·재가중 변형. 제약을 건 분배함수를 구간별로 재구성하는 방식. 부호 문제를 없애지는 못하고 접근 가능한 부피·온도 범위를 조금 넓힐 뿐이다.

방법	비용	편향	적용 범위
직접 재가중	지수적	없음	작은 계·고온만
고정노드·구속경로	다항식	있음(상한 보장 가능)	전자 구조·격자 모형
기저 변환·메론	다항식	없음	찾아낸 모형에만
복소 랑주뱅	다항식	잘못 수렴 가능	유한 밀도 QCD 등
레프셰츠 심블	높음	원리상 없음	저차원 모형 중심
해석적 연속	낮음	외삽 오차	무부호 영역 근처

7. 실무에서[편집]

평균 부호를 먼저 본다. 오차막대보다 먼저 볼 숫자다. $\langle s\rangle$ 의 온도·부피 의존성을 찍어 보면 접근 가능한 매개변수 범위가 그냥 눈에 보인다.
편향 없는 방법과 편향 있는 방법을 섞지 않는다. 고정노드 결과와 정확한 결과를 같은 그래프에 오차막대만 붙여 놓으면 독자가 속는다. 근사 종류를 캡션에 반드시 적는다.
두 방법으로 교차검증한다. 부호 문제 영역의 결과는 단일 방법으로 확정하지 않는 것이 이 분야의 관례가 됐다. 2차원 허바드 모형 벤치마크가 그 정신의 결과물이다.
“조금만 더 돌리면 된다”는 유혹을 경계한다. 지수적 비용 앞에서 코어 시간을 10배 늘려 얻는 것은 $\ln10/(2\beta\Delta f)$ 만큼의 부피나 역온도다. 대개 아무것도 아니다.²

8. 여담[편집]

부호 문제라는 이름이 워낙 소박해서 처음 듣는 사람은 “부호 하나 관리하는 게 뭐가 그리 어렵나” 싶어 한다. 실제로 어려운 것은 부호가 아니라 상쇄다. 거의 같은 크기의 양수와 음수를 더해 지수적으로 작은 값을 얻으려는 시도이며, 이런 구조는 수치해석 어디서든 재앙이다. 조건수 이야기의 확률론 버전이라 봐도 된다.
부호 문제가 풀리면 무엇이 열리는지 목록을 적어 보면 좀 무섭다 — 구리산화물 고온초전도 기작, 중성자별 상태방정식, 좌절 자성체의 스핀 액체 여부, 강상관 물질 설계. 한 알고리즘 장벽 뒤에 미해결 문제들이 줄을 서 있는 드문 사례다.
그래서 이 분야에는 “부호 문제를 풀었다”는 주장에 대한 반사적 회의가 있다. 대부분은 특정 모형군에서만 성립하는 결과이고, 종종 그 모형군이 애초에 부호 문제가 없던 부류로 판명된다. 발표를 들을 때의 첫 질문은 정해져 있다 — “어떤 모형 부류에서요?”³
재미있는 관점 하나. 부호 문제의 심각도 $\Delta f$ 는 원래 계와 절댓값 계의 자유에너지 차이인데, 절댓값 계는 물리적으로 아무 의미가 없는 가상의 계다. 의미 없는 계와의 거리가 계산 난이도를 결정한다는 구조가 묘하다. 그리고 이 사실이야말로 부호 문제가 물리가 아니라 표현의 문제라는 가장 짧은 증거이기도 하다.

9. 관련 문서[편집]

양자 몬테카를로 · 몬테카를로 방법 · 마르코프 연쇄 몬테카를로 · 중요도 표본추출
격자 QCD · 모트 절연체 · 보스-허바드 모형 · 초전도
경로 적분 · 복소 랑주뱅 · 확률미분방정식 · 안장점
NP-완전 · 스핀글라스 · 담금질 모사 · 이징 모형
유효표본크기 · 부트스트랩 · DMRG · 텐서 네트워크
광격자 · 계산물리 · 검증 및 확인

실제로 이 바닥의 초심자 통과의례가 있다. 며칠을 돌려 예쁜 곡선을 뽑아 왔는데 지도교수가 첫 질문으로 “평균 부호 얼마야?”를 던지고, 확인해 보니 $10^{-4}$ 였다는 이야기. 그 곡선은 사실상 잡음이었다. ↩
$\beta\Delta f$ 가 3만 되어도 $\langle s\rangle\sim0.05$ 라 표본이 400배 필요하다. 거기서 $\beta$ 를 두 배로 하면 16만 배다. 지수 함수 앞에서 하드웨어는 늘 진다는 교훈이 이만큼 노골적인 곳도 드물다. ↩
물론 회의가 지나쳐서 진짜 진전을 놓치는 반대쪽 실패도 있다. 메론 클러스터나 마요라나 양성 조건처럼 실제로 특정 모형군의 지수 장벽을 없앤 성과들이 나왔고, 그 덕에 예전엔 접근 못 하던 상전이들이 정밀하게 측정됐다. 만능 해법이 없다는 것과 아무 진전이 없다는 것은 전혀 다른 이야기다. ↩