문턱값 정리

이번 레슨에서 논의할 마지막 주제는 *문턱값 정리(threshold theorem)*로 알려진 매우 중요한 정리입니다. 여기서는 이 정리의 다소 비형식적인 진술을 제시합니다.

Theorem

문턱값 정리: 크기가 $N$인 양자 Circuit은 잡음이 있는 양자 Circuit으로 높은 정확도로 구현될 수 있으며, 이는 잡음이 있는 Circuit의 각 위치에서 오류가 발생할 확률이 고정된 0이 아닌 문턱값 $p_{\text{th}} > 0$ 미만이라는 조건에서 성립합니다. 잡음이 있는 Circuit의 크기는 양의 상수 $c$에 대해 $O(N \log^c(N))$으로 스케일됩니다.

간단히 말하면, 이 정리는 $N$이 원하는 만큼 크더라도 $N$개의 Gate로 이루어진 임의의 양자 Circuit이 있다면, 잡음 수준이 $N$과 무관한 특정 문턱값 미만인 한 해당 Circuit을 잡음이 있는 양자 Circuit을 사용하여 높은 정확도로 구현할 수 있다고 말합니다. 게다가 이를 수행하는 데 드는 비용이 너무 크지도 않은데, 필요한 잡음 Circuit의 크기는 $N$에 $N$의 로그의 어떤 상수 거듭제곱을 곱한 정도의 규모입니다.

이 정리를 좀 더 형식적으로 진술하려면 잡음 모델에 대해 구체적으로 명시해야 하지만, 이번 레슨에서는 다루지 않습니다. 예를 들어, 이 정리는 앞서 언급된 독립 확률적 잡음 모델, 즉 Circuit의 각 가능한 위치에서 오류가 문턱값보다 엄격히 작은 어떤 확률로 독립적으로 발생하는 모델에 대해 증명될 수 있지만, 오류들 사이에 상관관계가 있을 수 있는 보다 일반적인 잡음 모델에 대해서도 증명될 수 있습니다.

이것은 이론적 결과이며, 일반적으로 증명되는 방식이 반드시 실용적인 접근법으로 이어지지는 않지만, 그럼에도 불구하고 이 정리는 큰 실용적 중요성을 지닙니다. 특히, 이 정리는 잡음이 있는 구성 요소를 사용하여 양자 계산을 수행하는 데 근본적인 장벽이 없음을 확립합니다. 이들 구성 요소의 오류율이 문턱값 미만인 한, 임의의 크기의 신뢰할 수 있는 양자 Circuit을 구축하는 데 사용될 수 있습니다. 이 정리의 중요성을 다른 방식으로 표현하자면, 만약 이 정리가 참이 아니었다면 대규모 양자 계산이 현실이 되는 것을 상상하기 어려웠을 것입니다.

이 정리(의 형식적 진술)에 대한 형식적 증명에는 많은 기술적 세부사항이 포함되어 있으며, 그러한 세부사항은 여기서 다루지 않겠습니다. 그러나 본질적인 아이디어는 직관적인 수준에서 설명될 수 있습니다. 이 설명을 가능한 한 간단히 하기 위해, 오류 수정에 $7$-qubit Steane code를 사용한다고 상상해 봅시다. 이는 실제 물리적 구현에서는 비실용적인 선택일 것이며, 이는 매우 작은 문턱값 $p_{\text{th}}$로 반영될 것입니다. 그러나 주요 아이디어를 전달하기에는 적합합니다. 또한 이 설명에서는 잡음 모델에 대해 다소 개략적으로 다루며, fault-tolerant 구현의 각 위치에 확률 $p$로 독립적으로 오류가 발생한다고 가정합니다.

이제 확률 $p$가 구현하려는 Circuit의 크기 $N$의 역수보다 크다면, 어딘가에서 오류가 발생할 가능성이 매우 높습니다. 따라서 우리는 이 레슨에서 설명한 방법을 따라 이 Circuit의 fault-tolerant 구현을 실행해 볼 수 있습니다. 그런 다음 앞서 제시된 질문을 던져볼 수 있습니다: 이것이 상황을 나아지게 만드는 것일까요, 아니면 오히려 악화시키는 것일까요?

각 위치에서의 오류 확률 $p$가 너무 크다면, 우리의 노력은 도움이 되지 않고 오히려 상황을 악화시킬 수도 있습니다. 마치 오류 확률이 약 3.23%를 넘을 때 $9$-qubit Shor code가 도움이 되지 않는 것과 같습니다. 특히 fault-tolerant 구현은 원래 Circuit보다 상당히 크기 때문에 오류가 발생할 수 있는 위치가 훨씬 더 많습니다.

그러나 $p$가 충분히 작다면, 우리가 수행하고 있는 logical 계산의 오류 확률을 줄이는 데 성공할 것입니다. (형식적 증명에서는 이 지점에서 매우 신중해야 합니다. logical 계산의 오류가 반드시 원래의 잡음 모델로 정확히 기술되지는 않을 것이기 때문입니다. 사실 이것이 오류가 독립적이지 않을 수 있는 더 까다로운 잡음 모델이 필요한 이유입니다. 하지만 이 설명에서는 이 세부사항을 덮어두겠습니다.)

좀 더 자세히 말하면, 원래 Circuit에서 logical 오류가 발생하려면 Steane code가 코드 블록 내의 단일 오류를 수정할 수 있다는 점을 고려할 때, fault-tolerant 구현에서 동일한 코드 블록에 최소 두 개의 오류가 떨어져야 합니다. 동일한 코드 블록에 두 개 이상의 오류가 발생하는 방식에는 여러 가지가 있음을 염두에 두면, 원래 Circuit의 각 위치에서 logical 오류가 발생할 확률이 어떤 고정된 양의 실수 $C$에 대해 기껏해야 $C p^2$임을 논할 수 있습니다. 여기서 $C$는 코드와 우리가 사용하는 gadget에 의존하지만, 결정적으로 원래 Circuit의 크기 $N$에는 의존하지 않습니다. 만약 $p$가 우리가 문턱값 $p_{\text{th}}$로 택할 수 있는 $1/C$보다 작다면, 이는 오류의 감소로 이어집니다.

그러나 이 새로운 오류율이 여전히 전체 Circuit이 올바르게 작동하기에는 너무 높을 수 있습니다. 이 시점에서 자연스러운 해결책은 더 나은 코드와 더 나은 gadget을 선택하여 구현이 제대로 작동할 만한 수준으로 오류율을 낮추는 것입니다. 이론적으로 이것이 가능하다는 것을 논증하는 간단한 방법은 *연쇄(concatenate)*하는 것입니다. 즉, 원래 Circuit의 fault-tolerant 구현을 또 하나의 양자 Circuit인 것처럼 간주한 다음, 같은 방식을 사용하여 이 새로운 Circuit을 fault-tolerant하게 구현할 수 있습니다. 그런 다음 원래 계산이 작동할 수 있는 수준으로 오류율을 낮출 때까지 이 과정을 반복해서 수행할 수 있습니다.

이 방법을 통해 오류율이 어떻게 감소하는지에 대한 대략적인 감을 잡기 위해, 몇 번의 반복에 대해 어떻게 작동하는지 살펴봅시다. 엄밀한 분석에는 여기서 생략한 다양한 기술적 세부사항을 고려해야 함에 유의해야 합니다.

원래 Circuit의 위치에 대한 오류 확률 $p$에서 시작합니다. $p < p_{\text{th}} = 1/C$라고 가정하면, 첫 번째 반복 후 logical 오류율은 $Cp^2 = (Cp) p$로 제한될 수 있습니다. fault-tolerant 구현을 또 하나의 Circuit으로 취급하고 이를 fault-tolerant하게 구현하면, logical 오류율에 대한 다음과 같은 한계를 얻습니다.

$$C \bigl((Cp) p \bigr)^2 = (Cp)^3 p.$$

또 한 번의 반복은 오류 한계를 다음과 같이 더 줄입니다.

$$C \bigl((Cp)^3 p \bigr)^2 = (Cp)^7 p.$$

이런 식으로 총 $k$번의 반복을 계속하면 (원래 Circuit에 대한) logical 오류율은 다음과 같이 제한됩니다.

$$(Cp)^{2^k - 1} p,$$

이는 $k$에 대해 *이중 지수적(doubly exponential)*으로 감소합니다.

이는 오류율을 극도로 작게 만드는 데 너무 많은 반복이 필요하지 않다는 것을 의미합니다. 한편, Circuit은 연쇄의 각 레벨마다 크기가 커지지만, 그 크기는 레벨 수 $k$에 대해 *단일 지수적(singly exponentially)*으로만 증가합니다. 이는 fault-tolerance의 각 레벨마다 크기가 사용되는 gadget의 최대 크기로 정해지는 배수 이하로만 증가하기 때문입니다. 모든 것을 종합하고 연쇄 레벨 수에 대한 적절한 선택을 하면, 문턱값 정리를 얻게 됩니다.

그렇다면 실제 문턱값은 얼마나 될까요? 그 답은 사용된 코드와 gadget에 따라 달라집니다. Steane code와 마법 상태 증류(magic state distillation)를 사용하는 경우 매우 작으며 실제로 달성하기 어려울 가능성이 높습니다. 그러나 surface code와 최신 gadget을 사용하면 문턱값은 0.1%에서 1% 수준으로 추정되고 있습니다.

새로운 코드와 방법이 발견됨에 따라 문턱값이 증가할 것으로 기대할 수 있으며, 동시에 실제 물리적 구성 요소의 잡음 수준은 감소할 것입니다. 대규모 양자 계산을 fault-tolerant하게 구현할 수 있는 지점에 도달하는 것은 쉽지 않을 것이며, 하룻밤 사이에 일어나지도 않을 것입니다. 그러나 이 정리는 양자 코드와 양자 하드웨어의 발전과 함께, 대규모 fault-tolerant 양자 컴퓨터를 구축한다는 궁극적 목표를 향해 계속 나아가는 우리에게 낙관의 근거를 제공합니다.

강의 후 설문조사

이 강좌를 완료하신 것을 축하합니다! 다음 간단한 설문조사를 작성하여 저희 강좌를 개선하는 데 도움을 주세요. 여러분의 피드백은 저희 콘텐츠 제공과 사용자 경험을 향상시키는 데 사용됩니다. 감사합니다!