⚛️ quantum physics

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

본 논문은 게이트 국소성과 회로 깊이의 곱이 시스템 크기에 대해 로그 스케일일 때, 새로운 국소 상관 기준과 차원에 독립적인 반집중 부등식을 활용하여 전체 역방향 광원 원뿔을 재구성하지 않고도 게이트를 식별함으로써 의사 무작위성의 출현 임계치를 명확히 하는, 상수 차원의 벽돌 구조 랜덤 양자 회로를 다항 시간 내에 학습하기 위한 효율적인 알고리즘을 제시한다.

원저자: Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

게시일 2026-10-01

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

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

양자 물리학의 조용하고 통제된 세계에서, 연구자들은 질서와 혼돈 사이의 경계를 이해하기 위해 끊임없이 노력하고 있습니다. 이 스펙트럼의 한쪽 끝에는 구조가 있습니다. 이는 명확하고 예측 가능한 경로를 따르며, 지도화하고 이해할 수 있는 시스템입니다. 반대쪽 끝에는 무작위성이 있습니다. 이곳에서 시스템은 특정 규칙에 의해 생성되었음에도 불구하고 순수한 우연처럼 보일 정도로 예측 불가능하게 작동합니다. 이러한 긴장은 현대 암호학, 즉 정보를 비밀로 유지하는 과학의 핵심입니다. 만약 컴퓨터가 관찰자에게 완전히 무작위적으로 보이는 일련의 사건들을 생성할 수 있다면, 그 시퀀스는 데이터를 잠그는 데 사용될 수 있습니다. 하지만 영리한 관찰자가 그 시퀀스를 만들어낸 숨겨진 규칙을 찾아낼 수 있다면, 그 자물쇠는 깨지게 됩니다. 수년 동안 과학자들은 단순한 국소적 상호작용으로 구축된 양자 시스템이 정확히 언제 스스로의 설계도를 효과적으로 숨길 만큼 복잡해지는지 궁금해해 왔습니다.

IBM 리서치와 일리노이 대학교의 연구팀은 이제 특정 유형의 양자 시스템에 대해 이 질문에 대한 정밀한 답을 제시했습니다. 그들은 특정 복잡도 지점까지만 무작위 양자 회로의 숨겨진 규칙을 효율적으로 역설계하는 방법을 개발했습니다. 그들의 연구는 회로가 너무 깊지 않고 입자 간의 연결이 너무 넓지 않은 한, 컴퓨터가 실험의 최종 결과를 보고 그 과정을 만든 전체 단계의 시퀀스를 완벽하게 재구성할 수 있음을 보여줍니다. 그러나 그들은 또한 급격한 임계치를 식별했습니다. 회로가 특정 크기를 넘어 성장하면, 재구성이 불가능해지며 시스템은 진정으로 자신의 기원을 숨기는 '의사 무작리(pseudorandom)' 객체가 됩니다. 이 발견은 양자 시스템이 학습 가능한 퍼즐에서 보안이 철저한, 깨뜨릴 수 없는 자물쇠로 전환되는 정확한 조건을 명확히 해줍니다.

연구진은 브릭워크(brickwork) 회로라고 알려진 특정 아키텍처에 집중했습니다. 큐비트(qubit)들이 행과 열로 배열된 격자를 상상해 보십시오. 이 설정에서 큐비트의 상태를 변화시키는 양자 게이트(quantum gates)—즉 연산—는 벽돌을 쌓을 때 교대로 층을 만드는 것처럼 인접한 쌍에만 작용합니다. 과학자들은 모든 큐비트를 단순한 제로(zero) 상태에서 시작하여 이러한 국소적 게이트들의 무작위 시퀀스를 적용했습니다. 질문은 관찰자가 큐비트의 최종 상태만을 가지고 주어졌을 때, 정확히 어떤 게이트가 어떤 순서로 사용되었는지 알아낼 수 있느냐는 것이었습니다.

이를 해결하기 위해 팀은 회로의 층을 역순으로 거슬러 올라가며 연산을 하나씩 벗겨내는 알고리즘을 고안했습니다. 그들 통찰의 핵심은 전체 시스템의 이력을 이해할 필요 없이 특정 게이트의 존재 여부를 테스트하는 영리한 방법이었습니다. 그들은 만약 회로에서 하나의 게이트를 제거하면, 격자의 두 특정 지점 사이의 관계가 완전히 상관관계가 없거나 독립적이 된다는 것을 깨달았습니다. 그러나 그 게이트가 존재한다면, 그 두 지점은 미묘하고 측정 가능한 방식으로 연결되어 있습니다. 이 연결의 강도를 측정함으로써, 알고리즘은 해당 층에서 어떤 게이트가 사용되었는지 정확히 결정할 수 있습니다. 이 접근 방식은 일반적으로 이러한 문제를 불가능하게 만드는 거대하고 복잡한 상호작용의 망을 재구성할 필요를 피하며, 연구자들이 높은 정밀도로 각 게이트를 식별할 수 있게 해줍니다.

이 연구는 회로의 깊이와 게이트의 크기의 곱이 큐비트 수에 대해 로그 스케일 내에 머무는 한 이 방법이 효율적으로 작동함을 증명합니다. 더 쉽게 말하자면, 회로가 너무 높지 않고 게이트가 한 번에 너무 많은 입자를 연결하지 않는다면, 시스템은 투명한 상태를 유지합니다. 연구진은 자신들의 알고리로이 시스템의 크기에 따라 합리적으로 증가하는 시간 내에 원래의 회로를 높은 확률로 복구할 수 있음을 보여주었습니다. 이 결과는 양자 시스템이 학습 가능한 상태로 남아 있는 경계선을 수학적으로 명확히 설정했다는 점에서 중요합니다. 이는 해당 한계 내의 회로들에 대해서는 그 '무작위성'이 충분히 똑똑한 관찰자에 의해 해소될 수 있는 환상임을 확인해 줍니다.

그러나 논문은 이 투명성의 한계 또한 강조합니다. 연구진은 회로가 이 특정 규모를 초과하면, 시스템이 효율적인 관찰자에게 진정한 무작위 상태와 구별할 수 없는 상태로 진입한다는 점을 지적합니다. 이것이 의사 무작리성이 나타나는 임계점입니다. 이 더 깊은 영역에서는 먼 지점들 사이의 상관관계가 너무 약하고 복잡해져서, 알고리즘은 올바른 게이트와 잘못된 추측을 더 이상 구별할 수 없습니다. 논문은 이 규모가 추가적인 자원을 요구하지 않는 안전한 양자 암호 시스템을 만들기 위한 자연스러운 경계일 가능성이 높다고 제안합니다. 만약 회로가 이 지점을 바로 넘어서서 구축된다면, 그것은 정보를 숨기기 위한 강력한 도구가 될 것입니다. 왜냐하면 그것을 역설계하는 데 드는 노력이 엄청나게 커질 것이기 때문입니다.

이 학습을 가능하게 만든 기술적 돌파구는 무작위 양자 연산이 어떻게 작동하는지를 설명하는 새로운 수학적 부등식입니다. 이전의 방법들은 게이트의 크기가 커짐에 따라 수학적 복잡성이 통제 불능으로 증가하기 때문에 어려움을 겪었습니다. 연구팀은 게이트가 아무리 커지더라도 복잡성을 관리 가능한 수준으로 유지하는 새로운 증명 기법을 개발했습니다. 이를 통해 그들은 입자 간의 연결이 늘어나는 시나리오, 즉 이전에는 진전을 가로막았던 상황을 다룰 수 있었습니다. 그들의 작업은 이러한 회로를 학습하는 도구를 제공할 뿐만 아니라, 양자 시스템에서 무작위성이 어떻게 발생하는지에 대한 더 깊은 이해을 제공합니다.

궁극적으로 이 연구는 양자 역학에서 알 수 있는 것과 알 수 없는 것 사이의 최전선을 그려냅니다. 이는 무작위 양자 회로가 믿을 수 없을 정도로 복잡한 상태를 생성할 수 있지만, 특정 크기에 도달하기 전까지는 난공불락이 아니라는 것을 보여줍니다. 그 지점까지는 우주의 구조가 보는 법을 아는 이들에게 여전히 접근 가능한 상태로 남아 있습니다. 그 너사를 넘어서면, 시스템은 스스로를 잠가버려 진정한 의사 무작리성의 원천이 됩니다. 이 발견은 과학자와 암호학자들이 보안이 보장된 양자 자물쇠를 만들기 위해 정확히 어느 정도의 복잡성이 필요한지를 이해하도록 도와주며, 미래의 양자 기술이 엄격하고 증명된 한계 위에 구축되도록 보장합니다.

기술 요약: 무작위 양자 회로의 학습과 의사 난수성(Pseudorandomness)의 출현

문제 정의
본 논문은 무작위 양자 회로의 맥락에서 학습 가능성(learnability)과 의사 난수성(pseudorandomness) 사이의 근본적인 상호작용을 다룹다. 구체적으로, 고정된 차원의 벽돌 구조(brickwork architecture)를 가진 로컬 무작위 양자 회로가 의사 난수 상태(pseudorandom states, PRS)의 임계치에 도달하기 전, 출력 상태의 복사본들(state access)로부터 효율적으로 학습될 수 있는지 여부를 조사한다.

설정은 깊이 $d$ 와 국소성(locality) $\ell$ 을 갖는 $k$ -차원 벽돌 구조 회로를 포함한다. 핵심 질문은 깊이와 국소성의 결합 스케일인 $\ell d = O(\log n)$ 을 만족할 때, 이러한 회로를 다항 시간 내에 정확히 복구할 수 있는가 하는 것이다. 이 영역은 의사 난수 상태(PRS)가 나타날 것으로 예상되는 자연스러운 경계점을 나타내며, 선행 연구들은 PRS가 나타나기 위해 $\ell d = \omega(\log n)$ 이 필요함을 시사한다.

방법론
저자들은 상태 접근 모델(state access model) 하에서 작동하는 효율적인 학습 알고리즘을 제안한다. 이 모델에서 학습자는 유니터리 $U$ 자체에 대한 쿼리 권한 없이, 오직 $|\psi_0\rangle = U|0\rangle^{\otimes n}$ 의 복사본만을 제공받는다. 알고리즘은 마지막 레이어 $U_d$ 에서 첫 번째 레이어 $U_1$ 까지 역방향으로 레이어를 하나씩 복구하며 진행된다.

핵-기술적 혁신은 이전의 접근 방식들이 의존했던 전체 역방향 광원뿔(backward lightcones)을 재구성해야 하는 병목 현상을 피하는 **국소 상관관계 기준(local correlation criterion)**이다. 주요 단계는 다음과 같다:

광원뿔의 불연리성(Lightcone Disjointness): 마지막 레이어의 사이트 $B$ 와 $C$ 에서 작용하는 게이트 $G$ 에 대해, 알고리즘은 $G$ 가 제거되었을 때 $B$ 와 $D$ 의 역방향 광원뿔이 서로 분리되는 사이트 $D$ 를 식별한다.
상관 함수(Correlation Function): 알고리즘은 상관 함수 $\text{Corr}_{B:D}(\rho) = \|\rho_{BD} - \rho_B \otimes \rho_D\|_F^2$ 를 정의한다. 올바른 게이트 $G$ 가 제거되거나 역전되면, 결과 상태는 $B$ 와 $D$ 에 대해 분리 가능(separable)해져 상관관계가 0이 된다. 잘못된 게이트가 선택되면 상관관계는 0이 아닌 값을 유지한다.
게이트 식별(Gate Identification): 공용 게이트 집합(public gateset)으로부터 모든 후보 게이트의 역행렬을 $B$ 와 $C$ 상의 축소된 상태(reduced state)에 적용함으로써, 알고-리즘은 상관관계를 0으로 최소화하는 올바른 게이트를 식별한다.
안티컨센트레이션 분석(Anticoncentration Analysis): 잘못된 게이트에 대한 상관관계가 충분히 큰 값(구체적으로 $\ge 2^{-O(\ell d)}$ )임을 보장하기 위해, 저자들은 Haar-무작위 유니터리에 대한 저차 다항식(low-degree polynomials)에 관한 새로운 차원 독립적 안티컨센트레이션 부등식을 증명한다.

주요 기여

효율적인 학습 알고리즘: 본 논문은 $\ell d = O(\log n)$ 일 때 다항 시간 복잡도를 갖는, $k$ -차원 깊이 $d$ 및 국소성 $\ell$ 의 무작위 벽돌 구조 회로를 정확하게 복구하는 알고리즘을 제시한다. 이는 $\text{poly}(n, 2^{\ell d})$ 의 시간을 소요함을 의미한다.
차원 독립적 안티컨센트레이션: 주요 기술적 기여는 유니터리 군 $U(m)$ 상의 다항식에 대한 새로운 Carbery-Wright 유형의 부등식이다. 소볼(small-ball) 지수가 차원 $m$ 에 다항적으로 의존했던 기존의 경계값들과 달리, 이 결과는 행렬 차원에 독립적인 지수를 확립한다:
$\Pr_{U \sim \mu_{\text{Haar}}} [|P(U)| \le \varepsilon \|P\|_\infty] \le 64m^2 \cdot \varepsilon^{\frac{1}{24\pi d}}$
이 차원 자유로운(dimension-free) 지수는 국소 힐베르트 공간의 차원이 커짐에 따라 복잡성이 폭발하는 것을 방지하면서, 국소성이 증가하는 게이트( $\ell$ )를 다루는 데 필수적이다.
상태 접근 vs 유니터리 접근: 본 연구는 유니터리 접근(임의의 입력에 대해 $U$ 를 쿼리함)보다 엄격하게 약한 모델인 상태 접근(단순히 $U|0\rangle$ 의 복사본을 가짐)만으로도 정확한 회로 복구가 가능하다는 것을 보여준다. 이는 상태 접근 시 거대한 광원뿔을 재구성해야 하여 초다항식(super-polynomial) 복잡성을 초래했던 기존 문헌의 간극을 해결한다.

결과

정리 1.1: 무작위 게이트 집합에서 선택된 깊이 $d$ , $k$ -차원 벽돌 구조 회로에 대해, 높은 확률로 $\text{poly}_k(n, d, \delta^{-1}) 2^{O_k(d\ell)}$ 시간 내에 회로를 정확하게 복구하는 알고리즘이 존재한다.
정리 1.2: 본 논문은 유니터리 군 상의 차원 자유로운 Carbery-Wright 부등식을 증명하며, 이를 Weyl 적분 공식과 Remez형 부등식을 통해 일변수 극값 문제로 환원한다.
상관관계 격차(Correlation Gap): 저자들은 잘못된 게이트 후보에 대해 상관관계 $\text{Corr}_{B:D}$ 가 높은 확률로 $\Gamma = 2^{-O(\ell d)} \text{poly}(\dots)$ 보다 낮지 않음을 증명하여, 학습 알고리즘이 올바른 게이트와 잘못된 게이트를 구별할 수 있음을 보장한다.

의의 및 주장
본 논문은 다음을 동시에 달성하는 최초의 알고리즘이라고 주장한다:

$\ell d = O(\log n)$ 을 만족하는 경우, 증가하는 국소성을 가진 회로에 대해 다항 시간 복잡도를 달성한다.
원래의 회로 배치와 게이트를 정확하게 복구한다.
암호학적 응용에서 출력 상태만을 사용할 수 있는 상황에 더 현실적인 모델인 상태 접근 모델 하에서 작동한다.

저자들은 이 연구가 의사 난수성이 발생하는 조건을 명확히 한다고 위치시킨다. 그들은 $\ell d = O(\log n)$ 스케일이 학습이 가능한 임계점이며, 이 스케일을 넘어설 때( $\ell d = \omega(\log n)$ ), 의사 난수성의 출현으로 인해 효율적인 학습이 불가능해진다고 제안한다. 이 결과는 로컬 Haar-무작위 회로가 로그 깊이 임계치를 초과할 경우, 의사 난수 상태 생성기의 후보로서 기능할 수 있다는 가설을 뒷받ند한다.

본 논문은 학습 알고리즘이 지정된 영역 내에서 효율적이지만, 구조화된 앙상블이나 보조 작업 공간(ancillary workspace)에 의존하는 암호 체계를 깨뜨린다고 주장하는 것이 아니라, 로컬 Haar-무작위 회로에 대한 학습의 한계를 명확히 하는 것이라고 명시적으로 밝힌다. 차원 독립적 안티컨센트레이션 결과는 양자 정보 이론 및 복잡도 이론 분야에서 독립적인 관심사로서의 도구로 강조된다.

유사한 논문