계산 비용 측정

다음으로, 이 강좌의 필요에 맞게 계산 비용을 측정할 수 있는 수학적 프레임워크에 대해 살펴보겠습니다. 알고리즘 분석과 계산 복잡도는 그 자체로 독립적인 방대한 주제이며, 이러한 개념에 대해 훨씬 더 많은 내용을 다루고 있습니다.

출발점으로, 이전 강의에서 소개된 다음 그림을 살펴보겠습니다. 이 그림은 계산의 매우 높은 수준의 추상화를 나타냅니다.

계산 자체는 Python으로 작성된 컴퓨터 프로그램, 튜링 기계, 불리언 Circuit, 또는 양자 Circuit 등 다양한 방식으로 모델링하거나 기술할 수 있습니다. 여기서는 Circuit(불리언 Circuit과 양자 Circuit 모두)에 집중하겠습니다.

인코딩과 입력 길이

계산 문제의 입력과 출력부터 시작해 보겠습니다. 이를 이진 문자열로 가정하겠습니다. 다른 기호를 사용할 수도 있지만, 이 논의에서는 이진 문자열 입력과 출력으로 범위를 제한하여 간단하게 유지하겠습니다. 이진 문자열을 통해, 우리가 관심을 갖는 문제들이 다루는 다양한 흥미로운 객체들을 인코딩할 수 있습니다. 예를 들어 숫자, 벡터, 행렬, 그래프뿐만 아니라 이러한 객체들의 리스트도 인코딩할 수 있습니다.

예를 들어, 음이 아닌 정수를 인코딩하기 위해 이진 표기법을 사용할 수 있습니다. 다음 표는 처음 아홉 개의 음이 아닌 정수에 대한 이진 인코딩과 각 인코딩의 길이(즉, 총 비트 수)를 나열합니다.

숫자	이진 인코딩	길이
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

원한다면 부호 비트를 표현에 추가하여 양수와 음수 모두를 처리하도록 이 인코딩을 쉽게 확장할 수 있습니다. 때로는 음이 아닌 정수의 이진 표현에 선행 0을 허용하는 것이 편리하기도 합니다. 선행 0은 인코딩되는 값을 바꾸지 않지만, 고정된 크기의 문자열이나 워드를 채울 수 있게 해줍니다.

이진 표기법을 사용하여 음이 아닌 정수를 표현하는 것은 일반적이고 효율적이지만, 원한다면 다음 표에서 제시된 것과 같이 이진 문자열을 사용하여 음이 아닌 정수를 표현하는 다른 방법을 선택할 수도 있습니다. 이러한 대안들의 세부 사항은 이 논의에서 중요하지 않습니다. 핵심은 우리가 사용하는 인코딩에 대해 선택권이 있다는 것을 명확히 하는 것입니다.

숫자	단항 인코딩	사전순 인코딩
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(이 표에서 기호 $\varepsilon$은 기호가 없고 길이가 0인 빈 문자열을 나타냅니다. 자연스럽게, 명백한 혼동을 피하기 위해 빈 문자열을 나타낼 때는 $\varepsilon$과 같은 특수 기호를 사용하며, 아무것도 쓰지 않는 방식은 쓰지 않습니다.)

벡터와 행렬, 또는 분자의 구조 설명과 같이 더 복잡한 객체들도 이진 문자열로 인코딩할 수 있습니다. 음이 아닌 정수에서와 마찬가지로 다양한 인코딩 방식을 선택하거나 고안할 수 있습니다. 주어진 문제에 대한 입력을 인코딩하기 위해 고안한 방식이 무엇이든, 입력 문자열의 길이는 해결하고자 하는 문제 인스턴스의 크기를 나타내는 것으로 해석합니다.

예를 들어, 음이 아닌 정수 $N$을 이진 표기법으로 표현하는 데 필요한 비트 수는 $\operatorname{lg}(N)$으로 표기되기도 하며, 다음 공식으로 주어집니다.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

정수 인수분해 문제의 입력을 이진 표기법으로 인코딩한다고 가정하면, 수 $N$에 대한 입력 길이는 $\operatorname{lg}(N)$입니다. 특히, 입력 $N$의 길이(또는 크기)는 $N$ 자체가 아님을 주의하세요. $N$이 클 때 이진 표기법으로 $N$을 표현하는 데 이만큼 많은 비트가 필요하지 않습니다.

엄밀한 형식적 관점에서, 계산 문제나 작업을 고려할 때마다 입력으로 주어지거나 출력으로 생성되는 객체를 인코딩하기 위한 특정 방식이 선택되었다고 이해해야 합니다. 이를 통해 흥미로운 문제를 해결하는 계산을 이진 문자열 입력에서 이진 문자열 출력으로의 추상적 변환으로 볼 수 있습니다.

객체가 이진 문자열로 인코딩되는 방식의 세부 사항은 어느 수준에서는 이러한 계산에 있어 반드시 중요합니다. 하지만 계산 비용을 분석할 때는 일반적으로 부차적인 세부 사항을 다루지 않기 위해 이러한 세부 사항을 크게 걱정하지 않습니다. 기본적인 이유는, "합리적인" 인코딩 방식들 사이에서 변환하는 계산 비용이 실제 문제를 해결하는 비용에 비해 미미할 것으로 예상하기 때문입니다. 그렇지 않은 경우에는 세부 사항을 명확히 해야 합니다(그리고 그래야 합니다).

예를 들어, 매우 간단한 계산으로 음이 아닌 정수의 이진 표현과 사전순 인코딩(위의 표에서 추론할 수 있지만 자세히 설명하지 않음) 사이를 변환할 수 있습니다. 이런 이유로, 입력 $N$에 대해 두 인코딩 중 하나를 다른 것으로 전환하기로 결정하더라도 정수 인수분해의 계산 비용은 크게 달라지지 않을 것입니다. 반면에, 음이 아닌 정수를 단항 표기법으로 인코딩하면 필요한 기호의 총 수가 지수적으로 증가하므로, 이러한 이유로 "합리적인" 인코딩 방식으로 보지 않습니다.

기본 연산

이제 계산 자체를 살펴보겠습니다. 이는 위 그림에서 파란색 직사각형으로 표현됩니다. 계산 비용을 측정하는 방법은 각 계산이 필요로 하는 기본 연산의 수를 세는 것입니다. 직관적으로 말하면, 기본 연산은 두 비트의 AND를 계산하는 것처럼 소수의 고정된 비트 또는 Qubit을 다루며 빠르고 쉽게 수행할 수 있는 연산입니다. 반면에, factorint 함수를 실행하는 것은 기본 연산으로 합리적으로 볼 수 없습니다.

형식적으로 말하면, 기본 연산으로 무엇을 구성하는지는 사용되는 계산 모델에 따라 다른 선택지가 있습니다. 여기서는 Circuit 모델, 특히 양자 Circuit과 불리언 Circuit에 초점을 맞추겠습니다.

범용 Gate 집합

Circuit 기반 계산 모델에서는 각 Gate를 기본 연산으로 보는 것이 일반적입니다. 이는 Circuit에서 허용할 Gate가 정확히 무엇인지에 대한 질문으로 이어집니다. 잠시 양자 Circuit에 집중하면, 이 시리즈에서 지금까지 $X,$ $Y,$ $Z,$ $H,$ $S,$ 및 $T$ Gate, swap Gate, Gate의 제어 버전(controlled-NOT, Toffoli, Fredkin Gate 포함), 그리고 표준 기저 측정을 나타내는 Gate를 포함한 여러 Gate를 살펴봤습니다. CHSH 게임의 맥락에서도 몇 가지 추가적인 회전 Gate를 봤습니다.

또한 쿼리 모델의 맥락에서 쿼리 Gate에 대해 논의했으며, 임의의 수의 Qubit에 작용하는 임의의 유니터리 연산 $U$를 원한다면 Gate로 볼 수 있다는 것도 살펴봤습니다. 하지만 이 두 옵션은 이 논의에서는 무시하겠습니다. 쿼리 모델에서 작업하지 않을 것이며(기본 연산을 사용한 쿼리 Gate의 구현은 강의 후반부에 논의됩니다), 잠재적으로 수백만 개의 Qubit에 작용하는 임의의 유니터리 Gate를 기본 연산으로 보는 것은 의미 있거나 현실적인 계산 비용 개념으로 이어지지 않습니다.

소수의 Qubit에 작용하는 양자 Gate를 고수하면서, 어느 것을 기본으로 볼지 결정하는 한 가지 접근 방식은 정확한 기준을 찾아내는 것입니다. 하지만 이것이 표준적인 접근 방식이나 우리가 취할 방식은 아닙니다. 대신, 단순히 선택을 합니다.

다음은 양자 Circuit의 기본 Gate 집합으로 채택할 표준적인 선택입니다:

• 다음 목록에서 단일 Qubit 유니터리 Gate: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ 및 $T^{\dagger}$
• Controlled-NOT Gate
• 단일 Qubit 표준 기저 측정

일반적인 대안으로는 Toffoli, Hadamard, $S$ Gate와 표준 기저 측정을 기본으로 보는 것입니다. 때로는 모든 단일 Qubit Gate를 기본으로 보기도 하지만, Gate가 수행되는 정확도를 적절히 고려하지 않으면 비현실적으로 강력한 모델로 이어집니다.

기본 컬렉션의 유니터리 Gate는 범용 Gate 집합이라고 불립니다. 이는 이러한 Gate만으로 구성된 Circuit을 사용하여 원하는 정확도로 임의의 수의 Qubit에 대한 임의의 유니터리 연산을 근사할 수 있음을 의미합니다. 명확히 하면, 범용성의 정의는 이러한 근사의 비용, 즉 집합에서 필요한 Gate의 수에 대해 아무런 요구 사항을 두지 않습니다. 실제로, 측도의 수학적 개념에 기반한 비교적 간단한 논증은 대부분의 유니터리 연산이 극도로 높은 비용을 가져야 함을 드러냅니다. 양자 Gate 집합의 범용성을 증명하는 것은 간단한 문제가 아니며 이 강좌에서는 다루지 않습니다.

불리언 Circuit에서는 AND, OR, NOT, FANOUT Gate를 기본 연산을 나타내는 것으로 취급하겠습니다. AND Gate와 OR Gate 모두 실제로 필요하지는 않습니다. 드 모르간의 법칙을 사용하여 세 입출력 와이어 모두에 NOT Gate를 배치함으로써 어느 것에서 다른 것으로 변환할 수 있습니다. 그럼에도 불구하고 AND와 OR Gate 모두를 허용하는 것이 일반적이고 편리합니다. AND, OR, NOT, FANOUT Gate는 결정론적 계산을 위한 범용 집합을 형성하는데, 이는 고정된 수의 입력 비트에서 고정된 수의 출력 비트로의 임의의 함수가 이러한 Gate로 구현될 수 있음을 의미합니다.

측정 지연 원칙

표준 기저 측정 Gate는 양자 Circuit 내에 나타날 수 있지만, 때로는 끝까지 지연하는 것이 편리합니다. 이를 통해 양자 계산을 유니터리 부분(계산 자체를 나타냄)으로 구성되고, 이후 Qubit이 측정되고 결과가 출력되는 단순한 읽기 단계가 따르는 것으로 볼 수 있습니다. 표준 기저 측정마다 추가 Qubit을 하나씩 추가할 의향이 있다면 항상 이렇게 할 수 있습니다. 다음 그림에서 오른쪽 Circuit은 왼쪽 Gate에 대해 이를 어떻게 할 수 있는지 보여줍니다.

구체적으로, 왼쪽 Circuit의 고전 비트는 오른쪽에서 Qubit으로 대체되며($\vert 0\rangle$ 상태로 초기화됨), 표준 기저 측정은 controlled-NOT Gate로 대체된 다음 하단 Qubit에 대한 표준 기저 측정이 따릅니다. 핵심은 오른쪽 Circuit의 표준 기저 측정이 Circuit의 끝까지 밀려날 수 있다는 것입니다. 왼쪽 Circuit의 고전 비트가 나중에 제어 비트로 사용된다면, 오른쪽 Circuit에서 대신 하단 Qubit을 제어로 사용할 수 있으며, 전체적인 효과는 동일합니다. (왼쪽 Circuit의 고전 비트가 측정 후 다른 측정에 의해 덮어쓰이지 않는다고 가정합니다. 만약 덮어쓰인다면 이전 측정에 사용된 비트를 덮어쓰는 대신 새 고전 비트를 사용하면 됩니다.)

Circuit 크기와 깊이

Circuit 크기

Circuit의 총 Gate 수를 해당 Circuit의 크기라고 합니다. 따라서 Circuit의 Gate가 기본 연산을 나타낸다고 가정하면, Circuit의 크기는 필요한 기본 연산의 수, 즉 다시 말해 계산 비용을 나타냅니다. 주어진 Circuit $C$의 크기를 $\operatorname{size}(C)$로 표기합니다.

예를 들어, 두 비트의 XOR을 계산하는 다음 불리언 Circuit을 고려해 보겠습니다.

이 Circuit의 크기는 총 7개의 Gate가 있으므로 7입니다. (Fanout 연산이 항상 Gate로 계산되지는 않지만, 이 강의에서는 Gate로 계산합니다.)

시간, 비용, Circuit 깊이

시간은 계산에서 매우 중요한 자원이며 제한적인 제약 조건입니다. RSA1024 인수분해 작업과 같은 위의 예시들은 이 관점을 강화합니다. factorint 함수가 RSA1024를 인수분해하는 데 실패하는 것이 아니라, 단지 완료하도록 충분한 시간이 없을 뿐입니다.

계산을 수행하는 데 필요한 기본 연산의 수로서의 계산 비용 개념은 계산을 구현하는 데 필요한 시간의 추상적인 대리자로 의도됩니다. 각 기본 연산은 수행하는 데 일정한 시간이 필요하며, 계산에 필요한 연산이 많을수록 최소한 일반적으로는 더 오래 걸립니다. 단순성을 위해, 계산 비용과 알고리즘 실행에 필요한 시간 사이의 이러한 연관성을 계속 유지하겠습니다.

하지만 Circuit의 크기가 실행하는 데 걸리는 시간과 직접적으로 일치하지 않을 수 있음을 주목하세요. 예를 들어 두 비트의 XOR을 계산하는 불리언 Circuit에서 두 FANOUT Gate는 동시에 수행될 수 있으며, 두 NOT Gate도, 두 AND Gate도 마찬가지입니다. 이러한 병렬화 가능성을 고려하는 Circuit 효율성을 측정하는 또 다른 방법은 깊이입니다. 이는 Circuit에서 필요한 레이어의 최소 수이며, 각 레이어 내의 Gate는 서로 다른 와이어에서 작동합니다. 동등하게, Circuit의 깊이는 입력 와이어에서 출력 와이어까지의 경로에서 만나는 최대 Gate 수입니다. 위의 Circuit에서는 깊이가 4입니다.

Circuit 깊이는 병렬 계산의 실행 시간을 형식화하는 한 가지 방법입니다. 이는 고급 주제이며, 특정 계산에 필요한 깊이를 최소화하는 매우 정교한 Circuit 구성이 존재합니다. Circuit 깊이에 관한 매력적인 미해결 질문들도 있습니다. (예를 들어, GCD를 계산하는 데 필요한 Circuit 깊이에 대해 아직 많은 것이 알려져 있지 않습니다.) 이 시리즈에서 Circuit 깊이에 대해 더 많이 언급하지 않겠지만, 진행하면서 Circuit 깊이에 관한 몇 가지 흥미로운 사실을 포함할 예정이며, 병렬화가 잠재적인 계산 이점의 원천임을 명확히 인정해야 합니다.

다른 Gate에 비용 할당

Circuit 크기와 계산 비용에 관한 마지막 참고 사항으로, 모든 Gate를 총 비용에 동등하게 기여하는 것으로 보는 대신 Gate에 다른 비용을 할당하는 것이 가능합니다.

예를 들어, 이미 언급했듯이 FANOUT Gate는 불리언 Circuit에서 종종 무료로 보입니다. 즉, FANOUT Gate의 비용을 0으로 선택할 수 있습니다. 또 다른 예로, 쿼리 모델에서 작업하고 Circuit이 입력 함수(블랙 박스 형태)에 대해 수행하는 쿼리 수를 세는 경우, 실질적으로 쿼리 Gate에 단위 비용을 할당하고 Hadamard Gate와 같은 다른 Gate에는 0 비용을 할당합니다. 마지막 예로, 구현하기 어렵기에 따라 Gate에 다른 비용을 할당하는 경우가 있는데, 이는 고려되는 하드웨어에 따라 달라질 수 있습니다.

이러한 옵션들은 모두 다른 맥락에서 합리적이지만, 이 강의에서는 간단하게 유지하고 계산 비용의 표현으로 Circuit 크기를 고수하겠습니다.

입력 길이의 함수로서의 비용

우리는 주로 입력이 점점 커질수록 계산 비용이 어떻게 확장되는지에 관심이 있습니다. 이를 위해 알고리즘의 비용을 입력 길이의 함수로 표현합니다.

Circuit 패밀리

주어진 계산 문제에 대한 입력은 길이가 다양하며, 임의로 커질 수 있습니다. 반면 모든 Circuit은 고정된 수의 Gate와 선(wire)을 가지고 있습니다. 따라서 Circuit을 기준으로 알고리즘을 생각할 때, 알고리즘을 표현하려면 일반적으로 무한히 큰 Circuit 패밀리가 필요합니다. Circuit 패밀리란 크기가 점점 커지는 Circuit의 수열로, 점점 더 큰 입력을 수용할 수 있도록 합니다.

예를 들어, factorint가 사용하는 것과 같은 정수 인수분해를 위한 고전 알고리즘이 있다고 가정해 봅시다. 모든 고전 알고리즘과 마찬가지로 이 알고리즘은 불리언 Circuit으로 구현할 수 있습니다. 단, 가능한 각 입력 길이마다 별도의 Circuit이 필요합니다. 서로 다른 입력 길이에 대한 결과 Circuit을 살펴보면, 입력 길이가 커질수록 크기가 자연스럽게 증가하는 것을 알 수 있습니다. 이는 예를 들어 4비트 정수를 인수분해하는 것이 1024비트 정수를 인수분해하는 것보다 훨씬 쉽고 훨씬 적은 기본 연산이 필요하다는 사실을 반영합니다.

이를 통해 알고리즘의 계산 비용을 함수 $t$로 표현하는데, $t(n)$은 $n$비트 입력에 대해 알고리즘을 구현하는 Circuit의 Gate 수로 정의됩니다. 더 형식적인 표현으로, 불리언 Circuit 모델에서의 알고리즘은 Circuit의 수열 $\{C_1, C_2, C_3,\ldots\}$로 설명되며, 여기서 $C_n$은 $n$비트 입력(또는 더 일반적으로는 $n$에 의해 어떤 방식으로 매개변수화된 크기를 가진 입력)에 대해 해당 문제를 풀고, 이 알고리즘의 비용을 나타내는 함수 $t$는 다음과 같이 정의됩니다.

$$t(n) = \operatorname{size}(C_n).$$

양자 Circuit의 경우도 마찬가지로, 더 긴 입력 문자열을 수용하려면 점점 더 큰 Circuit이 필요합니다.

예시: 정수 덧셈

더 자세히 설명하기 위해, 정수 인수분해나 최대공약수 계산보다 훨씬 단순한 정수 덧셈 문제를 잠시 살펴봅시다.

정수 덧셈

입력: 정수 $N$과 $M$
출력: $N+M$

이 문제를 풀기 위한 불리언 Circuit을 어떻게 설계할 수 있을까요?

단순하게 유지하기 위해, $N$과 $M$이 모두 이진 표기법을 사용하는 $n$비트 문자열로 표현된 음이 아닌 정수인 경우로 제한합니다. 이 인코딩에서 앞자리 0을 허용하므로

$$0\leq N,M\leq 2^n - 1.$$

출력은 합을 나타내는 $(n+1)$비트 이진 문자열이 되며, 이는 결과를 표현하는 데 필요한 최대 비트 수입니다.

먼저 알고리즘부터 시작합니다. 이진 표현의 덧셈을 위한 표준 알고리즘은 전 세계 초등학교에서 가르치는 덧셈 방법의 2진수 버전입니다. 이 알고리즘은 다음과 같이 불리언 Circuit으로 구현할 수 있습니다.

최하위 비트부터 시작하여, 두 최하위 비트의 XOR을 계산해 합의 최하위 비트를 구합니다. 그런 다음 올림 비트(carry bit)를 계산하는데, 이는 $N$과 $M$의 두 최하위 비트의 AND입니다. 이 두 연산을 합쳐서 *반가산기(half adder)*라고 부르기도 합니다.

앞에서 여러 번 살펴본 XOR Circuit과 AND Gate, 그리고 두 개의 FANOUT Gate를 사용하면 10개의 Gate로 반가산기를 만들 수 있습니다. 어떤 이유로 XOR Gate를 기본 연산 집합에 포함하기로 결정했다면, 반가산기를 만들기 위해 AND Gate 1개, XOR Gate 1개, FANOUT Gate 2개가 필요할 것입니다.

더 유효한 비트로 넘어가면 비슷한 절차를 사용하지만, 이번에는 이전 자리의 올림 비트를 계산에 포함합니다. 두 개의 반가산기를 연결하고 각각이 생성하는 올림 비트의 OR을 취하면 *전가산기(full adder)*라고 알려진 것을 만들 수 있습니다.

이것은 총 21개의 Gate가 필요합니다: AND Gate 2개, XOR Gate 2개(각각 구현에 7개의 Gate 필요), OR Gate 1개, FANOUT Gate 4개.

마지막으로, 전가산기를 연결하면 음이 아닌 정수 덧셈을 위한 불리언 Circuit을 얻을 수 있습니다. 예를 들어, 다음 Circuit은 두 4비트 정수의 합을 계산합니다.

일반적으로, 이에는

$$21 (n-1) + 10 = 21 n - 11$$

개의 Gate가 필요합니다. XOR Gate를 기본 연산 집합에 포함하기로 했다면, AND Gate $2n-1$개, XOR Gate $2n-1$개, OR Gate $n-1$개, FANOUT Gate $4n-2$개로 총 $9n-5$개의 Gate가 필요합니다. FANOUT Gate를 세지 않기로 한다면 $5n-3$개의 Gate가 됩니다.

점근 표기법

한편으로는 위의 정수 덧셈 예시처럼 다양한 계산을 수행하는 데 정확히 몇 개의 Gate가 필요한지 아는 것이 좋습니다. 이러한 세부 사항은 실제로 Circuit을 구축하는 데 중요합니다.

반면에 덧셈보다 훨씬 복잡한 작업을 포함하여 우리가 관심 있는 모든 계산에 대해 이 수준의 세부 분석을 수행하면 금방 세부 사항에 파묻히게 됩니다. 다루기 쉽도록 유지하고 부차적인 세부 사항을 의도적으로 억제하기 위해, 알고리즘을 분석할 때 일반적으로 빅-O 표기법을 사용합니다. 이 표기법을 통해 함수가 증가하는 차수를 표현할 수 있습니다.

형식적으로 말하면, 두 함수 $g(n)$과 $h(n)$이 있을 때, 양의 실수 $c > 0$과 양의 정수 $n_0$가 존재하여

$$g(n) \leq c\cdot h(n)$$

이 모든 $n \geq n_0$에 대해 성립하면 $g(n) = O(h(n))$이라고 씁니다. 일반적으로 $h(n)$은 가능한 한 단순한 표현으로 선택하여, 이 표기법이 함수의 극한 동작을 간단한 용어로 나타낼 수 있도록 합니다. 예를 들어, $17 n^3 - 257 n^2 + 65537 = O(n^3)$입니다.

이 표기법은 여러 인수를 가진 함수로 상당히 간단한 방식으로 확장될 수 있습니다. 예를 들어, 양의 정수 $n$과 $m$에 대해 정의된 두 함수 $g(n,m)$과 $h(n,m)$이 있을 때, 양의 실수 $c > 0$과 양의 정수 $k_0$가 존재하여

$$g(n,m) \leq c\cdot h(n,m)$$

이 $n+m \geq k_0$인 경우에 성립하면 $g(n,m) = O(h(n,m))$이라고 씁니다.

이 표기법을 음이 아닌 정수 덧셈의 예시와 연결하면, 두 $n$비트 음이 아닌 정수를 더하는 $C_n$으로 구성된 불리언 Circuit 패밀리 $\{C_1, C_2,\ldots,\}$가 존재하여 $\operatorname{size}(C_n) = O(n)$임을 알 수 있습니다. 이는 덧셈 비용이 입력 크기에 따라 어떻게 확장되는지의 가장 본질적인 특징을 드러냅니다: 선형적으로 확장됩니다.

또한 XOR Gate의 비용을 1로 볼지 7로 볼지와 같은 구체적인 세부 사항에 의존하지 않는다는 점도 주목하세요. 일반적으로 빅-O 표기법을 사용하면 이러한 저수준 세부 사항에 민감하지 않은 계산 비용에 대한 설명을 할 수 있습니다.

추가 예시

다음은 곱셈을 시작으로 계산 수론의 몇 가지 추가 문제 예시입니다.

정수 곱셈

입력: 정수 $N$과 $M$
출력: $NM$

이 문제에 대한 불리언 Circuit을 만드는 것은 덧셈을 위한 Circuit을 만드는 것보다 더 어렵습니다. 그러나 표준 곱셈 알고리즘을 생각하면 이 문제에 대해 크기 $O(n^2)$의 Circuit을 만들 수 있습니다($N$과 $M$이 모두 $n$비트 이진 표현으로 표현된다고 가정). 더 일반적으로, $N$이 $n$비트이고 $M$이 $m$비트라면, $N$과 $M$을 곱하기 위한 크기 $O(nm)$의 불리언 Circuit이 존재합니다.

실제로 더 잘 확장되는 다른 곱셈 방법들이 있습니다. 예를 들어, Schönhage-Strassen 곱셈 알고리즘은 비용 $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n)))$으로 두 $n$비트 정수를 곱하는 불리언 Circuit을 만드는 데 사용할 수 있습니다. 하지만 이 방법의 복잡성으로 인해 오버헤드가 많이 발생하여, 수만 비트를 가진 수에 대해서만 실용적입니다.

또 다른 기본적인 문제는 나눗셈으로, 정수 제수와 피제수가 주어졌을 때 몫과 나머지를 모두 계산하는 것을 의미합니다.

정수 나눗셈

입력: 정수 $N$과 $M\neq0$
출력: $0\leq r < |M|$이고 $N = q M + r$을 만족하는 정수 $q$와 $r$

정수 나눗셈의 비용은 곱셈과 유사합니다: $N$이 $n$비트이고 $M$이 $m$비트라면, 이 문제를 풀기 위한 크기 $O(nm)$의 불리언 Circuit이 존재합니다. 곱셈과 마찬가지로 점근적으로 더 우수한 방법들도 알려져 있습니다.

이제 최대공약수(GCD) 계산을 위한 알려진 알고리즘을 덧셈 및 곱셈과 비교할 수 있습니다. $n$비트 수 $N$과 $m$비트 수 $M$의 GCD를 계산하는 유클리드 알고리즘은 크기 $O(nm)$의 불리언 Circuit이 필요하며, 이는 곱셈과 나눗셈의 표준 알고리즘과 유사합니다. 곱셈과 나눗셈과 마찬가지로 점근적으로 더 빠른 GCD 알고리즘들도 있습니다. 두 $n$비트 수의 GCD를 계산하는 데 $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$개의 기본 연산이 필요한 알고리즘도 포함됩니다.

수론에서 발생하는 다소 더 비용이 많이 드는 계산은 *모듈식 거듭제곱(modular exponentiation)*입니다.

정수 모듈식 거듭제곱

입력: $K\geq 0$이고 $M\geq 1$인 정수 $N,$ $K,$ $M$
출력: $N^K \hspace{1mm} (\text{mod }M)$

$N^K\hspace{1mm} (\text{mod }M)$은 $N^K$를 $M$으로 나눈 나머지, 즉 $0\leq r < M$이고 어떤 정수 $q$에 대해 $N^K = q M + r$을 만족하는 유일한 정수 $r$을 의미합니다.

$N$이 $n$비트, $M$이 $m$비트, $K$가 $k$비트라면, 이 문제는 크기 $O(k m^2 + nm)$의 불리언 Circuit으로 풀 수 있습니다. 이것은 전혀 자명하지 않습니다. 해결책은 먼저 $N^K$를 계산한 다음 나머지를 구하는 것이 아닙니다. 그렇게 하면 단지 $N^K$라는 수를 저장하는 데만 지수적으로 많은 비트가 필요하게 됩니다. 대신, 거듭제곱 알고리즘(이진 방법 또는 반복 제곱법이라고도 알려진)을 사용할 수 있는데, 이는 $K$의 이진 표현을 이용하여 $M$에 대한 모듈로 전체 계산을 수행합니다. $N,$ $M,$ $K$가 모두 $n$비트 수라고 가정하면, $O(n^3)$ 알고리즘, 즉 삼차(cubic) 시간 알고리즘을 얻습니다. 그리고 다시, 더 복잡하지만 점근적으로 더 빠른 알고리즘들이 알려져 있습니다.

정수 인수분해의 비용

방금 논의한 알고리즘들과 대조적으로, 정수 인수분해를 위한 알려진 알고리즘들은 훨씬 더 비용이 많이 듭니다. 이는 강의 앞부분의 논의에서 예상할 수 있는 바와 같습니다.

인수분해의 한 가지 단순한 접근 방법은 *시험 나눗셈(trial division)*으로, 알고리즘이 입력 수 $N$의 소인수를 찾기 위해 $2,\ldots,\sqrt{N}$ 목록을 탐색합니다. 이는 $N$이 $n$비트 수일 때 최악의 경우 $O(2^{n/2})$번의 반복이 필요합니다. 각 반복은 시험 나눗셈을 필요로 하는데, 이는 각 반복당 $O(n^2)$개의 기본 연산이 필요합니다(정수 나눗셈의 표준 알고리즘 사용). 결국 크기 $O(n^2 2^{n/2})$의 Circuit이 만들어지는데, 이는 입력 크기 $n$에 대해 지수적입니다.

정수 인수분해를 위해 더 나은 확장성을 가진 알고리즘들이 있습니다. 앞서 언급한 수체 체(number field sieve)는 예를 들어 무작위성을 활용하는 알고리즘으로, 일반적으로 (엄밀히 증명된 것은 아니지만) 높은 확률로 $n$비트 정수를 인수분해하는 데

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

개의 기본 연산이 필요하다고 여겨집니다. 이 표현의 지수에서 $n$이 $1/3$ 거듭제곱으로 올라가는 것은 상당히 중요하지만, 지수에 나타난다는 사실 자체는 여전히 좋지 않은 확장성을 야기하는 문제이며, RSA1024가 여전히 적용 가능한 범위 밖에 있는 이유를 부분적으로 설명합니다.

다항 비용 대 지수 비용

정수 덧셈, 곱셈, 나눗셈, 그리고 최대공약수 계산을 위한 고전 알고리즘들은 수천 비트의 입력에 대해 눈 깜짝할 사이에 이러한 문제들을 풀 수 있게 해줍니다. 덧셈은 선형 비용을 가지는 반면, 나머지 세 문제는 이차(quadratic) 비용(또는 점근적으로 빠른 알고리즘을 사용하면 준이차(subquadratic) 비용)을 가집니다. 모듈식 거듭제곱은 더 비용이 많이 들지만 삼차(cubic) 비용(또는 점근적으로 빠른 알고리즘을 사용하면 준삼차 비용)으로 여전히 상당히 효율적으로 수행할 수 있습니다.

이것들은 모두 다항(polynomial) 비용을 가진 알고리즘의 예시로, 어떤 고정 상수 $c > 0$에 대해 비용이 $O(n^c)$임을 의미합니다. 대략적인 첫 번째 근사로, 다항 비용을 가진 알고리즘들은 추상적으로 효율적인 알고리즘을 나타내는 것으로 여겨집니다.

반면에, 알려진 고전 정수 인수분해 알고리즘들은 지수(exponential) 비용을 가집니다. 수체 체의 비용은 때때로 *준지수(sub-exponential)*로 설명되는데, 지수에서 $n$이 $1/3$ 거듭제곱으로 올라가기 때문입니다. 하지만 복잡도 이론에서는 이 용어를 보통 비용이

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

인 모든 $\varepsilon > 0$에 대한 알고리즘에 예약해 둡니다. 소위 NP-완전(NP-complete) 문제들은 다항 비용 알고리즘을 가지지 않는 것으로 알려진(그리고 광범위하게 추측되는) 문제들의 클래스입니다. *지수 시간 가설(exponential-time hypothesis)*의 Circuit 기반 형식화는 더 강한 것을 가정하는데, 어떤 NP-완전 문제도 준지수 비용 알고리즘을 가질 수 없다는 것입니다.

다항 비용 알고리즘을 효율적인 알고리즘과 연관 짓는 것은 느슨한 추상화로 이해해야 합니다. 물론, 알고리즘의 비용이 크기 $n$의 입력에 대해 $n^{1000}$ 또는 $n^{1000000}$으로 확장된다면, 그 알고리즘을 효율적이라고 설명하는 것은 무리가 있습니다. 그러나 $n^{1000000}$으로 비용이 확장되는 알고리즘조차도 지수적 비용을 피하기 위해 무언가 영리한 것을 하고 있는 것인데, 이는 일반적으로 어떤 방식으로든 "무차별 대입(brute force)" 또는 "완전 탐색(exhaustive search)"에 기반한 알고리즘에서 기대되는 것입니다. 예를 들어, 수체 체의 정교한 개선조차도 비용에서 이 지수적 확장을 피하지 못합니다. 반면에 다항 비용 알고리즘들은 지수적 확장을 피하는 방식으로 문제 구조를 어떤 방식으로든 활용합니다.

실제로, 어떤 문제에 대한 다항 비용 알고리즘의 식별은 실제 효율성을 향한 첫 번째 단계에 불과합니다. 알고리즘 개선을 통해 큰 지수를 가진 다항 비용 알고리즘이 때로는 극적으로 개선되어 더 "합리적인" 다항 확장으로 비용이 낮아질 수 있습니다. 가능하다고 알려진 경우 일이 더 쉬워지는 경우도 있습니다. 따라서 어떤 문제에 대한 다항 비용 알고리즘의 식별이 새롭고 훨씬 더 효율적인 알고리즘에 영감을 줄 수 있는 효과도 있습니다.

양자 컴퓨팅이 고전 컴퓨팅에 비해 가지는 이점을 고려할 때, 우리는 일반적으로 지수적 이점 또는 최소한 초다항(super-polynomial) 이점을 먼저 주목합니다. 이상적으로는 다항 비용의 고전 알고리즘을 가지지 않는 것으로 알려진 문제에 대한 다항 비용의 양자 알고리즘을 찾는 것입니다. 이러한 수준의 이론적 이점은 실제 실용적 이점으로 이어질 가능성이 가장 높습니다. 그러나 그러한 이점을 식별하는 것은 극도로 어려운 도전입니다. 현재 알려진 예시는 몇 가지뿐이지만, 탐색은 계속됩니다.

다항적이지만 초다항적이지 않은 양자 대 고전 계산 비용의 이점도 흥미롭고 무시해서는 안 됩니다. 그러나 현재 양자 컴퓨팅과 고전 컴퓨팅 기술의 격차를 고려할 때, 현재 시점에서는 다소 덜 설득력 있어 보입니다. 하지만 언젠가는 중요해질 수 있습니다. 예를 들어, *그로버 알고리즘(Grover's algorithm)*은 이후 강의에서 다루어지는데, 소위 *비구조적 탐색(unstructured searching)*에 대해 양자가 고전보다 이차적(quadratic) 이점을 제공하며, 광범위한 응용 가능성이 있습니다.

Circuit 계산의 숨겨진 비용

이 과정에서는 더 이상 다루지 않겠지만, 언급할 가치가 있는 마지막 문제가 있습니다. Circuit으로 작업할 때 "숨겨진" 계산 비용이 있는데, 이는 Circuit 자체의 명세와 관련됩니다. 입력이 점점 길어질수록 점점 더 큰 Circuit이 필요합니다. 그러나 이를 구현하려면 어떻게든 이러한 Circuit의 설명을 손에 넣어야 합니다.

우리가 논의했거나 이후 강의에서 논의할 모든 예시에는 Circuit이 도출되는 기저 알고리즘이 있습니다. 보통 패밀리 내의 Circuit들은 덧셈을 위한 불리언 Circuit을 만들기 위해 전가산기를 연결하거나 하다마르 Gate와 다른 Gate들을 간단히 설명할 수 있는 패턴으로 계층화하는 것과 같이 더 큰 입력으로 쉽게 확장할 수 있는 기본 패턴을 따릅니다.

하지만 Circuit 자체의 패턴과 관련된 금지적인 계산 비용이 있다면 어떻게 될까요? 예를 들어, Circuit 패밀리의 각 구성원 $C_n$의 설명이 원칙적으로 계산하기 매우 어려운 $n$의 함수에 의해 결정될 수 있습니다.

대답은 이것이 실제로 문제가 된다는 것입니다. 따라서 Circuit 패밀리가 진정으로 효율적인 알고리즘을 표현하려면 다항 비용을 갖는 것 외에도 추가적인 제약을 둬야 합니다. Circuit의 균일성(uniformity) 속성은 다양한 정확한 형식화에서 패밀리의 각 Circuit 설명을 계산적으로 쉽게 얻을 수 있어야 한다고 규정함으로써 이를 수행합니다. 우리가 논의할 모든 Circuit 패밀리는 이 속성을 가지고 있습니다. 그러나 이것은 공식적인 관점에서 Circuit 계산 모델을 연구할 때 일반적으로 알고 있어야 할 중요한 문제입니다.