산술 회로

비가역 연산을 reversible하게 만들기

고전 덧셈 a+b는 입력을 덮어쓰면 비가역입니다. 양자 회로에서는 보통 아래처럼 target register에 더합니다.

$$
|a,b\rangle\mapsto |a,a+b\rangle
$$

입력 a가 남아 있으므로 역연산이 가능합니다.

1비트 half adder

합 비트와 carry는 아래입니다.

$$
s=a\oplus b,\qquad c=ab
$$

CNOT으로 XOR를 만들고 Toffoli로 AND carry를 만듭니다.

$$
|a,b,0\rangle \xrightarrow{\mathrm{CCX}} |a,b,ab\rangle
$$

Ripple-carry adder

여러 비트 덧셈은 carry를 낮은 자리에서 높은 자리로 전달합니다.

$$
s_i=a_i\oplus b_i\oplus c_i
$$

$$
c_{i+1}=a_ib_i\oplus a_ic_i\oplus b_ic_i
$$

깊이는 대략 비트수에 선형으로 증가합니다. ancilla를 더 쓰면 병렬 prefix adder로 깊이를 줄일 수 있지만 큐비트 수가 늘어납니다.

Modular arithmetic

Shor 알고리즘에서 필요한 핵심은 modular multiplication과 exponentiation입니다.

$$
|x\rangle\mapsto |a x \bmod N\rangle
$$

이는 controlled modular addition의 반복으로 구현할 수 있습니다. 실제 비용은 Shor 회로의 대부분을 차지합니다.

Comparator

비교 회로는 조건부 연산에 필요합니다. 예를 들어 a\ge N이면 N을 빼는 modular reduction을 만들 수 있습니다.

회로설계 관점에서는 comparator가 남긴 flag와 borrow/carry ancilla를 반드시 uncompute해야 합니다.

비용 감각

• 덧셈: 보통 O(n) 깊이와 O(n) Toffoli 계열 비용
• 곱셈: 덧셈을 반복하므로 더 비쌉니다.
• modular exponentiation: controlled multiplication 반복이라 Shor의 핵심 병목입니다.

Full adder를 reversible하게 보기

한 자리 덧셈은 입력 a_i,b_i,c_i에서 sum과 next carry를 만듭니다.

$$
s_i=a_i\oplus b_i\oplus c_i
$$

$$
c_{i+1}
=
(a_i b_i)\oplus(a_i c_i)\oplus(b_i c_i)
$$

하지만 이 식을 그대로 회로로 옮기면 중간 AND가 여러 개 필요합니다. 실제 reversible adder는 majority/unmajority 구조를 써서 carry를 앞으로 밀고, 마지막에 역순으로 중간값을 정리하는 방식이 많습니다.

핵심 감각은 단순합니다. carry를 만들 때는 Toffoli가 필요하고, sum을 만들 때는 CNOT들이 필요합니다. 덧셈의 비싼 부분은 대체로 carry 경로입니다.

in-place 덧셈과 out-of-place 덧셈

out-of-place 덧셈은 결과 레지스터를 따로 둡니다.

$$
|a,b,0\rangle\mapsto |a,b,a+b\rangle
$$

구조가 이해하기 쉽지만 width가 큽니다. in-place 덧셈은 한 입력 레지스터를 결과로 덮어씁니다.

$$
|a,b\rangle\mapsto |a,a+b\rangle
$$

이 형태도 reversible입니다. 왜냐하면 a가 남아 있으므로 (a+b)-a=b를 복원할 수 있기 때문입니다. 회로설계에서는 width를 아끼려면 in-place, 이해와 디버깅을 쉽게 하려면 out-of-place를 먼저 생각하는 식으로 접근하면 좋습니다.

controlled addition

Shor나 oracle 설계에서는 조건부 덧셈이 자주 나옵니다.

$$
|c\rangle|a\rangle|b\rangle
\mapsto
|c\rangle|a\rangle|b+c a\rangle
$$

c=0이면 아무 일도 하지 않고, c=1이면 a를 b에 더합니다. 회로 수준에서는 기존 adder의 Toffoli와 CNOT에 control이 하나 더 붙습니다. 이 control이 비용을 키웁니다.

multi-controlled 산술은 논리적으로 간단해 보여도 분해 후에는 ancilla와 2큐비트 게이트가 급격히 늘 수 있습니다. 그래서 “조건 하나 붙이면 되지”라는 말은 실제 회로 비용 관점에서는 가볍지 않습니다.

modular reduction 패턴

a+b\bmod N을 만들려면 보통 먼저 더하고, N 이상이면 N을 뺍니다.

1. s=a+b를 계산합니다.
2. comparator로 s\ge N flag를 만듭니다.
3. flag가 1이면 s\leftarrow s-N을 수행합니다.
4. 비교 과정에서 생긴 borrow/carry/flag를 uncompute합니다.

이 구조는 말로는 네 줄이지만, 실제로는 comparator와 controlled subtractor가 들어갑니다. 특히 flag를 uncompute하려면 값이 바뀐 뒤에도 비교 정보를 다시 정리할 수 있게 회로 순서를 조심해야 합니다.

곱셈은 shift-add의 반복

상수 c와 양자 레지스터 x의 곱은 비트별 조건부 덧셈으로 만들 수 있습니다.

$$
cx
=
\sum_i x_i(c2^i)
$$

따라서 x_i=1일 때 결과 레지스터에 c2^i를 더합니다. mod N 곱셈이면 각 덧셈을 modular addition으로 바꿉니다.

Shor의 controlled modular multiplication은 이 곱셈 전체에 다시 control이 붙은 형태입니다. 그래서 Shor 회로의 리소스 추정은 산술 회로를 얼마나 효율적으로 짜는지에 크게 좌우됩니다.