Quantum Algorithm 2 - Complexity

Before starting

이 시리즈는 양자 알고리즘을 다루고 있지만 양자역학을 다루진 않는다. 양자 알고리즘을 이해하는 데에 있어 필요한 최소한의 선수지식을 철저히 내 시선에서 이해한 대로 작성하는 연재글이니 참고할 것.

Definition

일반적으로 양자 컴퓨터에는 기존에 존재하는 모든 NP 문제를 다항시간 안에 해결해줄 것이라는 환상이 있다. 정말 그럴까?
양자 알고리즘으로 해결되는 문제의 복잡도 분류를 알아보고, 이를 고전 알고리즘에서의 복잡도 분류와 비교해보자.

양자 알고리즘에서는 크게 BQP와 QMA라는 두 가지 분류가 존재한다.

BQP(Bounded-error Quantum Polynomial time)는 양자 컴퓨터가 다항식 시간 내에 최대 $k$의 확률로 잘못된 답을 제시하는 문제들의 집합을 뜻한다. 이 오답률 $k$는 $0 < k < \dfrac{1}{2}$를 만족하기만 하면 어느 값이든 상관은 없으나 보통 $\dfrac{1}{3}$으로 생각한다. 이에 대응되는 고전 알고리즘에서의 복잡도 분류는 BPP이다.
그런데 이 BPP라는 용어는 좀 생소하다. BPP(Bounded-error Probabilistic Polynomial time)는 컴퓨터가 다항식 시간 내에 최대 $k$의 확률로 잘못된 답을 제시하는 문제들의 집합을 뜻한다. BQP와 마찬가지로 이 오답률 $k$는 $0 < k < \dfrac{1}{2}$를 만족하기만 하면 어느 값이든 상관은 없으나 보통 $\frac{1}{3}$으로 생각한다. 흔히 알고 있는 P와는 비슷하지만 확률적인 오답률이 추가된, 완화된 P 문제이다. 일반적으로 난수를 사용하는 튜링 기계가 여기에 속하며, $P=BPP$인지는 아직 밝혀지진 않았다. (당연하지만 $P \subseteq BPP$이다.)
P에 대응되는 양자 알고리즘의 분류는 EQP이다. EQP(Exact Quantum Polynomial time)는 양자 컴퓨터가 다항식 시간 내에 반드시 답을 구할 수 있는 문제들의 집합을 뜻한다. 엄밀하게 따지면 이 EQP가 P에 대응되지만, 양자 알고리즘의 특성상 100%의 확률로 해결되는 문제를 정의할 수 없다. 추후에 실제 양자 알고리즘을 살펴보면 알게 되겠지만, 대부분의 양자 알고리즘은 확률적 알고리즘이며 이 확률을 최대한 높이는 방향으로 설계된다. 따라서 BPP 대신 P를 주로 다루는 고전 알고리즘과 다르게 양자 알고리즘에서는 EQP 대신 BQP를 주로 다룬다. 그러면 양자 알고리즘은 본질적으로 오답을 출력할 위험성을 내포하는게 아니냐 싶지만, 다행스럽게도 Solovay-Kitaev theorem에 의해 정답에 한없이 근사시킬 수 있다. 보다 구체적으로는, qubit 1개를 임의의 정확도 $\epsilon$으로 근사시킬 때 약 $O(log^{c}\dfrac{1}{\epsilon})$ 개의 Gate가 필요하며 이는 실제 상황에서도 충분히 활용할 수 있는 복잡도이다.

QMA(Quantum Merlin Arthur)는 양자 컴퓨터가 다항식 시간 내에 검증할 수 있는 문제들의 집합을 뜻한다. 고전 알고리즘의 NP와 비슷한 분류로, 실제로 NP와 비슷하게 QMA는 다시 QMA-Hard와 QMA-Complete로 나눌 수 있다. 그 정의마저도 NP-Hard, NP-Complete와 동일하다. 즉, 모든 QMA 문제를 양자 컴퓨터가 다항식 시간 내에 A 문제로 reduce/transform 할 수 있는 경우 그 A 문제를 QMA-Hard라고 하며, QMA이자 QMA-Hard인 문제를 QMA-Complete라고 한다.

Comparison

그럼 이제 P/NP와 BQP/QMA 간의 관계를 생각해보자. 일단 명확히 해야 할 점은, 위의 네 집합 간의 관계는 아직 아무것도 증명되진 않았다. 다만 지금 시점에서 확실히 밝혀진 정보들, 그리고 이를 바탕으로 대부분의 사람들이 추측하는 관계를 정리해보면 다음과 같다.

• $P \subseteq NP, $P \subseteq BQP$
  즉, BQP에 속하지만 P문제는 아닌 문제가 존재하며 (대표적으로 Shor’s algorithm), NP-Complete와 BQP는 아직 서로의 관계를 확실히 알 수 없는 관계이다. 그러나 NP이면서 BQP가 아닌 문제, 그리고 BQP가 아니면서 NP인 문제로 추측되는 문제들이 존재하므로, 이 둘은 교집합은 존재하나 어느 쪽도 상대방을 포함하는 관계는 아닐 것으로 예상된다. 즉, 세간의 믿음과는 다르게 NP-Complete 문제는 양자 컴퓨터를 이용하더라도 여전히 다항 시간 안에 해결하긴 어려울 것으로 보인다.
• $NP \subseteq QMA \subseteq PSPACE$
  그렇다면 QMA는 어떨까? QMA는 기존의 NP가 아닌 PSPACE와 비교한다. PSPACE(Polynomial SPACE)는 고전 컴퓨터가 시간은 얼마든지 쓸 수 있되 다항 공간만 써서 풀 수 있는 문제들의 집합을 뜻한다. 그리고 현재까지는 MQA는 PSPACE의 부분집합이라고 추측되고 있다.

즉, 이상의 관계를 정리해보면 양자 알고리즘은 기존 NP 문제들을 전부 다항 시간 안에 해결해주는 만능의 도구는 아니라는 것을 알 수 있다. 하지만 NP 문제들 중 일부를 다항 시간 안에 풀 수 있음이 증명되었고, 그 중 하나가 하필이면 소인수분해를 다루는 Shor’s algorithm이라는 점에서, 그리고 앞으로 또 어떤 양자 알고리즘이 개발될지 알 수 없다는 점에서 잠재력은 무궁무진한 것 같다.