Decoding Algorithm to Composite Errors Consisting of Deletions and Insertions for Quantum Deletion-Correcting Codes Based on Quantum Reed-Solomon Codes

기술 요약: Hagiwara 부호를 위한 합성 오류 해독 알고리즘

문제 제기
양자 정보 시스템은 동기화 오류, 특히 양자 삭제 오류 (큐비트 손실) 와 양자 삽입 오류 (새로운 큐비트 추가) 에 취약합니다. 양자 Reed-Solomon (RS) 부호와 그 파생체인 Hagiwara 부호는 삭제와 삽입으로 구성된 합성 오류를 정정할 수 있음이 입증되었으나, 이러한 합성 오류에 대한 효율적인 해독 알고리즘은 여전히 미해결 과제로 남아 있었습니다. Hagiwara 부호에 대한 기존 해독 방법은 주로 삭제 또는 삽입 중 하나만을 정정하거나, 각각의 단일 사례를 정정하는 데 국한되었으며, 오류의 총수가 제한된 일반적인 합성 시나리오에서는 적용되지 않았습니다.

방법론
저자들은 $t_d$개의 삭제와 $t_i$개의 삽입으로 구성된 합성 오류를 처리하는 Hagiwara 부호용 해독 알고리즘을 제안합니다. 여기서 $t_d + t_i \le t$이며 $t_d, t_i \neq 0$입니다. 방법론은 두 단계로 진행됩니다:

1. 고전적 대응물 개발: 저자들은 먼저 단일 삽입/단일 삭제 오류에 대한 기존 알고리즘을 고전적 환경으로 일반화합니다. Hagiwara 부호는 고전적 Reed-Solomon (RS) 부호의 블록 사이에 "마커" 시퀀스 (구체적으로 $0^{(t)}1^{(t)}$) 를 삽입하여 구성됩니다. 이 알고리즘 (알고리즘 1) 은 수신된 시퀀스를 마커 주변 영역을 분석하여 검토합니다. 마커 형식이 보존되었는지 파괴되었는지 감지하고, 예상되는 마커 경계 대비 삭제와 삽입의 수를 세어냅니다.

   • 마커 형식이 보존되었으나 이동한 경우, 알고리즘은 이동을 식별하여 데이터 블록 내에서 삭제 또는 삽입이 발생했는지 판단합니다.
   • 마커 형식이 파괴된 경우 (예: '1' 영역에 '0'이 삽입됨), 알고리즘은 해당 블록에 삽입 오류가 있음을 플래그로 표시합니다.
   • 이 단계의 출력은 일부가 오류가 감지된 블록 (지움) 으로 식별되고 나머지는 감지되지 않았으나 정정된 오류가 있는 블록 (대체) 으로 식별된 고전적 블록 시퀀스와, 지움의 위치를 포함합니다.

2. 양자 영역으로의 확장: 고전적 알고리즘을 양자 영역으로 확장합니다. 저자들은 "블록 변환 오류"를 양자 블록 $R_b$를 밀도 행렬 공간의 상태로 변환하는 오류로 정의합니다. 그들은 삭제와 삽입의 합성 오류 ($I_Q \circ D_P$) 가 영향을 받은 큐비트에 작용하는 파울리 오류들의 복잡한 선형 결합과 큐비트 위치의 치환으로 분해될 수 있음을 증명합니다.

   • 마커 큐비트를 측정함으로써 (RS 부호 블록의 데이터 큐비트를 파괴하지 않음), 수신자는 결과의 고전적 시퀀스를 얻습니다.
   • 고전적 알고리즘 1 을 이러한 측정 결과에 적용하여 어떤 블록이 정보 손실 (지움) 을 겪었는지, 어떤 블록이 단위 변환 (대체) 을 겪었는지 식별합니다.
   • 그 후 양자 해독은 RS 부호 $C_1$과 $C_2$로 구축된 기반 CSS 부호 구조에서의 지움과 단위 오류를 정정하는 문제로 축소되며, 이에 대한 효율적인 알고리즘은 이미 존재합니다.

주요 기여

• 알고리즘 제안: 본 논문은 $t_d + t_i \le t$인 일반적인 합성 오류 ($t_d$개의 삭제와 $t_i$개의 삽입) 를 정정할 수 있는 Hagiwara 부호에 대한 최초의 효율적인 해독 알고리즘을 제시합니다.
• 이론적 정당화: 저자들은 제안된 알고리즘이 수신된 시퀀스를 최대 $e$개의 블록 지움과 $m$개의 블록 대체를 포함하는 형태로 변환하며, 조건 $e + 2m \le t$를 만족함을 엄밀하게 증명합니다 (정리 2). 이는 오류가 기반 Reed-Solomon 부호의 정정 능력 범위 내에 있음을 보장합니다.
• 오류 분해: 본 논문은 Hagiwara 부호 블록에 대한 임의의 합성 삭제/삽입 오류가 영향을 받은 큐비트들의 파울리 오류들의 선형 결합으로 표현될 수 있음을 확립합니다 (정리 1 및 corollary 1). 이는 동기화 오류와 표준 양자 오류 정정 프레임워크 간의 간극을 연결합니다.

결과
본 논문은 $t=4$인 고전적 Hagiwara 부호와 관련된 구체적인 예를 통해 알고리즘의 동작을 시연합니다. 이 예시는 알고리즘이 여러 블록에 걸쳐 발생한 삽입과 삭제의 혼합을 정확하게 식별하여, 기반 RS 해독기가 해결할 수 있는 지움과 대체의 패턴으로 변환하는 방식을 보여줍니다. 이론적 결과는 해당 알고리즘이 복잡한 동기화 오류를 양자 RS 부호에 대해 정정 가능한 형태로 성공적으로 매핑함을 확인시켜 줍니다.

의의
본 논문은 Hagiwara 부호와 관련된 문헌의 중요한 공백을 해소했다고 주장합니다. 이러한 부호의 구성이 이론적으로 합성 오류를 정정할 수 있음은 알려져 있었으나, 실용적인 해독 방법의 부재로 인해 그 활용도가 제한되었습니다. 구체적인 해독 알고리즘을 제공하고 그 정확성을 증명함으로써, 이 연구는 동기화 오류에 노출된 양자 통신 시스템을 위한 Hagiwara 부호의 실용적 적용을 가능하게 합니다. 이 연구는 Hagiwara 부호의 기초적 정의에 기반을 두고, 단일 오류에 대한 기존 해독 노력을 보다 복잡한 합성 오류 시나리오로 확장합니다.