Linear gate bounds against natural functions for position-verification

당신이 거대하고 텅 빈 방의 정확히 중간에 서 있다는 것을 친구들에게 증명하려고 한다고 상상해 보십시오. 단순히 "나 여기 있어"라고 말할 수는 없습니다. 왜냐하면 친구들은 당신을 볼 수 없기 때문입니다. 대신, 그들은 반대편 벽에서 당신에게 질문을 던지고, 음파가 당신의 귀에 닿는 즉시 답변을 요구합니다. 만약 당신이 실제로 중간에 있다면, 타이밍이 완벽하게 맞아떨어집니다. 하지만 당신이 구석에 숨어 있다면, 소리가 도달하는 데 시간이 너무 오래 걸려 당신의 답변이 늦게 도착하게 되고, 결국 당신의 위치가 탄로 나게 됩니다. 이것이 바로 **위치 검증(position verification)**의 기본 개념입니다. 즉, 빛의 속도를 자(ruler)로 사용하여 누군가의 위치를 증명하는 것입니다.

하지만 여기서 까다로운 문제가 있습니다. 만약 속임수를 쓰려는 사람이 초능력을 가지고 있다면 어떨까요? 양자 물리학의 세계에는 '복제 불가능 정리(no-cloning theorem)'라는 규칙이 있는데, 이는 비밀스러운 양자 메시지를 완벽하게 복제할 수 없음을 의미합니다. 이 덕분에 위치 검증은 깨뜨릴 수 없는 것으로 여겨졌습니다. 그러나 영리한 사기꾼들은 다른 초능력인 **얽힘(entanglement)**을 이용해 속임수를 쓸 수 있다는 것을 알아냈습니다. 두 개의 마법 동전이 서로 아무리 멀리 떨어져 있어도 항상 같은 면이 나오는 상황을 상상해 보십시오. 만약 사기꾼 팀이 이 마법 동전들을 공유한다면, 그들은 마법 같은 연결을 이용해 답을 즉각적으로 시뮬레이션함으로써, 실제로는 가장자리에 서 있으면서도 마치 중간에 있는 것처럼 속일 수 있습니다.

오랫동안 과학자들은 궁금해했습니다. 사기꾼이 이 속임수를 쓰기 위해 얼마나 많은 마법의 동전이 필요한가? 만약 그 답이 "아주 많이"라면, 정직한 사람들은 그만큼의 마법을 구축하는 것이 너무 어렵기 때문에 안전할 수 있습니다. 하지만 만약 그 답이 "아주 조금만 있어도 된다"라면, 이 시스템은 무너지는 것입니다. 이 논문은 바로 이 질문, 특히 정직한 사람이 간단한 수학 문제(숫자를 더하는 것과 같은)와 아주 적은 양의 양자 마법만을 사용해도 안전을 유지할 수 있는 체계를 구체적으로 살펴봅니다.

---

이 논문의 핵심 발견: 중요한 것은 마법의 동전이 아니라 '노동'이다

이 연구에서 저자들인 비히드 R. 아사디(Vahid R. Asadi), 리처드 클리브(Richard Cleve), 에릭 컬프(Eric Culf), 알렉스 메이(Alex May)는 새로운 관점에서 이 문제를 바라보기로 했습니다. 이전의 연구들은 사기꾼이 보유해야 하는 "마법의 동전"(큐비트)의 개수에 집중했습니다. 하지만 저자들은 동전을 가지고 있는 것만으로는 충분하지 않다는 것을 깨달았습니다. 사기꾼은 그 동전들로 무언가를 수행해야 합니다. 스위치를 올리고 계산을 수행하며 프로그램을 실행해야 합니다.

이 논문은 놀랍고 강력한 사실을 증명합니다: 성공적으로 속임수를 쓰기 위해서, 부정직한 플레이어는 엄청난 양의 양자 노동(quantum work)을 해야만 합니다.

구체적으로, 저자들은 사기꾼이 필요로 하는 양자 "게이트"(양자 컴퓨터가 계산을 수행하는 기본 단계)와 측정의 횟수가 수학 문제의 난이도와 직접적으로 연결되어 있음을 보여줍니다. 만약 정직한 사람이 많은 통신량을 요구하는 문제(두 숫자 목록을 곱하고 더하는 방식인 '내적(Inner Product)' 함수와 같은 특정 방식)를 풀어야 한다면, 사기꾼은 입력값의 크기에 비례하여 증가하는 횟수의 양자 연산을 반드시 수행해야 합니다.

이를 강도 영화에 비유해 보겠습니다. 예전 이야기들에서 도둑들은 단지 보물을 숨기기 위해 아주 큰 금고(많은 얽힘)만 있으면 되었습니다. 하지만 이 논문은 이렇게 말합니다. "잠깐만요! 금고가 있다고 해도, 열쇠를 얻으려면 마라톤을 뛰어야 합니다." 저자들은 특정 유형의 위치 검증 방식(f-routing 및 f-BB84)에 대해, 사기꾼이 가만히 앉아서 기다릴 수 없으며, 퍼즐의 크기에 대략 비례하는 횟수의 양자 단계를 사용하여 능동적으로 답을 계산해야 한다는 것을 증명했습니다.

"내적(Inner Product)" 테스트 케이스

이를 구체화하기 위해, 저자들은 **내적(Inner Product)**이라 불리는 특정 수학 문제를 통해 이론을 테스트했습니다. 당신과 친구가 각각 1,000개의 숫자(0 또는 1)로 이루어진 목록을 가지고 있다고 가정해 봅시다. 당신은 두 사람이 같은 위치에 "1"을 가지고 있는 총 횟수가 홀수인지 짝수인지 알고 싶어 합니다. 이것이 내적입니다.

논문에 따르면, 정직한 사람이 일반 컴퓨터에서 이 수학 문제를 푸는 것은 쉽고 빠르지만, 위치를 속이려는 사기꾼은 그 목록의 길이에 따라 선형적으로 증가하는 수의 양자 단계를 수행해야 합니다. 목록에 $n$개의 숫자가 있다면, 사기꾼은 대략 $n$번의 양자 단계가 필요합니다.

이는 정직한 사람과 사기꾼 사이에 거대한 격차를 만들어내기 때문에 매우 중요합니다:

• 정직한 사람: 단순한 수학(선형적 노력)과 아주 적고 고정된 양의 양자 작업(하나 또는 두 개의 큐비트를 보유하는 것과 같은)만을 필요로 합니다.
• 사기꾼: 기만을 성공시키기 위해 막대한 양의 양자 작업(선형적 노력)을 수행해야 합니다.

저자들은 수학적으로 이를 증명하여, "아래 선형적(sub-linear)"인 자원으로는 이 체계를 속일 수 없음을 보여주었습니다. 즉, 퍼즐이 커진다고 해서 아주 적은 양의 작업만으로 속임수를 쓸 수는 없다는 것입니다.

이 연구가 중요한 이유: "손실 허용(Loss-Tolerant)" 보너스

이 논문의 가장 멋진 점 중 하나는 이 체계가 손실 허용(loss-tolerant) 버전에도 적용된다는 것입니다. 현실 세계에서 빛의 광자(photon)와 같은 양자 신호를 먼 거리로 보내는 것은 매우 번거로운 일입니다. 많은 신호가 길을 잃거나 흡수될 수 있습니다. 이전의 이론들은 만약 신호를 너무 많이 잃게 되면 보안 보장이 사라질 수 있다고 시사했습니다.

그러나 저자들은 자신들의 새로운 경계(bound)가 이러한 지저치고 손실이 많은 조건에서도 유효함을 보여줍니다. 이는 정직한 사람이 양자 신호의 일부를 잃더라도, 사기꾼은 여전히 위치를 속이기 위해 그 막대한 양의 양자 노동을 수행해야 함을 의미합니다. 이는 마치 강도 영화에서 몇몇 장면이 편집되어 빠졌다고 하더라도, 도둑은 여전히 열쇠를 얻기 위해 전체 마라톤을 뛰어야 한다는 것과 같습니다.

무엇을 배제하는가

이 논문은 사기꾼이 아주 적은 양의 양자 작업만으로 속임수를 쓸 수 있다는 아이디어를 명시적으로 배제합니다. 입력값이 아무리 커지더라도 사기꾼이 적고 고정된 양의 양자 자원만을 필요로 하는 시스템을 설계할 수 있다는 희망에 반론을 제기합니다. 저자들은 이러한 특정 체계의 경우, 요구되는 작업량이 문제의 크기에 따라 늘어난다는 것을 보여줍니다.

또한 저자들은 단순히 "마법의 금고"의 크기(보유한 큐비트의 수)를 세는 것이 아니라, 실제적인 "노동"(수행된 게이트와 측정의 횟수)을 측정하는 것이라고 명확히 합니다. 이는 훨씬 더 엄격하고 현실적인 난이도 측정 방식입니다.

얼마나 확신하는가?

저자들은 자신들의 결과에 매우 확신하고 있습니다. 그들은 단순히 컴퓨터로 시뮬레이션을 돌려 가능성을 제시한 것이 아니라, 엄격한 수학적 증명을 제공했습니다. 만약 사기꾼이 예측된 경계보다 적은 양의 양자 단계를 사용하여 시스템을 깨뜨리려 한다면, 높은 정확도로 성공하는 것이 불가능하다는 것을 보여주었습니다. 이 증명은 사기꾼이 얽힘을 공유할 수 있는 경우와 시스템이 손실이 발생하는 경우를 모두 포함한 광범위한 시나리오에서 유효합니다.

요약하자면, 이 논문은 명확한 선을 긋습니다. 만약 이러한 특정 양자 방식을 사용하여 누군가의 위치를 검증하고자 한다면, 사기꾼이 속임수를 쓰기 위해 막대한 양의 힘든 양자 노동을 해야 한다는 것을 수학적으로 확신할 수 있습니다. 이 논문은 속임수의 난이도를 "얼마나 많은 마법을 가지고 있는가?"에서 "얼마나 열심히 일할 용의가 있는가?"로 바꿉냐며, 거대한 문제 앞에서 그 노동은 너무나도 무거운 짐이 됩니다.