Asymmetric Linear-Combination-of-Unitaries Realization of Quantum Convolution via Modular Adders

1. 연구 배경 및 문제 제기 (Problem)

• 양자 컨볼루션의 물리적 실현 가능성: 고전적인 신호 처리에서 컨볼루션은 핵심 연산이지만, 양자 컴퓨팅에서 진폭의 직접적인 곱셈 (이차적 연산) 은 물리적으로 불가능하다는 Lomont 의 'no-go' 정리가 존재합니다. 따라서 이산 원형 컨볼루션 (discrete circular convolution) 을 양자 선형 연산자로 어떻게 구현할 수 있는지가 중요한 문제였습니다.
• 기존 접근법의 한계: 기존 연구들 (Zhou & Wang, Castelazo et al.) 은 컨볼루션을 순환 행렬 (circulant matrix) 이나 유한군의 선형 결합으로 해석하여 LCU(Linear Combination of Unitaries) 프레임워크를 통해 구현할 수 있음을 보였습니다. 그러나 구체적인 회로 수준에서 복소수 계수 (complex coefficients) $b_i$의 위상 (phase) 을 보존하는 방식과 핵심 (kernel) 상태 준비의 비대칭성을 명확히 연결한 연구는 부족했습니다. 특히, 대칭적인 오버랩을 사용하면 계수의 크기의 제곱 ($|b_i|^2$) 만 남게 되어 위상 정보가 소실되는 문제가 있었습니다.
• 목표: 모듈러 가산기 (modular adder) 를 제어된 시프트 (controlled-shift) 연산자로 사용하여, 원형 컨볼루션을 비대칭 LCU로 명시적으로 구현하고, 이를 통해 위상 정보를 보존하며 효율적인 회로 구조를 제시하는 것입니다.

2. 주요 방법론 (Methodology)

이 논문은 다음과 같은 세 가지 핵심 방법론을 제시합니다.

가. 비대칭 LCU 및 모듈러 가산기 기반 구현 (Asymmetric LCU via Modular Adders)

• 비대칭성 (Asymmetry): 컨볼루션 연산 $C_n(b)$을 구현할 때, 포스트셀렉션 (postselection) 상태는 고정된 균일 상태 $|u\rangle$로 두고, 입력 안시라 (ancilla) 에는 문제 의존적인 커널 상태 $|b\rangle$를 공급합니다.
  • 대칭적 접근 ($|b\rangle$을 양쪽에서 사용) 은 $|b_i|^2$ 가중치만 생성하여 위상을 잃게 만듭니다.
  • 비대칭적 접근 ($|u\rangle$과 $|b\rangle$의 조합) 은 복소수 계수 $b_i$ 자체를 보존하여 정확한 컨볼루션을 수행합니다.
• 모듈러 가산기 (Modular Adder): 제어된 시프트 연산자 $SELECT_L$은 계산 기저 상태에서의 모듈러 덧셈 ($|i\rangle|k\rangle \to |i\rangle|k+i \pmod N\rangle$) 과 수학적으로 동일합니다. 따라서 기존의 양자 모듈러 가산기 (Ripple-carry, QFT 기반 등) 를 $SELECT$ 블록으로 직접 사용할 수 있습니다.

나. $J_n$-대칭화 및 에르미트 연산자 (Jn-Symmetrization and Hermitian Operator)

• 반전 행렬 도입: $J_n = X^{\otimes n}$ (비트 반전) 행렬을 도입하여 반사된 시프트 연산자 $\tilde{L}_{i,n} = L_{i,n} J_n$을 정의합니다.
• 대칭화 컨볼루션: 표준 컨볼루션 $C_n(b)$은 $H_n(b)J_n$으로 표현됩니다. 여기서 $H_n(b) = \sum b_i \tilde{L}_{i,n}$은 실수 커널의 경우 에르미트 (Hermitian) 연산자가 됩니다.
• 의의: 이 변환은 컨볼루션 연산자를 QSVT(Quantum Singular Value Transformation) 및 블록 인코딩 (block-encoding) 프레임워크에 직접적으로 적용할 수 있는 에르미트 인터페이스를 제공합니다.

다. 재귀적 구조 및 최적화된 컴파일 (Recursive Structure and Optimized Compilation)

• 구조적 재귀: 반사된 생성자 $U_n = \tilde{L}_{1,n}$에 대한 재귀적 구조를 제시하여 연산자의 대수적 성질을 명확히 합니다.
• 비트 단위 컴파일: 구조적 재귀를 설명용으로 사용하고, 실제 게이트 효율성을 위해 캐리 전파 (carry-propagation) 기반의 최적화된 비트 단위 재귀 컴파일을 제안합니다. 이는 표준 가산기 (QFT, Ripple-carry) 와 동등한 기능을 수행하면서도 모듈러한 회로 설계를 가능하게 합니다.

3. 주요 결과 (Results)

• 정리 1 (Asymmetric LCU Realization): 모듈러 가산기를 $SELECT$ 연산자로 사용할 때, 비대칭 LCU 회로를 통해 원형 컨볼루션이 정확히 구현됨을 증명했습니다. 포스트셀렉션 확률은 $p_{succ} = \frac{\|C_n(b)a\|^2}{N\|a\|^2\|b\|^2}$입니다.
• 에르미트성 보장: 커널 $b$가 실수일 때, $H_n(b)$는 에르미트 연산자가 되어, 역문제 (deconvolution) 해결 시 조건수 (condition number) 의 제곱 ($\kappa^2$) 이 아닌 선형 의존성 ($\kappa$) 을 가지는 QSVT 적용이 가능해집니다. 이는 정규 방정식 (normal equation) 기반 접근법보다 효율적입니다.
• 복잡도 분석:
  • 직접 재귀 구현: 거시 블록 (macro block) 기준 $O(\log^3 N)$, 기본 CNOT 게이트 기준 $O(\log^4 N)$.
  • 최적화된 비트 단위 컴파일: 거시 블록 기준 $O(\log^2 N)$, 기본 CNOT 게이트 기준 $O(\log^3 N)$.
  • 기존 가산기 비교: Ripple-carry 가산기를 사용하면 $O(\log N)$, QFT 가산기를 사용하면 $O(\log^2 N)$의 게이트 복잡도를 가집니다.
  • 입력 모델: 데이터와 커널이 이미 양자 상태 (coherent quantum state) 로 준비된 경우, 상태 준비 비용이 제거되어 컨볼루션 블록 자체의 비용이 $O(\text{polylog}(N))$으로 매우 효율적입니다.

4. 기여 및 의의 (Significance)

1. 명시적인 비대칭 LCU 공식화: 양자 컨볼루션이 모듈러 가산기를 기반으로 한 비대칭 LCU 블록으로 구현될 수 있음을 명확히 하고, 이 과정에서 커널 계수의 위상 정보가 보존됨을 규명했습니다. 이는 기존 연구들이 간과했던 '상태 공급 (supplied-state)' 모델의 핵심 이점을 부각시킵니다.
2. 에르미트 인터페이스 제공: $J_n$ 행렬을 도입하여 컨볼루션 연산자를 에르미트 형태로 변환함으로써, QSVT 및 기타 스펙트럼 변환 기법을 직접 적용할 수 있는 길을 열었습니다. 이는 역문제 (deconvolution) 해결 시 조건수 제곱 문제를 피하고 더 낮은 다항식 차수 (polynomial degree) 로 근사할 수 있게 합니다.
3. 구조적 투명성과 최적화의 조화: 연산자의 대수적 구조를 명확히 보여주는 재귀적 설계와 실제 게이트 효율성을 극대화한 최적화된 컴파일을 동시에 제시하여, 이론적 분석과 실용적 구현 사이의 간극을 좁혔습니다.
4. 범용성: 이 프레임워크는 순환 행렬 구현, Toeplitz 시스템, 군 컨볼루션 등 다양한 구조화된 행렬 연산에 대한 통일된 관점을 제공합니다.

5. 결론

이 논문은 양자 컨볼루션을 모듈러 가산기를 통한 비대칭 LCU 로 재해석함으로써, 위상 보존과 에르미트성 확보를 동시에 달성했습니다. 특히, 데이터와 커널이 양자 상태로 이미 준비된 시나리오에서 매우 효율적인 연산을 제공하며, QSVT 를 활용한 역문제 해결에 있어 새로운 표준 (standard) 을 제시합니다. 이는 양자 신호 처리 및 양자 머신러닝 분야에서 컨볼루션 연산의 실용적 구현을 위한 중요한 이론적, 기술적 기반을 마련했습니다.