기술 요약: $\delta$-약화 SMT를 통한 광학 회로 탐색

문제 정의

본 논문은 선형 광학을 사용하여 양자 컴퓨팅 게이트를 모사할 수 있는 광학 회로의 합성을 다룹니다. 선형 광학 양자 컴퓨팅(LOQC)에서 양자 게이트는 빔 분할기(beam splitters), 위상 변조기(phase shifters), 검출기(detectors)와 같은 기본 구성 요소를 사용하여 구현됩니다. 이 분야의 근본적인 과제는 단일 양자 게이트가 각각 특정 성공 확률과 원치 않는 방식으로 작용할 확률을 가진 수많은 회로 구성으로 표현될 수 있다는 점입니다.

핵심 문제는 **문제 3(Problem 3)**으로 정의됩니다: $q$개의 큐비트에 작용하는 목표 유니터리 양자 연산 $U$, 특정 수의 광학 와이어($2q + m_a$, 여기서 $m_a$는 보조 와이어를 나타냄), 그리고 동시 계수 기저(coincidence basis) $C$가 주어졌을 때, 성공 확률($|\alpha|^2$)을 최대화하는 듀얼 레일(dual-rail) 광학 연산의 전송 행렬 $\hat{U}$를 찾는 것입니다. 솔루션은 $\hat{U}$의 작용이 복소 스케일링 인자 $\alpha$에 의해 스케일링된 상태로 포크 공간(Fock space)의 관련 부분 공간(동시 계수 기저 $C$)에서 $U$를 모사하도록 보장해야 합니다.

저자들은 두 가지 측정 체계를 구분합니다:

1. 사후 선택(Post-selection): 모든 와이어를 측정하며, 양자 계산 기저와 일치하는 결과만을 수락합니다.
2. 헤럴디드 선택(Heralded selection): 보조 와이어만을 측정합니다. 만약 이들이 초기 상태(예: 진공 상태)로 돌아오면, 해당 연산은 성공한 것으로 간주되어 큐비트 상태를 재사용할 수 있습니다.

방법론

비선형 실수 산술(NRA)로의 인코딩

저자들은 합성 문제를 비선형 실수 산술(Non-Linear Real Arithmetic, NRA) 내의 제약 충족 문제로 변환합니다. 전송 행렬 $\hat{U}$와 성공 진폭 $\alpha$는 실수 변수로 모델링됩니다(단, 논문에서는 복소 변수가 실수 쌍으로 인코딩될 수 있다고 언급함).

제약 조건은 다음과 같이 공식화됩니다:

• 유니터리성(Unitarity): $\hat{U}$는 유니터리 행렬($\hat{U}\hat{U}^\dagger = I$)이어야 합니다. 이는 이차 다항식 제약을 생성합니다.
• 범위(Bounds): 변수는 $[-1, 1]$ 범위로 제한됩니다.
• 포크 공간 등가성(Fock Space Equivalence): 핵심 제약 조건은 포크 기저 상태(구체적으로 동시 계수 기저 $C$)에 대한 $\hat{U}$의 작용이 $\alpha$로 스케일링된 목표 연산 $U$와 같아야 함을 요구합니다. 이는 $k$차 다항식 제약을 생성하며, 여기서 $k$는 회로에 사용된 광자의 수에 따라 달라집니다.

$\delta$-약화( $\delta$-weakening) 및 dReal

표준 SMT 솔버는 일반적인 NRA의 결정 불가능성, 특히 고차 다항식이 포함된 경우 어려움을 겪습니다. 저자들은 dReal 솔버에서 구현된 기술인 $\delta$-약화를 활용합니다. 정확한 등식($f(x) = 0$)을 요구하는 대신, $\delta$-약화는 작은 섭동($|f(x)| \le \delta$)을 허용합니다.

• 만약 허용 오차 $\delta$ 내에 솔루션이 존재하면, dReal은 값의 영역($\delta$-sat)을 반환합니다.
• 이 접근 방식은 표준 솔버가 솔루션을 찾지 못하거나 과도한 시간이 걸릴 수 있는 것과 달리, 근사 솔루션을 훨씬 빠르게 찾을 수 있게 해줍니다.

탐색 알고리즘 및 정밀화

합성 과정은 반복 탐색 알고리즘(Algorithm 1)을 채택합니다:

1. 반복 최적화: 알고리즘은 최소 성공 임계값 $\alpha_{min}$에서 시작합니다. dRead에 쿼리를 보내 제약 조건을 만족하면서 성공 확률이 $\alpha_{min}$보다 큰 전송 행렬을 찾습니다.
2. 임계값 업데이트: 솔루션이 발견되면, $\alpha_{min}$을 발견된 확률의 상한보다 약간 높게 업데이트하고 탐색을 반복합니다.
3. 종료: 루프는 타임아웃이 발생하거나 솔버가 "unsat"(현재 임계값 이상의 솔루션이 존재하지 않음)을 반환할 때까지 계속됩니다.
4. 정확한 복구(Exact Recovery): dReal은 근사값의 영역을 반환하므로, 저자들은 이 영역 내의 행렬에 **특이값 분해(SVD)**를 적용합니다. 특이값을 1로 대체함으로써 엄격한 유니터리 행렬을 구축합니다. 그런 다음 결과 행렬들을 목표 $U$와 비교하여 최적의 후보를 선택함으로써, $\delta$-근사를 실행 가능한 정확한 전송 행리로 변환합니다.

주요 기여

1. 새로운 합성 기술: 본 논문은 선형 광학 회로 합성에 $\delta$-약화 SMT 솔버를 적용한 첫 사례를 소개합니다. 이 접근 방식은 회로 설계를 글로벌 최적화 문제로 취급한다는 점에서 기존의 분해 방식이나 계산 단순화 도구와 다릅니다.
2. 자동화 및 일반성: 도구는 완전히 자동화되어 있습니다. 사용자가 목표 게이트와 회로 설정(와이어, 광자)을 입력하면, 시스템은 수동적인 구조 유도 없이 최적의 전송 행렬을 탐색합니다.
3. 근사 처리: 저자들은 $\delta$-SMT 솔버가 제공하는 근사 솔루션과 물리적 구현에 필요한 정확한 유니터리 행렬 사이의 간극을 SVD 정밀화 기법을 사용하여 메우는 엄격한 방법을 제공합니다.
4. 복소 변수 인코딩: 복소 변수(일반적인 양자 게이트에 필수적임)를 실수 쌍으로 인코딩하는 이론적 가능성을 논의하며, 이로 인한 계산 복잡도의 증가를 인정합니다.

결과

도구는 알려진 문헌 결과와 대조하여 검증되었으며, 새로운 구성을 탐색하는 데 사용되었습니다:

• 사후 선택 결과:

  • 검증: 도구는 알려진 불가능성 결과(예: 0 또는 1개의 보조 진공 와이어를 가진 CZ 게이트는 불가능함)를 성공적으로 검증하였고, 알려진 최적 회로(예: 2개의 진공 와이어를 통해 $1/9$ 성공 확률을 달성하는 CZ)를 재현했습니다.
  • 보조 와이어 탐색: 저자들은 다양한 광자 수를 가진 단일 보조 와이어를 사용하여 CZ 게이트를 합성하는 과정을 조사했습니다. 결과는 이전 연구들과 유사하게, 광자 수가 1개를 초과하여 증가함에 따라 성공 확률이 일반적으로 감소함을 보여주었습니다.
  • 기븐스 회전(Givens Rotations): 도구는 (양자 화학에 범용적인) 기븐스 회전 게이트를 위한 회로를 합성했습니다. 특정 각도(예: $\theta = \pi/2$)에 대해 $1/9$의 성공 확률을 달성할 수 있음을 발견했습니다. 데이터는 회전 각도와 최대 달성 가능 성공 확률 사이의 관계를 시사했으며, $\theta \approx 0.5$ 근처에서 최솟값을 가짐을 보여주었습니다.

• 헤럴디드 결과:

  • 도구는 특정 헤럴디드 설정(예: 0 또는 1개의 진공 와이어를 가진 CZ)의 불가능성을 확인했습니다.
  • 그러나 알려진 헤럴디드 솔루션(예: 각각 하나씩의 광자를 포함하는 두 개의 보조 와이어를 가진 CZ)을 찾는 과정에서 도구가 빈번하게 "unknown"(타임아웃으로 인한)을 반환했습니다. 저자들은 이를 다항식의 차수가 높아지고 필요한 방정식의 수가 급증함에 따라 현재의 SMT 솔버가 한계에 부딪히기 때문이라고 설명합니다.

의의 및 한계

의의:
본 논문은 SMT 기반 합성이 선형 광학 회로를 설계하는 데 있어 유효하고 강력한 방법임을 입증하며, 알려진 결과를 재현할 뿐만 아니라 새로운 구성(기븐스 회전 등)을 발견할 수 있음을 보여줍니다. 이 기술은 다항식 차수가 관리 가능한 수준으로 유지되는 사후 선택 체계에서 특히 효과적입니다. 저자들은 (기븐스 회전을 사용하는) 양자 화학용 광학 회로가 일반적인 양자 컴퓨팅 게이트보다 최적으로 합성하기에 더 용이할 수 있다고 제안합니다.

한계 및 향리 과제:
저자들은 현재의 범위에 대해 겸허한 태도를 보입니다:

• 헤럴디드 체계: 이 기술은 현재 다항식의 높은 차수로 인해 헤럴디드 선택 적용 시 "벽"에 부딪히고 있습니다.
• 복소 변수: 이론적으로는 가능하지만, 복소 변수를 인코딩하는 것은 변수와 제약 조건을 두 배로 늘려 계산 시간을 크게 증가시킵니다. 복잡한 위상을 가진 다중 큐비트 게이트에 대한 솔루션을 찾는 것은 현재의 도구로는 어렵습니다.
• 확장성: 이 방법은 제약 조건의 폭발적인 증가로 인해 3개 이상의 큐비트에 작용하는 게이트(예: Toffoli 게이트)를 다루는 데 어려움을 겪습니다.

논문은 이 분야의 발전을 위해 NRA에서의 유계 차수 다항식(bounded-degree polynomials)을 처리하는 기술이나 효율적인 복소 산술(Complex Arithmetic, CA) 이론 솔버의 발전이 필요하다고 결론짓습니다.