기술 요약: 가우스 소거법을 위한 양자 회로

문제 정의

가우스 소거법은 선형 방정식 시스템을 풀고, 행렬의 계수(rank), 행렬식(determinant), 역행렬을 계산하는 데 사용되는 근본적인 알고리즘이다. 추상적인 양자 알고리즘은 유니터리 연산에 의해 정의되지만, 실제 구현에서는 비트 문자열 매핑에 대한 가역적인 고전적 구성이 필요한 경우가 많다. 중요한 과제는 가우스 소절법 자체가 본질적으로 비단사적(non-injective)이라는 점이다. 즉, 많은 입력 행렬이 동일한 행 사다리꼴(row-echelon form)로 매핑될 수 있으므로, 가역성을 유지하기 위해 최소 $x-y$개의 큐비트($x$와 $y$는 각각 입력 및 출력 비트 길이)에 해당하는 작업 공간(가비지)이 필요하다.

기존의 가우스 소거법 양자 구현은 이진 필드 $GF(2)$로 제한되어 있었다. 이러한 기존 연구들은 두 가지 주요 한계점에 직면해 있었다:

1. 가비지 축적: 최소 이론적 작업 공간 요구 사항을 충족하지 못하거나, 다시 계산(uncompute)할 수 없는 상당한 양의 "가비지"(보충 공간)를 생성했다.
2. 복잡도 불일치: 특히 토폴리(Toffoli) 깊이와 큐비트 수 측면에서 고전적 구현의 점근적 복잡도를 달着하지 못하는 경우가 많았다.

또한, 임의의 유한체 $GF(p^l)$ 상에서 작동하는 일반화된 양자 가우스 소거법 회로는 존재하지 않았으며, 이는 더 넓은 암호학적 및 대수적 맥락에서의 양자 선형 대수의 적용성을 제한했다.

방법론

저자들은 임의의 유한체 $GF(p^l)$ 상에서 작동하는 가역적인 양자 가우스 소거법 회로를 제안한다. 이 방법론은 세 가지 핵심 혁신을 중심으로 한다:

1. 의사 행 사다리꼴 (Pseudo Row Echelon Form)

표준 가우스 소거법의 비단사성을 해결하기 위해, 저자들은 의사 행 사다리꼴을 도입한다.

• 정의: 행렬 $A'$가 의사 행 사다리꼴이라는 것은 $A'$의 상삼각 요소들이 $A$의 표준 행 사다리꼴의 상삼각 요소들과 일치함을 의미한다. 하삼각 및 대각 부분은 형태에 의해 엄격하게 정의되지 않으며 정보를 저장하는 데 활용된다.
• 메커니즘: 이 변환은 본질적으로 비단사적인 매핑을 일대일(전단사) 변환으로 전환한다. 연산을 역전시키기 위해 필요한 정보가 하삼각 및 대각 성분 내에 보존되므로, 최소한의 임시 큐비트를 사용하여 결과를 입력 큐비트에 덮어쓸 수 있다.

2. 알고리즘 구조

제안된 알고리즘(Algorithm 1)은 행렬을 변환하기 위해 열 단위로 반복 수행된다. 이 알고리즘은 네 가지 가역적 서브루틴에 의존한다:

• 레이블링 (Labeling): 피벗 인덱스(현재 열에서 첫 번째로 0이 아닌 항목이 있는 행)를 식별하고 이를 단항(unary) 형식으로 인코딩한다. 저자들은 깊이를 줄이기 위해 재귀적인 토너먼트 구조를 활용하여 이 과정을 병렬화한다.
• 피보팅 (Pivoting): 첫 번째 행을 피벗 행과 교환한다. 이는 "빌려온 큐비트"(알 수 없는 상태에 있는 안실라 큐비트이며 연산 종료 시 초기 상태로 복구됨)를 사용하여 병렬화할 수 있는 토너먼트 스타일의 스와핑 메커니즘을 통해 구현된다.
• 행 감소 (Row Reduction): 피벗 행의 요소들을 피벗 요소로 나누고, 피벗 행을 다른 행들로부터 뺀다. 이는 필드 산술(곱셈, 역원, 덧셈)을 포함하며, 깊이를 최소화하기 위해 빌려온 큐비트를 사용하여 병렬화된다.
• 피벗 인덱스 삭제 (Deleting the Pivot Index): 레이블링 및 부분 피보팅 단계를 역으로 수행하여 작업 큐비트를 0으로 복구함으로써, 보충 공간에 대한 가비지가 없도록 보장한다.

3. 빌려온 큐비트를 이용한 병렬화

핵심적인 기술적 기여는 **빌려온 큐비트(borrowed qubits)**를 사용하여 연산을 병렬화하는 것이다.

• 깨끗한 안실라 큐비트를 요구하는 대신, 이 회로는 알 수 없는 값을 가질 수 있는 큐비트를 활용한다.
• 저자들은 공유 제어 값이나 피연산자를 이러한 빌려온 큐비트로 전달하고, 병렬 연산을 수행한 다음, 빌려온 큐비트를 원래 상태로 복구하기 위한 교정 단계를 적용하는 Gidney의 접근 방식을 응용한다.
• 이 기술은 제어 스와프(피보팅에서의 제어 스와프) 및 산술 연산(행 감소에서의 산술 연산)에 적용되어 회로 깊이를 크게 줄인다.

주요 기여 및 결과

1. 임의의 유한체로의 일반화

$GF(2)$에 국한되었던 기존 연구들과 달리, 이 설계는 임의의 유한체 $GF(p^l)$에 대해 일반화되었다. 이를 통해 저자들은 다양한 암호학적 프리미티브 및 부호 이론 문제와 관련된 더 복잡한 대수적 구조를 처리할 수 있게 되었다.

2. 가비지 없는 구성 (Garbage-Free Construction)

개발된 회로는 보충 공간에 대해 가비지 없는 구성을 달성한다.

• 가우스 소거법의 결과는 입력 큐비트에 직접 덮어씌워진다.
• 회로는 중간 계산을 위해 $m-1$개의 임시 작업 큐비트를 필요로 하며, 이들은 연산 종료 시 모두 0으로 복구된다.
• 결정적으로, 이 회로는 임시 큐비트와 입력 큐비트 외에 추가적인 (가비지) 공간을 점유하지 않는다. 이는 보충 공간이 $O(n^2)$ 또는 $O(mn)$에 비례하며 0으로 돌아오지 않았던 이전 연구들(예: [20])과 대조된다. 논문은 보충 공간을 초기에는 0이지만 끝날 때 0으로 돌아오지 않는 작업 큐비트로 정의하며, 본 설계는 이 수치가 0임을 보장한다.

3. 복잡도 개선

논문은 $GF(2)$에서의 $m \times n$ 크기 행렬에 대한 회로 복잡도의 정량적 비교를 표 1에 요약하여 제공한다:

지표	이전 연구 ([9], [20], [5])	본 연구
Toffoli Count	$O(n^2m)$ ~ $O(n^2m^2)$	$O(n^2m)$
Toffoli Depth	$O(nm)$~$O(n^2m \log^3 m)$| **$O(m \log^2 n + n \log^4 m)$**
임시 공간 (Temporary Space)	$0$~$m-2$| **$m-1$**
보충 (가비지) 공간 (Supplemental Space)	$0$~$O(n^2)$| **$0$**

• $GF(2)$의 경우: 이 회로는 로그 인수를 제외하고 최선의 알려진 점근적 Toffoli 깊이를 달성하는 동시에, 고전적 산술 복잡도인 $O(n^2m)$과 일치한다.
• 일반 필드의 경우: 복잡도는 필드 크기 파라미터 $\alpha = l \lceil \log_2 p \rceil$에 따라 확장되며, 동일한 구조적 효율성을 유지한다.

의의 및 주장

저자들은 본 연구가 선형 대수의 양자 구현에 있어 중요한 최적화를 이루었다고 주장한다:

1. 트레이드오프의 최적화: 본 설계는 시간(깊이)과 공간(큐비트) 사이의 트레이드오프를 성공적으로 최적화한다. 큐비트 수가 병목 현상이 되는 근접 미래의 양자 하드웨어에서 중요한 요소인 추가 공간 사용을 엄격히 제한하면서도 고전적 산술 복잡도와 일치한다.
2. 가비지 없는 가역성: 의사 행 사다리꼴을 도입함으로써, 본 논문은 가우스 소거법을 보충 가비지 큐비트를 축적하지 않고 가역적으로 수행할 수 있음을 입증하였다. 이는 $m-1$개의 임시 큐비트만을 사용하면서도 기존 $GF(2)$ 구현들이 달성하지 못한 성과이다.
3. 광범위한 적용 가능성: 임의의 유한체로의 일반화는 비이진 필드 상의 선형 시스템을 다루는 특정 포스트 퀀텀 암호 해독 작업 및 부호 이론 응용 분야와 같은 문제에 대한 양자 알고리즘의 범위를 확장한다.

결론적으로, 본 논문은 곱셈 깊이를 줄이는 등의 추가적인 최적화가 가능할 수 있으나, 현재의 설계가 낮은 큐비트 오버헤드와 경쟁력 있는 시간 복잡도의 균형을 맞춘 가역적 가우스 소거법의 새로운 벤치마크를 설정했다고 밝히고 있다.