(x)=0)\geq \tfrac{2}{3}양자 튜링 기계 를 사용하여 정의할 수 있다. 언어 ''L''이 '''BQP'''에 속하려면, 모든 인스턴스에 대해 1/3 이하의 오류 확률로 ''L''을 수락하는 다항식 양자 튜링 기계가 존재해야 한다.−''c'' 만큼 높은 오류를 허용하거나, 다른 한편으로는 2−''nc '' 만큼 작은 오류를 요구함으로써 변경되지 않으며, 여기서 ''c''는 임의의 양의 상수이고, ''n''은 입력의 길이이다.
3. 다른 복잡도 클래스와의 관계
BQP는 양자 컴퓨터를 위해 정의된 복잡도 클래스이다. 고전 컴퓨터(확률적 튜링 기계 )에 해당하는 복잡도 클래스는 BPP이다. BQP는 P 와 BPP를 포함하고, AWPP,PSPACE 에 포함된다.\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE\subseteq EXP} NP 의 관계는 알려져 있지 않다. 2018년 5월, 프린스턴 대학교 의 컴퓨터 과학자 란 라즈와 스탠포드 대학교의 아비샤이 탈은 오라클과 관련하여 BQP가 PH에 포함되지 않는다는 논문을 발표했다.\mathsf{BQP}^\mathrm{A}\nsubseteq\mathsf{PH}^\mathrm{A} 가 되도록 오라클 A가 존재함을 증명할 수 있다.
4. Promise-BQP의 완전 문제
Promise-BQP는 균일한 양자 회로군(즉, BQP 내)에 의해 해결될 수 있는 약속 문제의 부류이다.NP-완전 및 다른 완전 문제의 개념과 유사하게, Promise-BQP에 속하며 Promise-BQP의 다른 모든 문제가 다항 시간 내에 이 문제로 축소될 수 있는 문제를 완전 문제로 정의할 수 있다.
양자 회로 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 의 확률로 나타난다. 4. 1. APPROX-QCIRCUIT-PROB로의 환산
모든 BQP 문제는 APPROX-QCIRCUIT-PROB 문제로 환산될 수 있다는 주장에 대한 증명은 다음과 같다.\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 의 멤버십을 결정한다.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를 공식화할 수 있다.Sum of Histories Tree 양자 회로 (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 를 나타내는 노드에서 끝나는 모든 루트에서 잎으로 가는 경로의 진폭을 더한다.g_i 에 대한 한 레벨과 분기 계수 2^n 을 갖는다.\alpha_x 를 계산하기 위해, 계산의 어떤 시점에서도 하나의 역사만 저장된다. 따라서, 역사 합 알고리즘은 어떤 x에 대해 \alpha_x 를 계산하기 위해 O(nm) 의 공간을 사용하는데, 이는 작업 공간 변수 외에 역사들을 저장하는 데 O(nm) 비트가 필요하기 때문이다.\sum_x |\alpha_x|^2 를 계산할 수 있는데, 이는 회로가 종료될 때 첫 번째 큐비트가 1로 측정될 확률이다.\mathsf{BQP} \subseteq \mathsf{EXP} 임을 증명하기 위해 주어진 시뮬레이션과 비교했을 때, 이 알고리즘은 훨씬 적은 공간을 사용하지만 대신 훨씬 더 많은 시간을 사용한다. 실제로 단일 진폭을 계산하는 데 O(m\cdot 2^{mn} ) 시간이 걸린다.\mathsf{BQP} \subseteq \mathsf{PP} 임을 보일 수 있다.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에 포함되지 않는다는 것을 시사하는 연구 결과들이 제시되고 있다.
참조
[1]
서적
Quantum Computation and Quantum Information
Cambridge University Press
2000
[2]
논문
Quantum Complexity Theory
1997-10
[3]
서적
Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak
https://www.cs.princ[...]
2018-07-24
[4]
논문
Complexity limitations on Quantum computation
http://people.cs.uch[...]
[5]
논문
Quantum computability
1997
[6]
웹사이트
ECCC - TR18-107
https://eccc.weizman[...]
2018-08-03
[7]
논문
BQP and the Polynomial Hierarchy
https://www.scottaar[...]
2010
[8]
논문
Quantum computing, postselection, and probabilistic polynomial-time
[9]
웹사이트
Complexity Class of the Week: PP
http://weblog.fortno[...]
2008-05-02
[10]
논문
A Simple PromiseBQP-complete Matrix Problem
https://theoryofcomp[...]
2024-04-18
[11]
서적
Quantum Computation and Quantum Information: 10th Anniversary Edition
https://books.google[...]
Cambridge University Press
2010-12-09
[12]
서적
Topics in Quantum Computing
https://books.google[...]
O. A. Cross
2012-11-05
[13]
논문
Quantum complexity theory
1997
[14]
논문
Quantum computability
1997
[15]
서적
Quantum Computation and Quantum Information
Cambridge: Cambridge University Press
2000
[16]
논문
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
http://www.arxiv.org[...]
CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.help@durumis.com