BQP

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

BQP(Bounded-error Quantum Polynomial time)는 양자 컴퓨터를 사용하여 정의되는 계산 복잡도 클래스이다. BQP는 유계 오차를 갖는 균일 양자 회로군 또는 양자 튜링 기계를 사용하여 정의할 수 있으며, P와 BPP를 포함하고 PP, PSPACE에 포함된다. BQP는 PP에 낮음이며, NP와의 관계는 알려져 있지 않지만, BQP가 PH에 포함되지 않는다는 것을 시사하는 결과가 제시되고 있다. APPROX-QCIRCUIT-PROB 문제는 BQP에 완전하며, BQP는 P를 포함한다. BQP가 P 외부에 있는 어려운 문제, 특히 NP에 속하는 문제를 해결할 수 있을 것으로 추정된다.

BQP

📚 더 읽어볼만한 페이지

확률적 복잡도 종류 - RP (복잡도)
RP 복잡도 클래스는 확률적 튜링 기계가 언어에 속하는 입력에 대해 1을 출력할 확률이 1/2 이상이고, 속하지 않는 입력에 대해서는 항상 0을 출력하는 문제들의 집합으로, BPP, ZPP, co-RP와 관련되며 P-NP 문제와 연관성을 갖는 다항식 항등식 검사 문제의 예시를 포함한다.
확률적 복잡도 종류 - BPP (복잡도)
BPP는 다항 시간 내에 특정 확률 조건으로 실행되는 확률적 튜링 기계로 정의되는 복잡도 종류로, 여집합, 합집합, 교집합에 대해 닫혀 있으며 다른 복잡도 종류와 다양한 관계를 가진다.
양자 컴퓨터 - 큐비트
양자 컴퓨터 - 데이비드 도이치
이스라엘 태생의 영국 물리학자 데이비드 도이치는 양자 컴퓨팅 이론의 선구자로서 양자 알고리즘 연구와 도이치-조자 알고리즘 개발에 기여했으며, 생성자 이론 연구와 과학적 설명 기준으로 불변량 제시 등의 업적을 남겼다.
양자정보과학 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
양자정보과학 - 벨 부등식
벨 부등식은 양자역학과 국소적 숨은 변수 이론의 모순을 보이는 부등식으로, 실험 결과는 벨 부등식의 위반을 통해 양자역학의 비국소성을 시사하며 양자 정보 과학에 중요한 함의를 가진다.

1. 개요
2. 정의
3. 다른 복잡도 클래스와의 관계
4. Promise-BQP의 완전 문제
- 4.1. APPROX-QCIRCUIT-PROB로의 환산
5. BQP와 EXP, PSPACE, PP의 관계
6. P, BQP, 그리고 NP
7. 양자 정보 및 복잡성 이론

2. 정의

BQP는 특정 유계 오차 균일 계열의 양자 회로와 관련된 언어로 볼 수 있다. 언어 L이 BQP에 속하려면 다음과 같은 조건을 만족하는 다항 시간 균일 양자 회로 계열 $\{Q_n\colon n \in \mathbb{N}\}$ 이 존재해야 한다.

* 모든 $n \in \mathbb{N}$ 에 대해, Q_n은 n개의 큐비트를 입력으로 받아 1 비트를 출력한다.
* L에 있는 모든 x에 대해, $\mathrm{Pr}(Q_$

👆

좌우로 밀어서 보기

(x)=1)\geq \tfrac{2}{3}
* L에 없는 모든 x에 대해,

\mathrm{Pr}(Q_

👆

좌우로 밀어서 보기

(x)=0)\geq \tfrac{2}{3}

또는, BQP를 양자 튜링 기계를 사용하여 정의할 수 있다. 언어 L이 BQP에 속하려면, 모든 인스턴스에 대해 1/3 이하의 오류 확률로 L을 수락하는 다항식 양자 튜링 기계가 존재해야 한다.

다른 "유계 오차" 확률적 클래스와 유사하게, 정의에서 1/3의 선택은 임의적이다. 알고리즘을 상수 번 실행하고 과반수 투표를 통해 체르노프 경계를 사용하여 1 미만의 원하는 정확도 확률을 얻을 수 있다. 복잡도 클래스는 한편으로는 1/2 − n^−c만큼 높은 오류를 허용하거나, 다른 한편으로는 2^{−n^c}만큼 작은 오류를 요구함으로써 변경되지 않으며, 여기서 c는 임의의 양의 상수이고, n은 입력의 길이이다.

3. 다른 복잡도 클래스와의 관계

BQP는 양자 컴퓨터를 위해 정의된 복잡도 클래스이다. 고전 컴퓨터(확률적 튜링 기계)에 해당하는 복잡도 클래스는 BPP이다. BQP는 P와 BPP를 포함하고, AWPP, PP, PSPACE에 포함된다.

BQP는 PP에 대해 낮음이며, 이는 PP 머신이 BQP 문제를 즉시 해결할 수 있더라도 추가적인 이점을 얻지 못한다는 것을 의미한다. 고전적인 복잡도 클래스와의 알려진 관계는 다음과 같다.

: $\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE\subseteq EXP}$

문제가 아직 해결되지 않았으므로, BQP와 위에 언급된 클래스 간의 부등식을 증명하는 것은 어려울 것으로 예상된다. BQP와 NP의 관계는 알려져 있지 않다. 2018년 5월, 프린스턴 대학교의 컴퓨터 과학자 란 라즈와 스탠포드 대학교의 아비샤이 탈은 오라클과 관련하여 BQP가 PH에 포함되지 않는다는 논문을 발표했다. $\mathsf{BQP}^\mathrm{A}\nsubseteq\mathsf{PH}^\mathrm{A}$ 가 되도록 오라클 A가 존재함을 증명할 수 있다.

푸리에 샘플링이 BQP 내에 존재하지만 다항 시간 계층 내에는 존재하지 않는 문제라는 것이 오랫동안 의심되어 왔으며, 최근에는 푸리에 검사가 다항 시간 계층에 포함되지 않으면서도 BQP 클래스에 존재한다는 증거를 제공했다.

사후 선택을 추가하면 PostBQP 복잡도 클래스가 생성되며, 이는 PP와 같다.

4. Promise-BQP의 완전 문제

Promise-BQP는 균일한 양자 회로군(즉, BQP 내)에 의해 해결될 수 있는 약속 문제의 부류이다. NP-완전 및 다른 완전 문제의 개념과 유사하게, Promise-BQP에 속하며 Promise-BQP의 다른 모든 문제가 다항 시간 내에 이 문제로 축소될 수 있는 문제를 완전 문제로 정의할 수 있다.

APPROX-QCIRCUIT-PROB 문제는 효율적인 양자 계산에 완전하며, Promise-BQP 복잡도 클래스에 대해 완전하다. (총 BQP 복잡도 클래스에 대해서는 완전한 문제가 알려져 있지 않다.) APPROX-QCIRCUIT-PROB의 완전성은 다른 복잡도 클래스와 BQP 간의 관계를 보여주는 증명에 유용하다.

APPROX-QCIRCUIT-PROB 문제는 다음과 같이 정의된다.

* 양자 회로 $C$ 가 $n$ 개의 큐비트에 작용하고 $m$ 개의 게이트를 가지며, 여기서 $m$ 은 $n$ 에 대한 다항식이고 각 게이트는 하나 또는 두 개의 큐비트에 작용한다.
* 두 숫자 $\alpha, \beta \in [0,1], \alpha > \beta$ 가 주어졌을 때, 다음 두 가지 경우를 구분한다.
* 상태 $C|0\rangle^{\otimes n}$ 의 첫 번째 큐비트를 측정하면 $|1\rangle$ 이 $\geq \alpha$ 의 확률로 나타난다.
* 상태 $C|0\rangle^{\otimes n}$ 의 첫 번째 큐비트를 측정하면 $|1\rangle$ 이 $\leq \beta$ 의 확률로 나타난다.

여기서는 인스턴스가 이 두 가지 경우에 해당하지 않는 경우의 동작을 문제에서 지정하지 않으므로 입력에 대한 약속이 있다.

모든 BQP 문제는 APPROX-QCIRCUIT-PROB로 축소 가능하다.

4.1. APPROX-QCIRCUIT-PROB로의 환산

모든 BQP 문제는 APPROX-QCIRCUIT-PROB 문제로 환산될 수 있다는 주장에 대한 증명은 다음과 같다.

APPROX-QCIRCUIT-PROB를 해결하는 알고리즘 A가 있다고 가정한다. 이 알고리즘은 n개의 큐비트에 작용하는 양자 회로 C와 두 숫자 $\alpha, \beta \in [0,1], \alpha > \beta$ 가 주어졌을 때, 다음 두 가지 경우를 구분한다.

* 상태 $C|0\rangle^{\otimes n}$ 의 첫 번째 큐비트를 측정하면 $|1\rangle$ 이 $\geq \alpha$ 의 확률로 나타난다.
* 상태 $C|0\rangle^{\otimes n}$ 의 첫 번째 큐비트를 측정하면 $|1\rangle$ 이 $\leq \beta$ 의 확률로 나타난다.

$\alpha = 2/3, \beta = 1/3$ 으로 설정하여 이 알고리즘 A를 오라클로 사용하여 BQP의 모든 문제를 해결할 수 있다.

모든 $L \in \mathsf{BQP}$ 에 대해, 다음을 만족하는 양자 회로 집합 $\{Q_n\colon n \in \mathbb{N}\}$ 이 존재한다.

* 모든 $n \in \mathbb{N}$ 에 대해 상태 $|x\rangle$ 는 $n$ 개의 큐비트이다.
* $x \in L$ 이면 $Pr(Q_n(|x\rangle)=1) \geq 2/3$ 이다.
* $x \notin L$ 이면 $Pr(Q_n(|x\rangle)=0) \geq 2/3$ 이다.

입력 $|x\rangle$ 가 n개의 큐비트이고, 해당 양자 회로 $Q_n$ 을 고정한다. $C_x|0\rangle^{\otimes n} = |x\rangle$ 인 회로 $C_x$ 를 구성할 수 있는데, 이는 $|x\rangle$ 를 하드와이어링하고 CNOT 게이트 시퀀스를 적용하여 큐비트를 뒤집으면 쉽게 수행할 수 있다. 그런 다음 두 회로를 결합하여 $C' = Q_nC_x$ 를 얻을 수 있으며, $C'|0\rangle^{\otimes n} = Q_n|x\rangle$ 가 된다.

$Q_n$ 의 결과는 여러 큐비트를 측정하고 일부 (고전적인) 논리 게이트를 적용하여 얻어야 한다. 항상 측정을 지연시키고 회로를 재라우팅하여 $C'|0\rangle^{\otimes n} = Q_n|x\rangle$ 의 첫 번째 큐비트를 측정하여 출력을 얻을 수 있다. 이것이 회로 C가 되고, $A(C)$ 를 $\alpha = 2/3, \beta = 1/3$ 으로 실행하여 $x \in L$ 의 멤버십을 결정한다.

BQP의 정의에 따라, 첫 번째 경우(수락) 또는 두 번째 경우(거부) 중 하나에 속하게 되므로, $L \in \mathsf{BQP}$ 는 APPROX-QCIRCUIT-PROB로 환산된다.

5. BQP와 EXP, PSPACE, PP의 관계

BQP는 P와 BPP를 포함하고, PP와 PSPACE에 포함된다. 알려진 관계는 다음과 같다.

: $\mathsf{P \subseteq BPP \subseteq BQP\subseteq PP \subseteq PSPACE\subseteq EXP}$

$\mathsf{BQP} \subseteq \mathsf{EXP}$ 임을 보이기 위해, APPROX-QCIRCUIT-PROB가 BQP-완전성이므로 APPROX-QCIRCUIT-PROB가 EXP에 속함을 보이는 것으로 충분하다.

이 알고리즘은 벡터와 행렬을 저장하기 위해 $2^{O(n)}$ 공간을 필요로 한다. 역사 합(sum-over-histories) 기법을 통해 공간 복잡성을 개선할 수 있다. $\mathsf{BQP} \subseteq \mathsf{PSPACE}$ 임을 보이기 위해 역사 합 기법으로 APPROX-QCIRCUIT-PROB를 공식화할 수 있다.

양자 회로(quantum circuit)를 고려해 보자. 이 회로는 m개의 게이트

g_1, g_2, \cdots, g_m

으로 구성되어 있으며, 각

g_j

는 보편 게이트 집합에서 가져오고 최대 두 개의 큐비트에 작용한다.

양자 회로가 주어졌을 때 양자 상태의 진화를 트리로 시각화한다. 루트는 입력

|0\rangle^{\otimes n}

이고, 트리의 각 노드는

2^n

개의 자식을 가지며, 각 자식은

\mathbb C^n

의 상태를 나타낸다. 트리 에지의 가중치는 j번째 레벨의 노드가 상태

|x\rangle

를 나타내고,

j+1

번째 레벨의 노드가 상태

|y\rangle

를 나타낼 때,

\langle y|g_{j+1}|x\rangle

인데, 이는

g_{j+1}

를

|x\rangle

에 적용한 후의

|y\rangle

의 진폭이다. 루트에서 잎으로 가는 경로의 전이 진폭은 경로를 따라 있는 모든 에지의 가중치의 곱이다. 최종 상태가

|\psi\rangle

일 확률을 구하기 위해,

|\psi\rangle

를 나타내는 노드에서 끝나는 모든 루트에서 잎으로 가는 경로의 진폭을 더한다.

더 공식적으로, 양자 회로 C에 대해, 역사 합 트리는 깊이가 m인 트리이며, 루트 외에 각 게이트

g_i

에 대한 한 레벨과 분기 계수

2^n

을 갖는다.

역사 합 알고리즘에서 어떤 진폭

\alpha_x

를 계산하기 위해, 계산의 어떤 시점에서도 하나의 역사만 저장된다. 따라서, 역사 합 알고리즘은 어떤 x에 대해

\alpha_x

를 계산하기 위해

O(nm)

의 공간을 사용하는데, 이는 작업 공간 변수 외에 역사들을 저장하는 데

O(nm)

비트가 필요하기 때문이다.

따라서, 다항 공간에서 우리는 첫 번째 큐비트가 1인 모든 x에 대해

\sum_x |\alpha_x|^2

를 계산할 수 있는데, 이는 회로가 종료될 때 첫 번째 큐비트가 1로 측정될 확률이다.

\mathsf{BQP} \subseteq \mathsf{EXP}

임을 증명하기 위해 주어진 시뮬레이션과 비교했을 때, 이 알고리즘은 훨씬 적은 공간을 사용하지만 대신 훨씬 더 많은 시간을 사용한다. 실제로 단일 진폭을 계산하는 데

O(m\cdot 2^{mn} )

시간이 걸린다.

비슷한 역사 합산 논증을 사용하여

\mathsf{BQP} \subseteq \mathsf{PP}

임을 보일 수 있다.

2010년대 즈음부터 BQP와 NP의 관계와 관련하여, NP를 포함하는 PH에 BQP가 포함되지 않는다는 것을 시사하는 결과가 몇몇 제시되고 있다.

6. P, BQP, 그리고 NP

모든 고전 회로는 양자 회로로 시뮬레이션될 수 있으므로 $\mathsf{P \subseteq BQP}$ 이다. BQP가 P 외부에 있는 NP 문제를 해결할 수 있다고 추정되지만, P=NP인지 아직 증명되지 않았으므로 확실하지 않다. BQP가 해결할 수 있다고 추정되는 문제들은 다음과 같다.

* 정수 인수 분해 (쇼어의 알고리즘 참조)
* 이산 로그
* 양자 시스템 시뮬레이션 (범용 양자 시뮬레이터 참조)
* 단위근에서 존스 다항식 근사
* 해로우-하시딤-로이드 (HHL) 알고리즘

7. 양자 정보 및 복잡성 이론

BQP는 양자 정보 과학 및 양자 복잡성 이론에서 중요한 위치를 차지한다.

관련 연구 분야

* 양자 알고리즘: 효율적인 양자 알고리즘 개발은 BQP 문제 해결 능력을 향상시킨다.
* 양자 통신: 양자 통신은 양자 정보를 안전하게 전송하고 처리하는 데 중요한 역할을 한다.
* 양자 암호: 양자 암호는 기존 암호 체계보다 안전한 통신을 가능하게 한다.
* 양자 오류 수정: 양자 오류 수정은 양자 컴퓨터의 안정적인 작동을 보장한다.

양자 컴퓨팅과의 관계

양자 컴퓨팅의 발전은 BQP 문제 해결 능력을 향상시킬 수 있다. 특히, 양자 컴퓨터는 기존 컴퓨터로는 해결하기 어려운 문제를 해결할 수 있는 잠재력을 가지고 있다. 예를 들어, 쇼어의 알고리즘은 양자 컴퓨터를 이용하여 정수 인수 분해 문제를 효율적으로 해결할 수 있음을 보여준다.

BQP와 다른 복잡도 클래스와의 관계

* BQP는 P와 BPP를 포함하며, PP와 PSPACE에 포함된다.
* 구체적인 포함 관계는 다음과 같다.

: $\mbox{P} \subseteq \mbox{BPP} \subseteq \mbox{BQP}\subseteq \mbox{PP} \subseteq \mbox{PSPACE}$
* BQP와 NP의 관계는 아직 명확하게 밝혀지지 않았지만, BQP가 NP를 포함하는 PH에 포함되지 않는다는 것을 시사하는 연구 결과들이 제시되고 있다.