기술 요약: 제어된 PROPs: 양자 회로에 대한 이론 및 응용

1. 문제 정의

제어(Control)는 양자 및 가역 계산 모델에서 핵심적인 개념으로, 제어 시스템의 상태에 따라 변환을 조건부로 적용할 수 있게 한다. 도식적 추론(diagrammatic reasoning)은 대칭 단성 카테고리(symmetric monoidal categories, 구체적으로 PROPs)를 통해 양자 회로를 정형화하는 데 성공해 왔으나, 표준 PROP 프레임워크는 제어 연산을 기본 생성자(primitive constructor)가 아닌 파생된 구성물(shorthand notations)로 취급한다.

기존의 유니터리 양자 회로(PROPs로 정의됨)에 대한 완전한 공리화의 중대한 한계는 $n$개의 큐비트에 관한 공리가 모든 $n \in \mathbb{N}$에 대해 필요하다는 점이다[11]. 이러한 무한성(unboundedness)은 도식적 추론과 자동 검증을 복잡하게 만든다. 본 논문은 제어를 기본 생성자로 취급하여 공리화를 단순화하고 잠재적으로 무한성 문제를 우회하는 것을 목표로 하는, 제어를 기본 생성자로 다루는 새로운 형식을 제안한다.

2. 방법론

저자들은 제어 함수(control functor)를 갖춘 **제어된 PROPs (CPROPs)**를 도입하여 표준 PROP 형식을 확장한다.

• 제로 함수 (Control Functor): 임의의 객체 $n$을 $n+1$로 매핑하고, 임의의 내생 사상(endomorphism) $f: n \to n$을 제어된 버전인 $\text{ctrl}(f): n+1 \to n+1$로 매핑하는 함수 $\text{ctrl}: P_{\text{endo}} \to P_{\text{endo}}$이다. 이 함수는 특정 일관성 법칙(예: 순차적 합성 보존, 항등원과의 병렬 합성 분배, 스왑(swap)과의 교환)을 만족한다.
• 공액 제어 PROPs (CCPROPs): 공액 법칙(conjugation law) $\text{ctrl}(g \# f \# g^{-1}) = (\text{id}_1 \otimes g) \# \text{ctrl}(f) \# (\text{id}_1 \otimes g^{-1})$이 성립하는 확장된 형태이다. 이는 알고리즘 설계에서 널리 사용되는 "계산/역계산(compute/uncompute)" 패턴을 포착한다.
• 유니터리 CPROPs: 모든 모피즘이 가역적인 유니터리 CPROPs로 특수화되며, 이를 통해 공액 법칙을 일반 역원 대신 수반(adjoint, $g^\dagger$)을 사용하여 적용할 수 있다.
• 축약 및 완결성 증명: 저자들은 축약 전략을 사용하여, 만약 유니터리 CPROP이 "M-축약 가능(M-reducible)"하다면(즉, 모든 모피즘이 부분 집합 $M$으로 분해될 수 있다면), $M$ 내의 특정 중첩 구성에 대해 공액 법칙을 증명하는 것만으로 일반적인 증명이 충분함을 보여준다. 저자들은 표준 양자 회로(QC)와 제어 가능한 양자 회로(CQC) 사이의 인코딩 및 디코딩 절차를 활용하여 완결성 결과를 전이시킨다.

3. 주요 기여

3.1. 이론적 프레임워크

• CPROPs 및 CCPROPs의 정의: 본 논문은 제어 함수의 기초적인 공리화를 제공하며 CPROPs와 CCPROPs를 공식적으로 정의한다. 제어가 병렬 합성을 보존하지 않지만($\text{ctrl}(f \otimes g) \neq \text{ctrl}(f) \otimes \text{ctrl}(g)$), 자연스럽게 분배됨을 입증한다.
• 제어 지점 (Points of Control): 비퇴화(non-degenerate) 제어 함수를 구분하기 위해 "지점"(논리적 참/거짓을 나타내는 모피즘 $0 \to 1$) 개념을 도입한다.
• 다중 제어 PROPs 및 SMC로의 일반화: 여러 제어 함수가 공존하는 다중 제어(poly-CPROPs)를 다루기 위해 호환성, 가환성, 포괄성 등의 속성을 갖춘 체계로 확장한다. 또한 제어가 객체에 의해 매개변수화되는 임의의 대칭 단성 카테고리(SMC)로 일반화한다.

3.2. 양자 회로에의 적용

• 제어 가능한 양자 회로 (CQC): 저자들은 전역 위상(global phases)과 아다마르 게이트(Hadamard gate)만을 생성자로 사용하는 자유 생성 CPROP으로서 CQC를 정의한다.
• 유한 큐비트를 이용한 완전한 공리화:
  • 본 논문은 CQC를 위한 완전한 공리화($A_c$)를 제시하며, 이는 네 개의 단순 공리(오일러 분해 및 공액 법칙 사례 포함)만을 포함한다.
  • 결정적으로, $A_c$의 모든 공리는 최대 3개의 큐비트만을 포함한다.
  • CCPROP으로 볼 때(공액 법칙을 공리가 아닌 규칙으로 포함할 경우), 이 시스템은 최대 2개의 큐비트를 포함하는 5개의 공리만을 필요로 한다.
• 보조 큐비트 (Ancillas): 프레임워크는 사후 선택(post-selection)이 있는 CPROP($ACQC$)을 통해 보조 큐비트를 포함하도록 확장되어, 등거리 사상(isometries)에 대한 완전한 공리화를 제공한다.

4. 결과

• CQC의 완결성: 저자들은 제어 가능한 양자 회로의 그래픽 언어가 완전함을 증명한다. 즉, 제어 가능한 양자 회로 사이의 모든 유효한 의미론적 동치 관계는 제안된 공리들을 사용하여 도식적으로 유도될 수 있다.
• 유한성 달려 (Boundedness Achievement): 제어를 생성자로 취급함으로써, 표준 PROP 설정에서 요구되었던 임의의 $n$에 대한 공위(unbounded) 공리의 필요성을 우회할 수 있음을 보여준다. CQC를 위한 유도된 공리계는 공리당 큐비트 수 측면에서 유한하다.
• 보편성: CQC 프레임워크는 $Uni_2$의 모든 유니터리 변환을 표현할 수 있는 유니터리 맵에 대한 보편성을 가짐이 입증되었다.
• 추론의 단순화: 공액 법칙은 복잡한 제어 패턴(예: $\text{ctrl}(g \# f \# g^{-1})$)을 더 단순한 형태로 축약하여 회로 최적화 및 컴파일을 용이하게 한다.

5. 의의 및 주장

본 논문은 Controlled PROPs가 표준 PROPs에 비해 양자 컴퓨팅의 도식적 추론을 위한 더 다재다능하고 단순한 언어를 제공한다고 주장한다.

• 무한성 우회: 가장 중요한 의의는 제어를 생성자로 다룸으로써, 양자 회로의 완전한 공리화를 위해 (구체적으로 최대 3개 또는 2개의 큐비트와 같이) 유한한 수의 큐비트를 사용하는 공리를 달성했다는 점이다. 이는 표준 PROP 공리화가 본질적으로 임의의 큰 $n$에 대한 공리를 필요로 하는 것과 대조된다.
• 기본 생성으로서의 제어: 제어를 생성자로 격상시킴으로써, 제어 버전의 방정식을 유도하는 과정($f=g$이면 $\text{ctrl}(f)=\text{ctrl}(g)$임이 즉각적임)이 단순해진다. 반면 표준 PROP에서 이를 유도하는 것은 번거롭다.
• 다재다능함: 이 형식은 양자 회로에 국한되지 않고, 고전적 가역 회로 및 큐디트(qudit) 시스템에도 적용 가능하다. 저자들은 표준 양자 회로 형식에서 미지의 유니터리를 제어하는 것에 대한 '불가능 정리(no-go theorem)'가 존재하지만, 본 프레임워크는 "화이트박스(white-box)" 환경(회로 구현이 알려진 경우)에서 작동하므로 미지의 연산을 제어하는 것이 그래픽 언어의 유효한 기능이 된다고 언급한다.

저자들은 이 접근 방식이 양자 컴퓨팅에 특화되지 않은 공리화 부분을 추상화함으로써 양자 회로의 본질을 고립시키며, 이는 양자 회로 최적화 및 형식 검증을 위한 유망한 연구 방향을 제시한다고 결론짓는다.