KR-102961291-B1 - APPARATUS AND METHOD FOR DECODING OF QUANTUM LOW DENSITY PARITY CHECK CODE

KR102961291B1KR 102961291 B1KR102961291 B1KR 102961291B1KR-102961291-B1

Abstract

본 발명은 양자 저밀도 패리티 검사 부호를 복호화하는 기술에 관한 것이다. 본 발명의 일 측면에 따르면, 양자 저밀도 패리티 검사 부호의 복호화 방법 은, 양자채널의 정보를 초기화하는 단계; 초기화된 양자채널의 정보를 이용하여, 신뢰 전파 알고리즘을 기반으로 제1 오류 정정을 수행하는 단계; 제1 오류 정정이 실패하면, 불만족 검사 노드와 불만족 검사 노드와 연결된 변수 노드의 연결 관계를 기반으로, 변수 노드에 대한 양자채널의 방향성을 결정하는 단계; 결정된 양자채널의 방향성을 기반으로 변수 노드에 대한 양자채널의 정보를 재설정하는 단계; 및 재설정된 양자채널의 정보를 이용하여, 신뢰 전파 알고리즘을 기반으로 제2 오류 정정을 수행하는 단계;를 포함할 수 있다.

Inventors

하정석
김재민
정현우

Assignees

한국과학기술원

Dates

Publication Date: 20260506
Application Date: 20230711

Claims (16)

큐비트에서의 오류 연산자 X, Y 및 Z 각각에 대한 확률값을 포함하도록 양자채널의 정보를 초기화하는 단계; 상기 초기화된 양자채널의 정보를 이용하여, 양자 저밀도 패리티 검사 부호의 복호용으로 선택된 신뢰 전파 알고리즘을 기반으로 제1 오류 정정을 수행하는 단계; 상기 제1 오류 정정이 실패하면, 불만족 검사 노드와 상기 불만족 검사 노드와 연결된 변수 노드의 연결 관계를 기반으로, 상기 변수 노드에 대한 상기 각각의 오류 연산자 별 양자채널의 방향성을 결정하는 단계; 상기 변수 노드에 대해 상기 각각의 오류 연산자 별로 결정된 양자채널의 방향성을 기반으로 상기 변수 노드에 대한 상기 각각의 오류 연산자 별 확률값을 재설정하는 단계; 및 재설정된 상기 각각의 오류 연산자 별 확률값을 이용하여, 상기 신뢰 전파 알고리즘을 기반으로 제2 오류 정정을 수행하는 단계; 를 포함하는, 양자 저밀도 패리티 검사 부호의 복호화 방법.
제1항에 있어서, 상기 변수 노드에 대한 각 오류 연산자 별 양자채널의 방향성은, 상기 변수 노드에 대한 상기 각각의 오류 연산자 별 불만족 검사 노드의 신드롬 정보 및 상기 제1 오류 정정에 이용된 안정기 연산자 정보를 기반으로 결정되는 양자 저밀도 패리티 검사 부호의 복호화 방법.
삭제
삭제
삭제
제1항에 있어서, 상기 변수 노드에 대한 상기 각각의 오류 연산자 별 양자채널의 방향성을 결정하는 단계에서는, 복수의 검사 노드 각각에 대해, 상기 제1 오류 정정의 결과에 해당하는 추정된 오류 및 상기 제1 오류 정정에 이용된 안정기 연산자를 기반으로 신드롬 정보를 산출하고, 산출된 신드롬 정보와 실제 신드롬 정보를 비교하고, 상기 산출된 신드롬 정보와 상기 실제 신드롬 정보가 일치하지 않는 상기 불만족 검사 노드가 확인되면, 상기 제1 오류 정정이 실패한 것으로 판단하는, 양자 저밀도 패리티 검사 부호의 복호화 방법.
제1항에 있어서, 상기 불만족 검사 노드와 복수의 변수 노드가 연결된 경우, 상기 불만족 검사 노드의 개수 및 만족 검사 노드의 개수를 기반으로, 상기 각각의 오류 연산자 별 확률값을 재설정할 상기 변수 노드를 상기 복수의 변수 노드 중에서 결정하는 단계; 를 더 포함하는, 양자 저밀도 패리티 검사 부호의 복호화 방법.
큐비트에서의 오류 연산자 X, Y 및 Z 각각에 대한 확률값을 포함하도록 양자채널의 정보를 초기화하는 단계; 상기 초기화된 양자채널의 정보를 이용하여, 양자 저밀도 패리티 검사 부호의 복호용으로 선택된 신뢰 전파 알고리즘을 기반으로 제1 오류 정정을 수행하는 단계; 상기 제1 오류 정정이 실패하면, 복수의 변수 노드 각각에 연결된 불만족 검사 노드의 개수 및 만족 검사 노드의 개수를 기반으로, 상기 각각의 오류 연산자 별 확률값을 재설정할 때의 상기 복수의 변수 노드 간 우선순위를 결정하는 단계; 결정된 우선순위를 기반으로 상기 복수의 변수 노드 각각에 대해, 상기 각각의 오류 연산자 별 확률값을 재설정하는 단계; 및 재설정된 상기 각각의 오류 연산자 별 확률값을 이용하여, 상기 신뢰 전파 알고리즘을 기반으로 제2 오류 정정을 수행하는 단계; 를 포함하는, 양자 저밀도 패리티 검사 부호의 복호화 방법.
명령어를 포함하는 메모리; 및 상기 명령어를 실행함으로써, 큐비트에서의 오류 연산자 X, Y 및 Z 각각에 대한 확률값을 포함하도록 양자채널의 정보를 초기화하고, 상기 초기화된 양자채널의 정보를 이용하여, 양자 저밀도 패리티 검사 부호의 복호용으로 선택된 신뢰 전파 알고리즘을 기반으로 제1 오류 정정을 수행하며, 상기 제1 오류 정정이 실패하면, 불만족 검사 노드와 상기 불만족 검사 노드와 연결된 변수 노드의 연결 관계를 기반으로, 상기 변수 노드에 대한 상기 각각의 오류 연산자 별 양자채널의 방향성을 결정하고, 상기 변수 노드에 대해 상기 각각의 오류 연산자 별로 결정된 양자채널의 방향성을 기반으로 상기 변수 노드에 대한 상기 각각의 오류 연산자 별 확률값을 재설정하며, 재설정된 상기 각각의 오류 연산자 별 확률값을 이용하여, 상기 신뢰 전파 알고리즘을 기반으로 제2 오류 정정을 수행하는 프로세서; 를 포함하는, 양자 저밀도 패리티 검사 부호의 복호화 장치.
제9항에 있어서, 상기 프로세서는, 상기 변수 노드에 대한 상기 불만족 검사 노드의 신드롬 정보 및 상기 제1 오류 정정에 이용된 안정기 연산자 정보를 기반으로, 상기 변수 노드에 대응하는 양자채널의 방향성을 결정하는, 양자 저밀도 패리티 검사 부호의 복호화 장치.
삭제
삭제
삭제
제9항에 있어서, 상기 프로세서는, 복수의 검사 노드 각각에 대해, 상기 제1 오류 정정의 결과에 해당되는 추정된 오류 및 상기 제1 오류 정정에 이용된 안정기 연산자를 기반으로 신드롬 정보를 산출하고, 산출된 신드롬 정보와 실제 신드롬 정보를 비교하고, 상기 산출된 신드롬 정보와 상기 실제 신드롬 정보가 일치하지 않는 상기 불만족 검사 노드가 확인되면, 상기 제1 오류 정정이 실패한 것으로 판단하는, 양자 저밀도 패리티 검사 부호의 복호화 장치.
제9항에 있어서, 상기 프로세서는, 상기 불만족 검사 노드와 복수의 변수 노드가 연결된 경우, 상기 불만족 검사 노드의 개수 및 만족 검사 노드의 개수를 기반으로, 상기 각각의 오류 연산자 별 확률값을 재설정할 변수 노드를 상기 복수의 변수 노드 중에서 결정하는 양자 저밀도 패리티 검사 부호의 복호화 장치.
명령어를 포함하는 메모리; 및 상기 명령어를 실행함으로써, 큐비트에서의 오류 연산자 X, Y 및 Z 각각에 대한 확률값을 포함하도록 양자채널의 정보를 초기화하고, 상기 초기화된 양자채널의 정보를 이용하여, 양자 저밀도 패리티 검사 부호의 복호용으로 선택된 신뢰 전파 알고리즘을 기반으로 제1 오류 정정을 수행하며, 상기 제1 오류 정정이 실패하면, 복수의 변수 노드 각각에 연결된 불만족 검사 노드의 개수 및 만족 검사 노드의 개수를 기반으로 상기 각각의 오류 연산자 별 확률값을 재설정할 때의 상기 복수의 변수 노드 간 우선순위를 결정하고, 결정된 우선순위를 기반으로 상기 복수의 변수 노드 각각에 대해, 상기 각각의 오류 연산자 별 확률값을 재설정하고, 재설정된 상기 각각의 오류 연산자 별 확률값을 이용하여, 상기 신뢰 전파 알고리즘을 기반으로 제2 오류 정정을 수행하는 프로세서; 를 포함하는, 양자 저밀도 패리티 검사 부호의 복호화 장치

Description

양자 저밀도 패리티 검사 부호 복호화 장치 및 방법{APPARATUS AND METHOD FOR DECODING OF QUANTUM LOW DENSITY PARITY CHECK CODE} 본 발명은 양자 저밀도 패리티 검사 부호를 복호화하는 기술에 관한 것이다. 양자 저밀도 패리티 검사 부호의 복호 알고리즘은 큐비트에 발생한 오류를 추정하고, 복구 연산자를 통해 오류를 정정하는 과정이다. 양자 저밀도 패리티 검사 부호의 복호화 알고리즘으로는 대표적으로 신뢰 전파 알고리즘이 있다. 하지만, 신뢰 전파 알고리즘은 축퇴의 특성을 반영하지 않아 양자 저밀도 패리티 검사 부호의 복호화 과정에서 문제점이 발생한다. 이러한, 문제를 해결하기 위해, 신뢰 전파 알고리즘에서도 축퇴 특성을 반영할 수 있도록 후처리 알고리즘(post-processing algorithm)을 적용하는 Enhanced Feed Back 알고리즘과 같은 알고리즘이 연구되고 있다. 하지만, Enhanced Feed Back 알고리즘에서도 오류 추정에 실패한 경우에, 재복호화를 진행하는 과정에서 과도한 재복호화 횟수로 인한 복호화 효율을 낮춘다는 문제가 여전히 존재한다. 도 1은 종래 양자 저밀도 패리티 검사 부호의 복호화를 설명하기 위한 도면이다. 도 2는 본 발명의 일 실시예에 따른 양자 저밀도 패리티 검사 부호 복호화 장치의 블록도이다. 도 3은 본 발명의 일 실시예에 따른 양자 저밀도 패리티 검사 부호 복호화 방법의 흐름도이다. 도 4는 도 3의 양자 저밀도 패리티 검사 부호 복호화 방법을 설명하기 위한 도면이다. 도 5는 종래 양자 저밀도 패리티 검사 부호의 재복호화를 설명하기 위한 도면이다. 도 6은 본 발명의 다른 실시예에 따른 양자 저밀도 패리티 검사 부호 복호화 방법의 흐름도이다. 도 7은 도 6의 양자 저밀도 패리티 검사 부호 복호화 방법을 설명하기 위한 도면이다. 도 8 및 도 9는 본 발명의 일 실시예에 따른 양자 저밀도 패리티 검사 부호 복호화 장치의 성능을 설명하기 위한 도면이다. 도 10은 본 발명의 또 다른 실시예에 따른 양자 저밀도 패리티 검사 부호 복호화 방법의 흐름도이다. 도 11은 본 발명의 다른 실시예에 따른 양자 저밀도 패리티 검사 부호 복호화 장치의 블록도이다. 본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시예들에 한정되는 것이 아니라 다양한 형태로 구현될 수 있으며, 단지 본 실시예들은 본 발명의 개시가 완전하도록 하고, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명의 범주는 청구항에 의해 정의될 뿐이다. 본 발명의 실시예들을 설명함에 있어서 공지 기능 또는 구성에 대한 구체적인 설명은 본 발명의 실시예들을 설명함에 있어 실제로 필요한 경우 외에는 생략될 것이다. 그리고 후술되는 용어들은 본 발명의 실시예에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다. 이하 사용되는 '…부', '…기' 등의 용어는 적어도 하나의 기능이나 동작을 처리하는 단위를 의미하며, 이는 하드웨어나 소프트웨어, 또는, 하드웨어 및 소프트웨어의 결합으로 구현될 수 있다. 안정기 부호(Stabilizer code)는 현재 가장 많은 연구가 진행되고 있는 대표적인 양자 오류 정정 부호이다. 안정기 부호는 그룸 이론(Group theory)을 기반으로 형성되었으며, 고전 선형 오류 정정 부호와 유사하며, 많은 양자 오류 정정 부호가 안정기 부호의 범주에 속한다. 안정기 부호는 파울리 그룹(Pauli group)의 아벨리안 부분군(Abelian subgroup)인 안정기 그룹 S으로 정의되며 부호 공간(Code space) C는 아래 수학식 1 같이 표현될 수 있다. 안정기 연산자들은 큐비트에 발생하는 오류를 판단하는 신드롬(Syndrome) 정보를 추출하는 데 사용된다. 이때 안정기 연산자들의 무게(Weight)가 대체로 작아 희소 패리티 검사 행렬(Sparse parity check matrix)을 가지는 부호를 양자 저밀도 패리티 검사 부호(Quantum low-density parity-check codes)라고 한다. 양자 저밀도 패리티 검사 부호는 오류 정정을 위한 복호화 과정에서 외부 영향을 받는 큐비트 수가 상대적으로 적어 결함 허용 복호(Fault-tolerant decoding)에 유리하다. 또한, 고전 영역과 구별되는 양자 특성 중 하나인 축퇴(Degeneracy)를 이용할 수 있으며, 이러한 특성은 양자 오류 정정 부호의 성능을 향상시킬 수 있다. 양자 저밀도 패리티 검사 부호의 복호 알고리즘은 큐비트에 발생한 오류 E를 추정(Estimate)하고 복구 연산자(Recovery operator)를 통해 정정 (Correct)하는 과정이다. 우선 큐비트 상태에 발생한 오류를 추정하기 위해서는 측정 (Measurement)이 이루어져야 한다. 하지만 정보가 담긴 큐비트에 직접적인 측정을 하면 큐비트 상태의 중첩(Superposition) 상태가 파괴되어 정보가 손실되는 문제가 발생한다. 따라서 큐비트가 가지고 있는 정보가 손실되지 않으면서 오류를 찾아내기 위해서는 추가적인 보조 큐비트(Ancilla qubit)를 사용하여 양자 회로를 구성하고 측정을 해야한다. 이때 사용하는 양자 회로를 신드롬 추출 회로 (Syndrome Extraction Circuit)라고 하며 신드롬 추출 회로를 이용하여 얻은 측정값을 신드롬(Syndrome) 정보(이하, 실제 신드롬 정보)이라 한다. 이후 복호 알고리즘은 신드롬 정보를 바탕으로 발생한 오류를 추정하여 오류 정정 과정에서 사용할 복구 연산자를 결정한다. 고전 오류 정정 부호와 달리 양자 오류 정정 부호는 양자 특성 중 하나인 축퇴(Degeneracy)라는 성질을 이용할 수 있다. 서로 다른 오류에 대해 동일한 복호 연산자를 통해 정보를 복원할 수 있는 특징을 축퇴라고 한다. 축퇴 관계에 있는 서로 다른 오류 연산자 ,는 아래와 같이 수학식 2를 만족한다. 축퇴 관계에 있는 서로 다른 오류 연산자는 양자 오류 정정 부호의 코드워드 (Codeword)에 주는 영향이 같다. 이는 복호화 과정을 통해 추정해야할 오류가 유일하지 않다는 것을 의미한다. 추정해야하는 오류가 유일한 고전 오류 정정 부호와 달리 양자 오류 정정 부호는 실제 오류와 코드워드에 주는 영향이 같은 오류 연산자 중 하나를 추정하더라도 복호에 성공하게 된다 양자 저밀도 패리티 검사 부호의 복호 알고리즘으로는 대표적으로 신뢰 전파 (Belief propagation) 알고리즘이 있다. 양자 저밀도 패리티 검사 부호의 복호화 과정은 큐비트에 적용된 오류의 유무를 판단해주는 신드롬 정보를 이용하여 신뢰 전파 알고리즘을 통해 오류를 추정하는 과정이다. 신뢰 전파 알고리즘에서 양자 오류의 채널로서 디폴라이징 채널(Depolarizing channel)을 사용하여 채널값을 초기화(Initialization)한다. 디폴라이징 채널은 양자 채널로서 많이 사용되며, 양자 오류 X,Z,Y 모두 p/3의 확률값을 가진다. 이때 p는 큐비트에 발생하는 오류율이다. 신뢰 전파 알고리즘은 축퇴의 특성을 반영하지 않아 양자 저밀도 패리티 검사 부호의 복호화 과정에서 발생하는 문제점으로 여겨진다. 따라서 축퇴 특성을 활용하기 위해 기존의 신뢰 전파 알고리즘에 후처리 알고리즘(Post-processing algorithm)을 적용하여 성능을 개선한 알고리즘이 제안되어왔으며, Enhanced feedback 알고리즘이 신뢰 전파 방식의 대표적인 후처리 알고리즘이다. 단순히 신드롬 정보를 활용하여 복호를 진행하는 신뢰 전파 알고리즘과는 달리 Enhanced feedback 알고리즘은 신드롬 정보뿐만 아니라 안정기 연산자 정보를 활용한다. 신뢰 전파 복호 알고리즘을 이용한 복호에 실패한 후, 불만족 검사 노드 (Unsatisfied check node)과 연결된 임의의 변수 노드(Variable node)의 오류가 잘못 추정되었다고 판단하여 해당 불만족 검사 노드에 대응하는 안정기 연산자 정보를 반영한 새로운 채널 모델을 생성하여 후처리 알고리즘에서 재복호화 과정을 진행한다. 이때 불만족 검사 노드는 추정된 오류와 안정기 연산자로 계산된 신드롬 정보와 실제 신드롬 정보가 일치하지 않는 경우에 발생된다. 도 1을 참조하면, 검은 색 정사각형은 불만족 검사 노드 c이며, 이와 연결된 변수 노드들 중 임의로 선택된 변수 노드는 t이다. 검사 노드 c 의 신드롬 정보가 1이고 계산된 신드롬 정보가 0인 경우, 변수 노드 t 의 채널 모델은 아래 수학식 3과 같이 표현될 수 있다. 여기서, p와 는 각각 디폴라이징 채널(Depolarizing channel)에서의 오류율과 i 번째 검사 노드에 해당하는 안정기 연산자에서 t 번째 위치의 연산자를 의미한다. 실제 신드롬 정보가 0이기 때문에 변수 노드 t는 연산자와 교환 가능해야 한다고 판단한다. 따라서 연산자와 교환 가능한 I 와 의 확률값을 높여준다. 마찬가지 방식으로 검사 노드 c 의 신드롬 정보가 0이고 계산된 신드롬 정보가 1인 경우, 변수 노드 t 의 채널 모델은 아래 수학식 4와 같이 표현될 수 있다. Enhanced Feedback 알고리즘은 불만족 검사 노드와 연결된 변수 노드 중 임의로 하나 선택하여 채널 정보를 변경하고 재복호화 과정을 수행한다. 재복호화 과정에서도 복호에 실패하게 된다면 불만족 검사 노드와 연결된 변수 노드 중에서 임의로 재선택하여 다시 재복호화 과정을 진행한다. 재복호화 과정 시도 횟수는 사전에 미리 정해두고 재복호를 진행한다. 본 발명은 이러한 재복호화 과정에서 시도 횟수를 줄이기 위해, 불만족 검사 노드와 변수 노드의 관계를 기반으로 양자채널의 정보를 재설정하는 기술 및 양자채널의 정보를 재설정할 변수 노드를 우선순위를 기반으로 결정하는 기술을 제시한다. 이에 대한 구체적인 설명은 도 2 내지 도 11을 참