BQP는 Bounded-error Quantum Polynomial time(제한오차 양자 다항시간)의 약자로, 계산 복잡도 이론에서 정의된 복잡도 종류(complexity class)이다. 양자 컴퓨터가 다항 시간 내에 해결할 수 있는 판정 문제(decision problem)들의 집합을 나타내며, 오차 확률은 모든 입력 인스턴스에 대해 최대 1/3로 제한된다. BQP는 고전적 확률적 튜링 기계의 복잡도 종류인 BPP(Bounded-error Probabilistic Polynomial time)에 대응하는 양자적 개념이다.
정의
언어 $L$이 BQP에 속한다는 것은, 다음 조건을 만족하는 다항 시간 균일(uniform) 양자 회로군 ${Q_n : n \in \mathbb{N}}$이 존재함을 의미한다:
- 각 $Q_n$은 $n$개의 큐비트를 입력으로 받아 1비트를 출력한다.
- 모든 $x \in L$에 대해, $\Pr(Q_{|x|}(x)=1) \geq \frac{2}{3}$이다.
- 모든 $x otin L$에 대해, $\Pr(Q_{|x|}(x)=0) \geq \frac{2}{3}$이다.
오차 한계 1/3은 임의적이며, 알고리즘을 상수 번 반복하고 다수결 투표를 통해 원하는 정확도(1 미만)로 높일 수 있다. 체르노프 부등식(Chernoff bound)에 의해 가능하다.
다른 복잡도 종류와의 관계
BQP와 다른 복잡도 종류 간의 포함 관계는 다음과 같이 알려져 있다:
$$ \mathsf{P \subseteq BPP \subseteq BQP \subseteq AWPP \subseteq PP \subseteq PSPACE \subseteq EXP} $$
- P와 BPP를 포함한다: 모든 고전적 회로는 양자 회로로 시뮬레이션 가능하므로 $\mathsf{P \subseteq BQP}$이며, $\mathsf{BPP \subseteq BQP}$ 또한 성립한다.
- PSPACE에 포함된다: BQP는 PSPACE의 부분집합으로 알려져 있다. 이는 파인만의 역사합(sum of histories) 접근법을 통해 증명된다.
- NP와의 관계: BQP와 NP의 관계는 아직 밝혀지지 않은 컴퓨터 과학의 미해결 문제이다. 소인수분해(쇼어 알고리즘)와 이산로그 문제는 BQP에 속하는 것으로 알려져 있지만, 이들이 NP-완전인지는 알려져 있지 않다.
- PH(다항 계층)와의 관계: 2018년 Ran Raz와 Avishay Tal은 오라클 상에서 BQP가 PH에 포함되지 않음을 증명하였으나, 오라클 분리(oracle separation)는 실제 복잡도 종류 간의 관계를 결정하지는 않는다.
주요 응용
BQP에 속하는 것으로 알려진 구체적인 문제들은 다음과 같다:
- 정수 소인수분해: 쇼어 알고리즘(Shor's algorithm)에 의해 다항 시간에 해결 가능하다.
- 이산로그 문제: 쇼어 알고리즘의 변형으로 해결 가능하다.
- 양자계 시뮬레이션: 양자 시스템의 효율적인 시뮬레이션.
- 존스 다항식 근사: 특정 근처에서의 존스 다항식 근사 계산.
- HHL 알고리즘: 선형 방정식 시스템의 해를 구하는 양자 알고리즘.
역사
BQP는 1993년 Ethan Bernstein과 Umesh Vazirani가 양자 컴퓨터의 계산 능력을 이론적으로 정립하는 과정에서 처음 정의하였다. 이후 1994년 Peter Shor의 소인수분해 알고리즘은 BQP가 고전적 컴퓨터보다 강력할 수 있다는 결정적 증거를 제시하였다.
미해결 문제
BQP에 관한 가장 중요한 미해결 문제는 다음과 같다:
- $\mathsf{BQP \stackrel{?}{=} NP}$ — 양자 컴퓨터가 NP 문제를 효율적으로 풀 수 있는지 여부.
- $\mathsf{BQP \stackrel{?}{=} BPP}$ — 양자 컴퓨터가 고전적 확률적 컴퓨터보다 본질적으로 더 강력한지 여부.
- $\mathsf{BQP \stackrel{?}{=} PSPACE}$ — BQP가 PSPACE와 동일한지 여부.
이 중 어느 것도 아직 증명되지 않았으며, 이들은 계산 복잡도 이론의 핵심 미해결 문제들 중 하나이다.
참고 문헌
- Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 0-521-63503-9.
- Bernstein, Ethan; Vazirani, Umesh (1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473.
- Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482.
