Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

양자 컴퓨터는 오늘날의 기계가 해결하는 데 수천 년이 걸릴 문제를 해결할 가능성을 약속하지만, 믿을 수 없을 정도로 취약합니다. 환경으로부터 발생하는 아주 작은 방해조차도 그들이 보유한 섬세한 정보를 뒤섞어 놓을 수 있습니다. 작동하는 기계를 만들기 위해 과학자들은 이 취약한 데이터를 '양자 오류 정정'이라 불리는 보호층으로 감싸야 합니다. 이 시스템은 마치 문서의 오타를 고치는 맞춤법 검사기처럼 끊임없이 실수를 점검하지만, 오타를 고치는 대신 양자 비트, 즉 큐비트(qubit)의 물리적 오류를 식별하고 되돌립니다. 이러한 기계를 위한 가장 유망한 설계들은 '위상 기하학적 코드(topological codes)'로 알려진 특정 유형의 보호 방식을 사용합니다. 이 시스템에서 정보는 단일 입자에 저장되는 것이 아니라 광범위한 2차원 큐비트 격자에 분산되어 저장되므로, 국소적인 노이즈에 강한 특성을 가집니다.

이 보호 기능이 현실 세계에서 작동하려면, 컴퓨터는 점검 결과를 읽고 정확히 무엇이 잘못되었는지 파악할 수 있어야 하며, 이 과정을 '디코딩(decoding)'이라고 부릅니다. 목표는 관찰된 오류에 대한 가장 단순하고 가능성 높은 설명을 찾는 것입니다. 만약 컴퓨터가 이러한 오류를 빠르고 정확하게 디코딩하지 못하면, 보호 기능은 실패하고 계산은 붕괴됩니다. 오랫동안 연구자들은 가장 흔한 유형의 오류에 대해 이 가장 단순한 설명을 찾는 것이 컴퓨터가 효율적으로 처리할 수 있는 작업이 되기를 희망해 왔습니다. 그러나 루아이 바지(Louay Bazzi)와 조지스 카터(Georges Khater)의 새로운 연구는 가장 강력한 오류 정정 체계에 대해서는 이러한 희망이 잘못되었을 수 있음을 시사합니다. 그들은 특정 고급 양자 코드의 경우, 완벽한 해답을 찾는 것이 너무나 계산적으로 어려워서 최선의 지름길을 사용하더라도 시스템이 커짐에 따라 오류를 충분히 작게 유지하는 데 결국 실패할 것임을 증명했습니다.

연구진은 두 가지 선도적인 양자 코드 제품군, 즉 표면 코드(surface codes)와 컬러 코드(color codes)에 집중했습니다. 표면 코드는 기존 하드웨어 설계와 호환되기 때문에 양자 컴퓨터를 구축하는 데 현재 가장 선호되는 방식이며, 컬러 코드는 계산을 수행하는 데 독특한 이점을 제공합니다. 두 시스템 모두에서 컴퓨터는 '신드롬(syndromes)'이라 불리는 일련의 신호를 측정하며, 이는 오류가 발생한 위치를 나타내는 지도 역할을 합니다. 디코딩 작업은 오류 지점들을 연결하는 경로를 격자 위에 그리는 것인데, 이때 최소한의 '노력' 또는 '가중치(weight)'를 필요로 하는 방식으로 연결해야 합니다. 가장 단순한 시나리오에서 이것은 종이 위에 점들을 가장 짧은 실로 연결하는 것과 같습니다. 일부 오래되고 더 단순한 코드의 경우, 이것은 빠르게 해결할 수 있는 간단한 수학 문제입니다.

바지와 카터는 오류가 더 복적으로 발생하는 상황, 구체적으로 서로 다른 유형의 실수가 동시에 발생하여 서로에게 영향을 미치는 상황인 '탈분극 채널(depolarizing channel)'을 조사했습니다. 그들은 근본적인 질문을 던졌습니다. "항상 최선의 답에 매우 근접한 해답을 찾을 수 있는 빠르고 효율적인 알고리즘이 존재하는가?" 이 질문에 답하기 위해 그들은 컴퓨터 시뮬레이션을 실행하는 대신 엄격한 수학적 증명을 구축했습니다. 그들은 표면 코드와 컬러 코드의 경우, 최선의 정답을 찾는 문제가 단순히 어려운 수준이 아니라 근본적으로 다루기 불가능한(intractable) 방식임을 보여주었습니다. 그들은 아무리 영리한 컴퓨터 프로그램이라 할지라도, 양자 컴퓨터의 크기가 커짐에 따라 알고리즘의 최선 추측치에 포함된 절대적 오류가 커진다는 것, 즉 알고리즘의 해답과 완벽한 정답 사이의 간극이 무시할 수 없는 수준으로 벌어진다는 것을 증명했습니다.

연구진은 특정 수의 큐비트를 가진 양자 컴퓨터에 대해, 어떤 빠른 알고리즘이라도 완벽한 정답과 비교했을 때 상당한 차이를 보이는 해답을 필연적으로 만들어낸다는 것을 입증했습니다. 구체적으로, 토릭 코드(toric code)와 4.8.8 컬러 코드의 경우, 해답의 오차는 전체 큐비트 수의 14제곱근과 관련된 속도로 증가한다는 것을 발견했습니다. 평면 표면 코드(planar surface code)의 경우, 오차는 큐비트 수의 18제곱근과 관련된 속도로 증가합니다. 이 수치들이 작아 보일 수 있지만, 이는 단순히 컴퓨터를 더 똑똑하거나 빠르게 만든다고 해서 좁힐 수 없는 격차를 의미합니다. 연구진은 만약 컴퓨터 과학 분야에서 매우 어렵다고 알려진 문제가 쉽다는 것이 밝혀지는 중대한 돌파구가 일어나지 않는 한, 다항 시간(polynomial-time) 알고리즘으로는 이 간극 내의 해답을 보장할 수 없다고 확립했습니다.

이 결론에 도달하기 위해 저자들은 '가젯(gadgets)'이라 불리는 작고 모듈화된 구조를 사용하여 복잡한 논리적 프레임워크를 구축했습니다. 이 가젯들은 마치 자물쇠가 올바른 열쇠가 있어야만 문을 열도록 보장하는 것처럼, 특정 규칙을 강제하도록 설계된 작고 독립적인 기계라고 상상할 수 있습니다. 그들은 이 가젯들을 격자 형태로 배치하여 해결하기 어려운 것으로 알려진 논리 퍼즐의 동작을 모방했습니다. 이 가젯들을 정교하게 간격을 두어 배치함으로써, 퍼즐의 해답이 격자를 가로질러 지름길을 택할 수 없도록 했습니다. 그들은 이 퍼즐을 효율적으로 푸는 유일한 방법이 기초적인 논리 문제를 푸는 것임을 증명했는데, 대규모 입력에 대해 이 문제를 빠르게 푸는 것은 불가능하다는 사실을 이미 알고 있습니다. 이 방법은 알려진 난제의 어려움을 양자 오류 디코딩의 어려움으로 직접 변환할 수 있게 해주었습니다.

이 연구는 해당 분야의 최근 낙관론에 대해서도 다루었습니다. 이 연구 직전에 다른 연구자들은, 동일한 코드들에 대해 고정된 작은 비율의 오차를 수용할 용의가 있다면 완벽한 정답에 매우 근접할 수 있다는 사실을 발견했습니다. 이는 효율적인 디코딩이 손에 닿을 곳에 있다는 믿음으로 이어졌습니다. 바지와 카터의 연구는 이러한 낙관론의 한계를 명확히 합니다. 그들은 최선의 답에 매우 가까워질 수는 있지만, 임의로 가까워질 수는 없다는 것을 보여주었습니다. 시스템이 확장됨에 따라 오차가 무시할 수 없을 만큼 커지는 단단한 벽이 존재합니다. 이 차이는 매우 중요한데, 양자 컴퓨팅에서는 아주 작은 지속적인 오류조차도 시간이 흐름에 따라 축적되어 계산을 파괴할 수 있기 때문입니다.

이 발견의 함의는 양자 하드웨어의 미래에 있어 매우 중요합니다. 이는 엔지니어들이 모든 크기의 양자 컴퓨터를 위해 단일한 범용 알고리즘에 의존할 수 없음을 시사합니다. 그들이 더 큰 기계를 구축함에 따라, 디코딩 과정의 정밀도가 낮아지는 것을 받아들이거나, 이러한 특정 수학적 함정을 피할 수 있는 완전히 새로운 방식의 코드를 구조화해야 할 수도 있습니다. 연구진은 또한 다른 과학자들이 다양한 유형의 양자 시스템에서 디코딩의 한계를 탐구하는 데 도움이 될 수 있는 새로운 '가젯' 도구 세트와 상호작용을 제어하는 방법을 개발했습니다. 그들의 연구는 양자 컴퓨터가 불가능하다고 말하는 것이 아니라, 그들의 오류를 얼마나 효율적으로 관리할 수 있는지에 대한 명확한 경계선을 긋고 있습니다.

결국, 이 논문은 냉혹하지만 필요한 현실 점검을 제공합니다. 이는 결함 허용(fault-tolerant) 양자 컴퓨터로 가는 길이 단순히 더 나은 하드웨어나 더 빠른 소프트웨어를 만드는 문제만이 아님을 확인시켜 줍니다. 그것은 오류 정정의 수학 속에 존재하는 근본적인 복잡성을 드러내며, 이를 극복하기 위해서는 새로운 전략이 필요함을 보여줍니다. 연구진은 현재 고려되고 있는 가장 유망한 코드들에 대해, 완벽하고 빠른 디코더라는 꿈은 수학적으로 도달 불가능하다는 것을 보여주었습니다. 이제 과제는 이러한 한계 내에서 작동하는 방법을 찾는 것으로 전환되었습니다. 아마도 더 쉽게 디코딩할 수 있는 코드를 설계하거나, 작동하는 양자 기계를 만드는 경쟁 속에서 어느 정도의 근사치는 불가피하다는 점을 받아들이는 방향이 될 것입니다.