Circuit complexity lower bounds for quantum spin glasses

기술 요약: 양자 스핀 글래스의 회로 복잡도 하한

문제 정의
본 논문은 양자 $p$-스핀 글래스의 근사 기저 상태(near-ground states)를 준비하기 위한 회로 복잡도를 조사한다. 양자 $p$-스핀 글래스는 상호작용 항이 파울리 문자열(Pauli strings)을 통해 큐비트의 $p$-튜플(p-tuples)에 작용하는 무작위 해밀토니언이다. 양자 정보 이론의 핵심 질문 중 하나는, 간결하게 기술된 해밀토니언의 기저 상태와 같이 물리적으로 자연스러운 상태 군(families of states)이 높은 회로 복잡도(특히 높은 깊이)를 요구하는지 여부이다.

최근 연구는 양자 $p$-스핀 글래스에 대해 최적 에너지가 비얽힘(unentangled, product) 상태에 의한 최적 에너지와 엄격히 분리되어 있음을 입증했다. 그러나 얕은 회로(예: 상수 깊이 또는 로그 깊이)가 이 "생성 상태 간극(product-state gap)"을 메울 수 있을 만큼 충분한 얽힘을 생성할 수 있는지 여부는 미해결 상태로 남아 있었다. 본 논문은 이러한 얕은 회로가 기저 상태 최적값에 가까운 에너지를 가진 상태를 준비할 수 있는지 문제를 다룬다.

방법론
저자들은 상태 준비 하한을 얕은 양자 회로에 의해 인덱싱된 가우시안 프로세스의 균등 제어(uniform control)로 재구성하는 확률적 접근 방식을 채택한다. 핵심적인 기술적 전략은 회로로 준비된 상태의 에너지를 두 가지 성분으로 분해하는 것이다:

1. 생성 유사 항 ($X_0$): 상태의 1-큐비트 마진(one-qubit marginals)에 의해서만 결정된다. 이 항은 회로 깊이에 관계없이 생성 상태(product state)의 최댓값에 의해 상한이 정해진다.
2. 잔차 항 ($R$): 비생성(non-product), 얽힌 $p$-점 상관관계(p-point correlations)를 포착한다.

저자들은 얕은 회로의 경우 잔차 항이 기저 상태 에너지 규모에 비해 점근적으로 무시할 수 있는 수준이라고 주장한다. 증명은 세 가지 주요 기술적 기둥에 의존한다:

• 역방향 서포트(Backward Supports) 및 의존 그래프: 저자들은 출력 큐비트의 "역방향 서포트"를 회로를 역추적하여 특정 출력 큐비트에 영향을 줄 수 있는 입력 큐비트의 집합으로 정의한다. 또한 큐비트들을 정점으로 하고, 역방향 서포트가 겹치는 경우에 에지를 형성하는 의존 그래프를 구축한다. 핵심 관찰은 만약 $p$-스핀 상호작용에 관여하는 큐비트들이 이 의존 그래프에서 독립 집합(independent set)을 형성하면, 해당 $p$-점 기대값이 인수분해되어 잔차 계수가 0이 된다는 것이다.
• 분산 감소(Variance Reduction): 얕은 회로의 국소성 덕분에, 잔차 프로세스의 분산은 원래 에너지의 분산보다 현저히 작다. 구체적으로, 원래의 정규화된 에너지는 $1/n$ 차수의 분산을 갖는 반면, 정규화된 잔차는 $2^D/n^2$ 차수의 분산을 갖는다 (여기서 $D$는 회로 깊이).
• 엔트로피 및 커버링 바운드(Entropy and Covering Bounds): 모든 가능한 회로에 대한 잔차 프로세스의 상한(supremum)을 제어하기 위해, 저자들은 깊이 $D$인 회로 클래스에 대한 균등 엔트로피 바운드를 유도한다. 결정적으로, 임의의 수의 보조 큐비트($r$)가 존재하는 상황을 처리하기 위해, 물리적 출력 큐비트들의 결합 역방향 서포트로 회로를 "가지치기(pruning)"하고 활성 보조 큐비트를 정형화된 블록으로 재라벨링한다. 이를 통해 커버링 수(covering numbers)가 $r$에 독립적이도록 보장한다.

이러한 바운드들은 무작위 해밀토니언의 세 가지 영역에 걸쳐 적용된다:

1. 평균장(Mean-Field): 가능한 모든 $p$-튜플이 존재하는 경우.
2. 성장하는 평균 차수 희박(Growing-Average-Degree Diluted): 평균 차수가 $n$에 따라 증가하는 희박한 하이퍼그래프.
3. 유한 평균 차수 희박(Bounded-Average-Degree Diluted): 평균 차수가 유한한(항의 개수가 선형적인) 희박한 하이퍼그래프.

주요 기여 및 결과
본 논문은 임의의 보조 큐비트 개수에 대해 균일하게, 세 가지 영역 모두에서 근사 기저 상태 준비를 위한 회로 깊이 하한을 확립한다:

1. 로그 깊이 하한 (평균장 및 성장하는 평균 차수 희박):
   충분히 큰 고정된 $p$에 대하여, $n$-큐비트 상태를 정규화된 에너지가 최적값으로부터 고정된 양의 상수 이내로 준비하는 모든 회로는 적어도 $\Omega_p(\log n)$의 깊이를 가져야 한다. 이는 임의의 보조 큐비트를 사용하는 경우에도 성립한다. 증명은 깊이 $D \leq \delta \log n$일 때, 잔차 에너지가 생성 상태 에너지와 기저 상태 에너지 사이의 간극을 메우기에는 너무 작다는 것을 보여준다.

2. 고정 깊이 장애 (유한 평균 차수 희박):
   평균 차수가 유한한(항의 개수가 선형적인) 영역에서, 본 논문은 고정 깊이 장애를 증명한다. 모든 고정된 깊이 $D$에 대하여, 충분히 큰 차수 프리팩터(degree prefactor) $\zeta$가 존재하여, 어떤 깊이 $D$의 회로(임의의 보조 큐비트 포함)도 높은 확률로 근사 기저 상태를 준비할 수 없다. 성공 확률은 $n \to \infty$를 거쳐 $\zeta \to \infty$로 가는 반복 극한(iterated limit)에서 0으로 수렴한다.

3. 보조 큐비트에 대한 균일성:
   보조 큐비트의 수가 많더라도 이 하한들이 유효하다는 것을 증명한 것이 중요한 기술적 기여이다. 기존의 계수(counting) 논법들은 보조 큐비트의 수가 시스템 크기에 비해 클 경우 의미 있는 깊이 하한을 제공하지 못하는 경우가 많았으나, 가지치기 및 재라벨링 기법은 이러한 한계를 극복한다.

의의 및 NLTS와의 연결
저자들은 자신들의 결과를 NLTS(No Low-Energy Trivial States) 문제에 대한 확률적 경로로 위치시킨다.

• 코드 기반 NLTS와의 대조: 이전의 돌파구(예: Anshu, Breuckmann, Nirkhe [6])는 양자 LDPC 코드로부터 구성된 해밀토니언에 대해 NLTS를 증명했다. 이러한 구성은 가환적인(commuting) 국소 항, 좌절 없는(frustration-free) 기저 공간, 그리고 특정한 부호 이론적 구조(등주적 성질 등)에 의존한다.
• 무작위, 비가환 설정: 이와 대조적으로, 여기서 연구되는 해밀토니언은 무작위적이며 일반적으로 비가환적이고, 알려진 효율적인 준비 절차가 없다. 장애는 코드의 기하학적 구조가 아니라, 스핀 글래스 무질서와 얕은 회로의 제한된 빛 원뿔(light-cones) 사이의 상호작용에서 발생한다.
• 함의: 이 결과는 평균장 및 성장하는 평균 차수 영역의 양자 스핀 글래스 해밀토니언에 대해 완전한(단순히 조합론적인 수준을 넘어선) NLTS 유형의 장애를 제공한다. 유한 평균 차수 영역에서는, 차수 프리팩터가 증가함에 따라 완전한 NLTS 성질에 도달하는 고정 깊이 장애를 제공한다.

본 논문은 근사 기저 상태의 양자 $p$-스핀 글래스가 임의의 보조 큐비트를 포함하더라도 다항식 크기의 회로에 의해 준비될 수 없다고 추측하며 마무리한다. 다만 이를 증명하는 데는 현재의 범위를 넘어서는 기술, 잠재적으로 BQP와 QMA의 분리와 관련된 기술이 필요할 것이다.