Approximating fixed size quantum correlations in polynomial time

두 친구 앨리스와 밥이 서로 엄청나게 멀리 떨어져 있어 대화할 수 없지만, 낯선 이의 질문에 답하여 상품을 타야만 하는 세상을 상상해 보십시오. 고전적인 세계에서 그들의 최선의 전략은 미리 계획을 세우는 것, 예를 들어 비밀 암호를 정하는 것입니다. 하지만 양자 세계에서 그들은 '얽힘(entanglement)'이라 불리는 특별하고 '기묘한' 연결을 공유할 수 있으며, 이를 통해 일반적인 물체로는 불가능해 보이는 방식으로 협력할 수 있습니다. 이 설정은 '비로컬 게임(non-local game)'으로 알려져 있으며, 현실의 한계를 시험하는 놀이터 역할을 합니다. 과학자들이 던져온 핵심적인 질문은 이것입니다: 앨리스와 Bob이 이러한 양자 기술을 사용한다면 얼마나 잘할 수 있는가? 어떤 게임의 경우에는 답을 알고 있지만, 많은 경우에 있어서 최고의 승률을 계산하는 것은 너무나도 어려워서 어떤 컴퓨터로도 합리적인 시간 내에 해결하는 것이 불가능할 수도 있습니다. 이는 우주의 원자 수보다 더 많은 회전이 있는 미로에서 단 하나의 최적의 경로를 찾는 것과 같습니다.

여기서 한 연구팀이 새롭고 영리한 접근 방식을 들고 등장합니다. 그들은 불가능한 미로를 한꺼번에 해결하려 하지 않습니다. 대신, 점점 더 꼭대기에 가까워지는 일련의 '근사 사다리(approximation ladders)'를 구축합니다. 그들의 주요 발견은, 플레이어들이 고정된 제한된 양의 양자 능력(특정한 크기의 얽힘 연결)을 가진 게임의 경우, 원하는 정밀도에 따라 합리적인 시간 내에 매우 좋은 추정치를 계산할 수 있다는 것입니다. 그들은 플레이어들의 공유된 양자 상태를 동일한 음표들의 교향곡처럼 취급하여, 계산의 지저분하고 반복적인 부분을 무시할 수 있게 하는 새로운 수학적 도구를 발명함으로써 이 일을 해냈습니다. 이 방식은 문제가 지수적인 시간(우주의 종말을 기다리는 것과 같은)이 걸리던 것을 다항 시간(큰 숫자를 세는 것과 같은)이 걸리는 문제로 바꾸어 놓았습니다. 그들은 단순히 답을 찾은 것이 아니라, 자신들의 수학적 추정치를 앨리스와 밥이 실제로 사용할 수 있는 실제 작동하는 전략으로 되돌리는 방법까지 만들어 냈으며, 이를 통해 자신들의 지름길이 진정한 해결책임을 증명했습니다.

양자 게임 쇼

두 명의 플레이어를 별도의 방으로 보내는 사회자가 진행하는 게임 쇼를 상상해 보십시오. 사회자는 앨리스에게 질문 하나를, 밥에게는 다른 질문 하나를 무작위로 보냅니다. 질문이 주어진 후에는 서로 대화할 수 없지만, 문이 닫히기 전에 몰래 계획을 속삭일 수는 있습니다. 그들의 목표는 무엇일까요? 비밀 규칙에 맞춰 답을 내놓는 것입니다. 만약 성공하면 점수를 얻습니다.

이 게임의 "고전적" 버전에서 앨리스와 밥은 동전 던지기나 미리 작성된 대본을 따르는 것과 같은 표준적인 전략에 국한됩니다. 하지만 "양자" 버전의 게임에서 그들은 **얽힘(entanglement)**이라 불리는 신비롭고 연결된 자원을 공유할 수 있습니다. 얽힘을 마법의 주사위 한 쌍이라고 생각해 보십시오. 아무리 멀리 떨어져 있어도, 만약 앨리스가 6을 던지면 밥의 주사위도 즉시 6을 보여줍니다. 비록 두 사람 중 누구도 결과를 확인하기 전까지는 무엇이 나올지 결정하지 않았음에도 말입니다. 이 '기묘한' 연결은 고전 물리학이 불가능하다고 말하는 방식으로 그들이 답을 조율할 수 있게 해주며, 종종 단순한 대본만 가지고 있을 때보다 더 자주 게임에서 이기게 해줍니다.

과학자들의 큰 수수께끼는 다음과 같습니다: 그들이 이길 수 있는 절대적인 최대 확률은 얼마인가? 간단한 게임의 경우 우리는 답을 알고 있습니다. 하지만 더 복잡한 게임의 경우, 이 완벽한 숫자를 찾는 것은 악몽과 같습니다. 문제의 핵심은 가능한 전략의 수가 너무 빠르게 증가하여, 가장 빠른 슈퍼컴퓨터라 할지라도 우주의 나이보다 더 긴 시간을 들여 모든 것을 확인해야 하기 때문입니다. 이는 마치 수를 둘 때마다 보드의 크기가 두 배씩 커지는 체스 게임에서 단 하나의 최선의 수를 찾는 것과 같습니다.

새로운 지름길: 대칭성과 "보즈(Bose)"의 마법

제리우스 제이시스(Julius Zeiss)와 그의 팀은 이 문제를 무차별 대입(brute-force) 방식으로 해결하려 하지 않았습니다. 대신, 그들은 플레이어들이 고정된 크기의 양자 도움(즉, '마법 주사위'의 면 수가 특정되어 있음)을 받는 게임의 경우, 활용할 수 있는 숨겨진 패턴이 있다는 것을 깨달았습니다.

그들은 이 문제를 거대한, 무질서한 도서관처럼 취급했습니다. 보통 수십억 권의 정리되지 않은 책이 있는 도서관에서 특정 책을 찾는 데는 영겁의 시간이 걸립니다. 하지만 만약 당신이 책의 99%가 단지 표지만 다를 뿐 같은 몇 가지 제목의 복사본이라는 것을 알게 된다면 어떨까요? 당신은 모든 복사본을 읽을 필요 없이, 각 유형을 대표하는 책 한 권만 읽으면 됩니다.

연구팀은 **보즈 대칭성(Bose-symmetry)**이라는 수학적 개념을 사용했습니다. 양자 세계에서 입자들은 '구별 불가능(indistinguishable)'할 수 있는데, 이는 두 입자를 바꾸어도 시스템의 상태가 변하지 않음을 의미합니다. 연구진은 이러한 게임을 위한 최선의 전략들이 종종 이와 동일한 '구별 불가능'한 특성을 가진다는 것을 깨달았습니다. 이러한 대칭적인 전략들에만 집중함으로써, 그들은 문제를 수십억 권의 책이 있는 도서관에서 작고 관리 가능한 선반으로 축소할 수 있었습니다.

그들은 **보즈 대칭 계층 구조(Bose-symmetric hierarchy)**라고 부르는 새로운 방법을 개발했습니다. 이것을 점진적으로 정확해지는 일련의 추측이라고 생각하십시오.

1. 첫 번째 추측: 계산하기 쉽지만 실제보다 약간 높을 수 있는 대략적인 근사치(상한선, outer bound)에서 시작합니다.
2. 정교화: 더 많은 대칭성 제약을 추가하여, 추측치를 더 촘촘하게 만들고 실제 정답에 가깝게 만듭니다.
3. 결과: 그들은 정답과의 오차가 아주 작은 값($\epsilon$)만큼만 나도록 하기 위해, 이 사다리의 특정 단계까지만 올라가면 된다는 것을 증명했습니다. 결정적으로, 이 사다리를 오르는 데 걸리는 시간은 $1/\epsilon$에 대해 다항식(polynomial) 형태로 증가합니다.

여기서 "다항식"이란 무엇을 의미할까요? 그것은 만약 당신이 두 배 더 정밀해지고 싶다면, 컴퓨터가 두 배 더 열심히 일해야 하는 것이 아니라, 네 배 혹은 여덟 배 정도 더 열심히 일하면 될 뿐, 무한히 더 많이 일할 필요는 없다는 뜻입니다. 이는 이전 방식들이 (정밀도를 두 배 높이면 시간이 두 배가 되고, 다시 또 두 배가 되는 식의) **지수적(exponential)**으로 증가했던 것에 비해 엄청난 개선입니다.

수학에서 현실로: 반올림 기법

숫자를 찾는 것과 실제 승리 전략을 찾는 것은 별개의 문제입니다. 연구진은 단지 승리 확률을 계산하는 데 그치지 않았습니다. 그들은 또한 **"반올림 스킴(rounding scheme)"**을 발명했습니다.

그들이 계산한 최선의 점수가 99.9%라고 가정해 봅시다. 하지만 어떻게 플레이해야 그 점수를 얻을 수 있을까요? 그들의 방법은 단순화된 대칭 세계로부터의 수학적 해를 가져와서 이를 실제 플레이 가능한 전략으로 "반올림"합니다. 그들은 측정 과정을 시뮬레이션함으로써 이 일을 수행합니다. 즉, 추상적이고 완벽한 해를 가져와서 앨리스와 밥이 실제로 수행할 수 있는 구체적인 지침(측정)을 추출하는 것입니다.

이것은 마치 꿈속의 언어로 그려진 보물섬의 완벽한 지도와 같습니다. 연구진은 보물이 어디에 있는지(승리 확률)를 알아냈을 뿐만 아니라, 그 지도를 실제 탐험가가 따를 수 있는 명확하고 단계적인 지침으로 번역하는 방법까지 찾아냈습니다. 그들은 이 번역된 전략이 반드시 최적의 전략에 매우 근접할 것임을 보여주었으며, 게임을 이기기 위한 "실행 가능한(feasible)" 방법을 제공했습니다.

이것이 왜 중요한가

이 연구는 양자 정보 이론의 오랜 난제를 해결했다는 점에서 매우 중요합니다. 오랫동안 과학자들은 고정된 크기의 양자 자원을 가진 게임의 경우 답이 계산 가능할 것이라는 점은 알고 있었지만, 이를 효율적으로 수행할 방법을 찾지 못했습니다. 이전의 방법들은 "지수 시간"에 갇혀 있어 아주 작은 규모의 게임이 아니면 쓸모가 없었습니다.

이러-문제들을 다항 시간 내에 해결할 수 있음을 증명함으로써, 저자들은 광범 Wide한 범위의 양자 게임을 효율적으로 분석할 수 있는 문을 열었습니다. 이것은 단지 게임 쇼에서 이기는 것에 관한 것이 아닙니다. 이는 고전 세계와 양자 세계 사이의 근본적인 경계를 이해하는 데 도움을 줍니다. 이는 특정 시나리오에서 어느 정도의 '양자 이점'이 가능한지를 정확히 알려주며, 그 이점을 달성하는 전략을 찾는 도구를 제공합니다.

또한 이 논문은 이러한 기술이 양자 컴퓨터가 제대로 작동하는지 확인하는 것(오류 수정)이나 두 양자 상태가 정말로 다른지 판별하는 것과 같은 다른 까다로운 양자 물리 문제에도 유용할 수 있음을 시사합니다. 하지만 현재로서 주요한 승리는 명확합니다: 그들은 대칭성의 힘을 사용하여 노이즈를 뚫고 지나감으로써, 불가능한 계산을 관리 가능한 것으로 바꾸어 놓았습니다.

요컨대, 연구팀은 양자 세계가 복잡하고 혼란스러울지라도 그 안에 숨겨진 질서가 있다는 것을 보여주었습니다. 그 질서에 귀를 기울임으로써, 우리는 놀라운 속도와 정확도로 양자 게임의 미래를 예측할 수 있습니다.