Bounded decoding complexity in transversal circuits with magic state injection

기술 요약: 매직 상태 주입을 포함한 가로형 회로의 유계된 디코딩 복잡도

문제 정의
클리포드 게이트를 가로형(transversally)으로 구현하고 매직 상태 주입을 통해 보편성을 달하는 결함 허용 양자 컴퓨팅 아키텍처는 시공간 상관 디코딩(space-time correlated decoding)의 복잡성이라는 중대한 확장성 문제에 직면해 있습니다. 예를 들어, 게이트당 한 번의 라운드로 디코딩 라운드 수를 줄이는 방식은 시간 오버헤드를 낮추지만, 여러 회로 레이어에 걸쳐 신드롬 정보를 상관시켜야 하는 필요성을 수반합니다. 이러한 스킴에서는 논리적 측정을 디코딩하기 위해, 측정 결과에 영향을 미칠 수 있는 오류가 발생할 수 있는 시공간 영역을 식별하도록 측정 연산자를 회로 전체로 역전파(backpropagation)해야 합니다. 회로 깊이가 증가함에 따라 이러한 역전파 영역은 일반적으로 확장되며, 이는 디코딩 그래프가 회로의 부피(volume)와 함께 성장하게 만듭니다. 이는 클래식 디코딩이 대규모 계산에서 병목 현상이 될 수 있다는 우려를 낳는데, 왜냐하면 디코딩은 일반적으로 크기에 따라 성능이 저하되는 문제로 간주되기 때문입니다.

방법론
저자들은 재구성 가능하고 효과적으로 비국소적인 연결성을 지원하는 최근의 실험적 플랫폼(트랩 이온, 중성 원자)에서 영감을 얻은 설정에서 디코딩 복잡도를 분석합니다. 본 연구는 다음으로 구성된 무작위 회로에 초점을 맞춥니다:

1. 가로형 클리포드 레이어: CNOT, H, S와 같은 게이트를 사용하여 1D 벽돌 구조(brickwork geometry) 또는 보충 분석에서의 전방향(all-to-all) 연결성을 갖도록 배치됩니다.
2. 매직 상태 주입: 비-클리포드 T-게이트는 리소스 상태 $|T\rangle_L$을 이용한 게이트 텔레포테이션을 통해 구현되며, 여기에는 중간 회로 측정 및 조건부 피드포워드가 포함됩니다.

핵심 방법론은 다음과 같습니다:

• 신뢰할 수 있는 측정 곱(Reliable Measurement Products): 모든 측정을 개별적으로 디코딩하는 대신, 저자들은 초기 상태 안정기(stabilizer)와의 교환 관계를 기반으로 측정을 "신뢰할 수 있음" 또는 "신뢰할 수 없음"으로 분류하는 전략을 활용합니다. 신뢰할 수 없는 측정은 무작위 결과를 할당받거나, "신뢰할 수 있는 곱"(역전파된 연산자가 모든 초기 안정기와 교환되는 측정값들의 곱)을 형성하기 위해 이전 측정들과 결합됩니다.
• 순차적 디코딩: 디코딩은 순차적으로 수행됩니다. 일단 신뢰할 수 있는 곱이 디코딩되고 수정 사항이 확정(commit)되면, 관련된 신드롬 데이터는 향후 디코딩 문제에서 제외됩니다. 이는 이미 해결된 신드롬 정보가 재처리되는 것을 방지합니다.
• 역전파 분석: 신뢰할 수 있는 곱에 대한 디코딩 그래프는 해당 곱을 회로를 통해 역전파함으로써 구축됩니다. 이 그래프의 크기(안정기 체크 횟수로 측정)는 디코딩 복잡도의 대리 지표 역할을 합니다.
• 수치 시뮬레이션: 저자들은 다양한 논리 큐비트 수($N$)와 매직 상태 주입 확률($\kappa$)을 가진 무작위 회로를 시뮬레이션합니다. 이들은 유효 디코딩 부피를 결정하기 위해 이전 단계에서 이미 처리된 체크를 제외한 "정규화된 체크 횟수"($N_C$)를 추적합니다.

주요 기여 및 결과

1. 유계된 디코딩 부피: 주요 발견은 중간 회로 측정에 대한 디코딩 복잡도가 계산 큐비트의 수($N$)와 회로 깊이($t$) 모두에 독립적인 정체 평균(stationary average)에 도달한다는 것입니다.

   • 과도기 영역(초기 회로 시간)에서는 신뢰할 수 없는 측정이 축적됨에 따라 체크 횟수가 증가합니다.
   • 정체 영역(stationary regime)에서, 평균 정규화 체크 횟수 $N_{C,\infty}$는 새로 생성된 체크와 레이어당 생성되는 신뢰할 수 있는 곱의 비율에 의해 결정됩니다.
   • 저자들은 다음과 같은 해석적 예측을 도출했습니다:
     $$N_{C,\infty} = \frac{3(2 + \kappa)}{\kappa}$$
     여기서 $\kappa$는 레이어당 T-게이트 주입 확률입니다. 이는 디코딩 부피가 매직 상태 주입 밀도에 반비례함을 나타냅니다.

2. 대규모 인스턴스의 지수적 억제: 정체 영역에서의 디코딩 부피 분포는 $p(N_C) \sim e^{-b N_C}$ 형태의 지수 꼬리를 보입니다. 붕괴율 $b$는 $\kappa$가 증가함에 따라 증가하며($\alpha \approx 0.98$인 $\kappa^\alpha$와 유사), 이는 매직 상태의 밀도가 높을수록 평균 디코딩 부하를 줄일 뿐만 아니라, 계산 비용이 큰 대규모 디코딩 인스턴스를 마주칠 확률을 지수적으로 억제함을 의미합니다.

3. 곱 선택의 무관성: 신뢰할 수 있는 곱을 구성하는 방법은 유일하지 않으며, 측정들을 결합하는 데 있어 지수적으로 많은 해가 존재합니다. 저자들은 네 가지 선택 전략(가우스 소거법, 무작위 선택, 순서 통계 디코딩을 이용한 신념 전파, MaxSAT을 통한 정확한 최소 해밍 가중치 계산)을 테스트했습니다. 그 결과, 선택된 곱들의 해밍 가중치(구성 측정값의 수)에는 상당한 차이가 있음에도 불구하고, 결과적인 디코딩 복잡도 통계는 구별할 수 없을 정도로 동일하다는 것을 발견했습니다. 이는 곱의 선택을 위해 계산적으로 비용이 많이 드는 최적화를 수행할 필요가 없으며, 단순한 가우스 소거법만으로도 충분함을 시사합니다.

4. 아키텍처 전반의 견고성: (유계성 및 정체 분포와 같은) 질적 특성은 서로 다른 회로 연결성(1D 벽돌 구조 vs 전방향 연결성) 및 클리포드 게이트 앙상블 전반에 걸쳐 지속됩니다.

의의 및 주장
본 논문은 가로형 아키텍처에서 보편성을 달성하기 위해 사용되는 바로 그 메커니즘인 매직 상태 주입이, 디코딩을 확장 가능하게 유지하는 메커니즘 또한 제공한다고 주장합니다.

• 확장성: 이 결과는 대규모 결함 허용 양자 알고리즘을 위한 확장 가능한 시공간 상관 디코딩이 가능하다는 것을 시사합니다. 매직 상태는 빈번한 중간 회로 측정을 도입함으로써 디코딩 문제를 지속적으로 "리셋"하여, 디코딩 영역을 제한함으로써 디코딩 부피를 제한합니다.
• 클래식 오버헤드: 클래식 처리 비용은 양자 계산의 크기(너비 또는 깊이)에 따라 증가하지 않고, 매직 상태의 국소 밀도와 기본 코드 거리에 의해서만 결정되는 유계된 상태를 유지합니다.
• 윈도우 디코딩과의 비교: 디코딩 영역을 제한하기 위해 임의의 시공간 경계를 정의해야 하는 "윈도우 디코딩"과 달리, 이 접근 방식은 수정 사항을 순차적으로 확정함으로써 동적으로 경계를 결정합니다. 이 방법은 경계 조건을 처리하기 위한 추가적인 처방 없이도 구조적으로 결함 허용성을 보존합니다.

저자들은 가로형 결함 허용 아키텍처의 경우, 매직 상태 밀도가 유한하다면 클래식 디코딩 문제가 양자 하드웨어와 함께 확장될 수 있다고 결론짓습니다. 이는 실질적인 대규모 양자 오류 정정의 주요 잠재적 병목 현상을 해결합니다.