[양자정보과학] BQP란?

금일은 BQP에 대해 알아보는 시간을 갖도록 하겠습니다.

BQP는 계산 복잡도 이론 용어로 '유계오차 양자 다항시간'(有界誤差 量子 多項時間, Bounded error, Quantum, Polynomial time)의 약자입니다. 

BQP의 정의는 무엇일까요?

BQP란 모든 풀이에 대해 최대 1/4의 확률로 잘못된 결과를 내놓으면서 양자 컴퓨터가 다항시간 안에 풀 수 있는 문제의 집합이라고 할수 있습니다. 

우리는, 양자컴퓨터에서 다항시간의 실행시간을 가지는 알고리즘의 집합으로 생각할 수 있습니다. 1/4이라는 확률로 잘못된다는 것은 '예'라는 답을 잘못 내놓는 경우와 '아니오'라는 답을 잘못 내놓는 경우 모두를 포함한 것입니다.

사실, BQP에서 확률을 1/4로 제한하는 데 특별한 의미가 있는 것은 아닙니다. 이 상수를 0 < k < 1/2 인 임의의 실수 k로 바꾸어도 BQP 집합이 변하는 것은 아닙니다. 어느 정도 잘못된 결과가 나올 확률이 있어도, 알고리즘을 여러 번 시행하면 잘못된 결과가 많이 나올 확률이 기하급수적으로 감소하기 때문입니다.

컴퓨터의 큐비트 수는 보통 입력값의 크기에 대한 함수 값을 가집니다. 예를 들어, 2n개의 큐비트로 n비트 정수를 소인수 분해하는 알고리즘이 알려져 있습니다.

실용적으로 널리 사용되는 문제의 일부가 P에는 속하지 않을 것 같지만 BQP에 속한다는 것이 알려지면서, 최근 양자컴퓨터에 대해 관심이 높아지고 있습니다. P에는 속하지 않을 것 같지만 BQP에 속하는 문제 중 현재까지 알려진 것은 다음 세 가지밖에 없습니다.

소인수 분해란?

소인수분해(영어: prime factorization, integer factorization)는 합성수를 소수의 곱으로 나타내는 방법을 말합니다.

소인수분해를 일의적으로 결정하는 방법은 아쉽게도 아직 발견되지 않았습니다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 됩니다.

이산 대수란?

이산 로그(離散--, discrete logarithm)는 일반 로그와 비슷하게 군론에서 정의된 연산으로, 를 만족하는 를 가리킵니다. 이산 대수(離散對數)라고 부르기도 합니다.

이산 로그의 정의

이산 로그의 가장 단순한 형태는 Z_p^*에서 정의하는 것이다. Z_p^*의 집합은 {1, …, p − 1}이고 소수 p를 법으로 가지는 모듈로 곱셈에 대하여 닫혀있다. 이 군에서 어떤 수의 k 제곱을 구하려면, 그 수를 k번 제곱한 다음 p로 나눈 나머지를 구하면 된다. 이런 연산을 이산 거듭제곱(discrete exponentiation)이라고 한다. 예를 들어, Z₇^*에서 3의 5제곱을 구하는 경우, 3⁵=243 이고 243을 7로 나눈 나머지가 5이므로 Z₇^*에서 3⁵=5이다. 이산 로그는 이산 거듭제곱의 역함수이다. 앞의 예제를 사용하여 설명하면, 3^k ≡ 5 (mod 7)일 때 이 조건을 만족시키는 가장 작은 k가 Z₇^*에서 밑이 3인 5의 이산 로그값이다. 이산로그문제(discrete logarithm problem)라고도 한다. 이산 로그의 정의를 일반화하면 다음과 같다. G가 n개의 원소를 가진 유한 순환군이라고 하자. 이 군은 곱셈군이라고 가정한다. b가 G의 생성원(primitive root, primitive element)이면 G의 모든 원소 x는 임의의 정수 k에 대하여 x = b^k의 형태로 쓸 수 있다. 또한 x를 표현하는 모든 원소들은 모듈로 n에 대해 합동이다. 이런 조건에서 다음과 같은 함수를 정의한다.

$${\displaystyle \log _{b}:\ G\ \rightarrow \ \mathbf {Z} _{n}}

여기서 Z_n은 정수 n을 법으로 가지는 환이고 x에는 모듈로 n에 대한 congruence class를 할당한다. 이와 같은 군 동형사상을 밑이 b인 이산 로그라고 부른다.

로그 함수의 밑변환은 이산 로그에서도 그대로 적용된다. c가 G의 또다른 생성원이면, 다음 식이 성립한다.

$${\displaystyle \log _{c}(x)=\log _{c}(b)\cdot \log _{b}(x).}

양자체계의 시뮬레이션 (범용 양자)

BQP는 양자 컴퓨터를 위해 정의된 복잡도 종류입니다. 일반적인 튜링 기계에서 확률적으로 시행되는 알고리즘의 집합은 BPP입니다.