Verifiable blind probabilistic error cancellation

당신이 거대하고 불가능한 퍼즐을 풀려고 노력하고 있다고 상상해 보십시오. 하지만 당신은 직접 할 수 있는 조각들도, 테이블도 없습니다. 그래서 당신은 잠긴 방 안에 있는 낯선 사람을 고용하여 당신 대신 그 일을 하게 합니다. 이것이 바로 "클라우드 양자 컴퓨팅"의 꿈입니다. 즉, 현재의 기계로는 너무 어려운 문제들을 강력하고 원격에 있는 양자 컴퓨터가 해결하도록 하는 것입니다. 하지만 함정이 있습니다. 양자 컴퓨터는 믿을 수 없을 정도로 취약합니다. 마치 유리 조각품과 같아서, 너무 세게 쳐다보거나 공기가 너무 건조하기만 해도 산산조각이 나버립니다. 이 "노이즈(noise)"는 오류를 만들어내어 답을 신뢰할 수 없게 만듭니다.

이를 해결하기 위해 과학자들은 "확률적 오류 제거(Probabilistic Error Cancellation, PEC)"라는 기술을 개발했습니다. 이것은 수학을 위한 노이즈 캔슬링 헤드폰과 같습니다. 만약 당신이 정전기(노이즈)의 정확한 패턴을 알고 있다면, 이를 상쇄할 수 있는 반대되는 소리를 재생하여 깨끗한 신호만을 남길 수 있습니다. 하지만 이것은 당신이 반대되는 소리를 만드는 사람을 신뢰할 수 있을 때만 작동합니다. 만약 잠긴 방 안의 낯선 사람이 속임수를 쓰는 사람이라면, 그는 노이즈를 제거하는 척하면서 실제로는 당신의 퍼즐을 망쳐놓을 수도 있고, 혹은 노이즈가 무엇인지에 대해 거짓말을 할 수도 있습니다. 지금까지는 그가 정직하게 일을 수행하고 있는지, 그리고 실제로 오류를 고치고 있는지 확인할 방법이 없었습니다. 이 논문은 그 낯선 사람이 정직하면서도 실제로 노이즈를 고치고 있음을, 당신이 결코 그들의 방 안을 들여다보지 않고도 보장해 주는 초정밀, 마법 같은 심판 역할을 하는 새로운 방법을 소개합니다.

---

문제점: 믿을 수 없는 마법 상자

당신이 양자 컴퓨터에게 "이 새로운 분자의 에너지는 얼마인가?"와 같은 질문을 던지고 싶다고 가정해 봅시다. 당신의 컴퓨터는 충분히 강력하지 않기 때문에 당신은 질문을 원격 서버(the "Server")로 보냅니다. 하지만 이 서버는 신뢰할 수 없습니다. 그것은 폭주하는 AI일 수도 있고, 결함이 있는 기계일 수도 있으며, 혹은 당신을 속이려는 악의적인 행위자일 수도 있습니다.

과거에 과학자들은 이를 처리하기 위해 두 가지 방법을 사용했습니다:

1. 블라인드 연산 (Blind Computation): 당신은 비밀 코드로 명령을 보내서 서버가 당신이 무엇을 계산하고 있는지 모르게 할 수 있습니다. 이는 당신의 비밀을 안전하게 지켜주지만, 만약 서버가 실수를 하거나(혹은 거짓말을 하면), 당신은 알 방법이 없습니다. 당신은 그저 틀린 답을 얻게 될 뿐입니다.
2. 오류 수정 (Error Correction): 당신은 노이즈를 고치려고 시도할 수 있습니다. 하지만 표준적인 오류 수정은 많은 양의 추가적인 "예비" 큐비트(양자 비트)를 필요로 하는데, 현재의 기계들은 이를 갖추고 있지 않습니다.

그 후에 **확률적 오류 제거 (PEC)**가 등장했습니다. 이것은 영리한 소프트웨어 트릭입니다. 추가적인 하드웨어가 필요한 대신, 이 방식은 다양한 "노이즈 캔슬링" 동작들을 섞어서 계산을 여러 번 실행합니다. 결과들을 평균함으로써, 수학적으로 노이즈를 뺍니다. 문제는 무엇일까요? PEC는 서버가 노이즈에 대해 정직하다는 것을 전제로 합니다. 만약 서버가 악의적이라면, 그는 노이즈 패턴에 대해 거짓말을 할 수 있고, 당신의 "상쇄" 작업은 오히려 답을 더 나쁘게 만들 것입니다. 당신은 서버가 규칙을 따르고 있는지, 그리고 그가 제거하고 있는 노이즈가 진짜인지 확인할 방법이 필요합니다.

해결책: VBPEC (마법의 심판)

Bo Yang, Elham Kashefi, 그리고 Harold Ollivier는 **검증 가능한 블라인드 확률적 오류 제거 (Verifiable Blind Probabilistic Error Cancellation, VBPEC)**라고 불리는 새로운 프로토콜을 만들었습니다. 이것은 다음 세 가지를 동시에 결합한 최초의 시스템입니다:

1. 블라인드 (Blindness): 서버는 당신이 무엇을 계산하는지 절대 알 수 없습니다.
2. 검증 가능성 (Verification): 서버가 속임수를 쓰지 않았음을 수학적으로 증명할 수 있습니다.
3. 오류 제거 (Error Cancellation): 서버가 실제로 노이즈를 고쳐서, 당신에게 더 나은 답을 제공합니다.

이 마법이 어떻게 작동하는지 몇 가지 비유를 통해 설명하겠습니다.

1. 양자 비밀을 위한 "원타임 패드 (One-Time Pad)"

서버를 보이지 않게 유지하기 위해, 프로토콜은 "양자 원타임 패드"라고 불리는 것을 사용합니다. 당신이 메시지를 서버에 보내는데, 모든 글자를 무작위적이고 깨뜨릴 수 없는 봉투에 담아 보내는 것을 상상해 보십시오. 서버는 봉투를 열고, 작업을 수행한 뒤, 다시 새로운 무작위 봉투에 담아야 합니다. 봉투들이 무작위이기 때문에, 서버는 오직 알 수 없는 암호문만을 보게 됩니다. 서버는 당신이 분자의 에너지를 계산하고 있는지, 아니면 단순히 열까지 숫자를 세고 있는지 알 수 없습니다. 이는 **완벽한 블라인드(완전한 익명성)**를 보장합니다.

2. 혼돈을 주사위 게임으로 바꾸기

저자들은 아주 멋진 사실을 발견했습니다. 무작위 봉투(양자 원타임 패드) 때문에, 서버가 저지르는 어떤 실수나 속임수라도 특정 유형의 무작위 오류인 "스토카스틱 파울리 채널 (stochastic Pauli channel)"로 뒤섞여 버린다는 것입니다.
이렇게 생각해보십시오: 만약 서버가 퍼즐 조각을 비틀어서 당신을 방해하려 한다면, 무작위 봉투는 그 조각을 다시 단순한 "플립(flip)"(예: 동전을 앞면에서 뒷면으로 바꾸는 것)으로 되돌려 놓습니다. 서버는 더 이상 정교한 짓을 할 수 없습니다. 그는 오직 동전을 던지는 일밖에 할 수 없습니다. 이는 추적하고 상쇄하기 매우 쉬운 일입니다.

3. 함정과 통계적 테스트

이제, 어떻게 거짓말쟁이를 잡을 수 있을까요? 프로토콜은 "함정(traps)"을 사용합니다. 당신이 서버에게 실제 퍼즐 조각과 가짜 "함정" 조각들을 섞어서 보낸다고 상상해 보십시오. 함정 조각들은 만약 서버가 정직하다면 특정한 예측 가능한 위치에 놓이도록 설계되었습니다. 만약 서버가 속임수를 쓴다면, 함정들은 잘못된 위치에 놓이게 됩니다.

이전의 프로토콜들은 단순히 함정이 얼마나 실패했는지를 세었습니다. 만약 너무 많은 함정이 실패했다면, "게임 끝, 당신은 속였어요!"라고 말하는 식이었죠. 하지만 이것은 너무 엄격합니다. 만약 기계가 단지 약간의 노이즈가 있는 상태라면(속이는 것이 아니라), 몇 개의 함정이 실패할 수도 있는데, 그러면 좋은 결과까지 버리게 됩니다.

VBPEC은 게임의 방식을 바꿉니다. 단순히 실패 횟수를 세는 대신, 함정의 결과를 사용하여 노이즈가 정확히 얼마나 발생하는지 추정합니다. 이것은 요리사가 수프를 맛보는 것과 같습니다. "너무 짜니까 버려!"라고 말하는 대신, 요리사는 맛을 보고 "원래보다 10% 더 짜네"라고 말하는 것입니다. 그런 다음 요리사는 그 지식을 사용하여 레시피를 조정합니다.

VBPEC에서 클라이언트(당신)는 함정의 결과를 사용하여 "노이즈 맵(noise map)"을 계산합니다. 만약 노이즈 맵이 서버가 해야 할 행동과 일치하면, 클라이언트는 결과를 수락합니다. 만약 노이즈 맵이 이상해 보인다면(예를 들어 서버가 거짓말을 하고 있다면), 클라이언트는 결과를 거부합니다.

큰 승리: 능동적 노이즈 캔슬링

가장 흥미로운 부분은 서버가 정직하지만 기계가 노이즈가 있는 상황에서 일어나는 일입니다.

• 기존 방식: 노이즈가 너무 높으면, 프로토콜은 결과를 100% 거부합니다. 당신은 아무것도 얻지 못합니다.
• VBPEC 방식: 프로토콜은 노이즈를 감지하고, 그것이 예상된 패턴과 일치하는지 확인한 다음, 능동적으로 이를 상쇄합니다. 결과적으로 클라이언트는 결과를 수락하고 교정된 답을 얻습니다.

이 논문은 서버가 정직하다면, 올바른 노이즈 상쇄 답변을 얻을 확률이 실행 횟수가 늘어남에 따라 거의 100%에 육박한다는 것을 증명합니다. 설령 노이즘 모델이 완벽하지 않더라도(예를 들어 기계가 예상과 약간 다르더라도), 그 차이가 너무 크지 않은 한 프로토콜은 여전히 작동할 만큼 견고합니다.

이것이 당신에게 의미하는 바

이 논문은 단순히 "우리는 이것이 작동할 것 같다고 생각한다"라고 말하는 것이 아닙니다. 이 논문은 VBPEC가 **결합 가능한 보안성(composably secure)**을 가진다는 엄격한 수학적 증명을 제공합니다. 이는 당신이 이 시스템을 더 큰 시스템의 구성 요소로 사용할 수 있으며, 보안 보장이 유지된다는 것을 의미합니다.

저자들은 다음을 보여줍니다:

• 추가적인 양자 하드웨어가 필요하지 않습니다 (공간 오버헤드가 없음).
• 유일한 비용은 계산을 몇 번 더 실행하는 것뿐입니다 (이는 새로운 하드웨어를 구축하는 것에 비하면 매우 저렴합니다).
• 당신은 당신을 속이려 할지도 모르는 낯선 이가 소유한 컴퓨터라 할지라도 그 답을 신뢰할 수 있습니다.

요약하자면, VBPEC는 "신뢰할 수 없고 노이즈가 많은 양자 클라우드"를 위험한 도박에서 신뢰할 수 있는 도구로 바꿉니다. 이는 오늘날의 지저분하고 노이즈가 많은 양자 컴퓨터의 현실과, 안전하고 완벽한 암호학의 세계 사이의 간극을 메워줍니다. 이는 우리가 원격 양자 컴퓨터에게 세상에서 가장 어려운 문제를 풀어달라고 자신 있게 요청할 수 있는 날을 향한 중대한 진전입니다. 그 답이 진짜이며, 사적이고, 정확하다는 것을 알면서 말입니다.