QIP(복잡도)
QIP (complexity)계산 복잡도 이론에서, 클래스 QIP(Quantum Interactive 다항식 시간을 의미)는 고전 복잡도 클래스 IP의 양자 컴퓨팅 유사체이며, 다항식 시간 검증자와 하나의 계산 무한 프로세버를 가진 대화형 증명 시스템에 의해 해결 가능한 문제 집합이다.비공식적으로 IP는 계산상의 제한이 없는 프로버가 다항식 시간 검증자에게 입력이 언어(높은 확률로)일 때 받아들이도록 설득할 수 있고, 입력이 언어(높은 확률로)일 때 받아들이도록 검증자를 설득할 수 없는 언어 세트입니다.즉, 프로버와 검증자는 다항식으로 여러 라운드를 주고받을 수 있으며, 만약 입력이 2/3 이상의 확률로 받아들여져야 하며, 입력이 언어에 있지 않다면 검증자는 2/3 이상의 확률로 거부되어야 한다.IP에서 검증자는 BPP 머신과 같습니다.QIP에서 프로버와 검증자 간의 통신은 양자이며 검증자는 양자연산을 할 수 있다.이 경우 검증자는 BQP 머신과 같습니다.
프로토콜에서 사용되는 메시지 수를 최대 k개로 제한함으로써 복잡도 클래스 QIP(k)를 얻을 수 있습니다.QIP와 QIP(k)는 존 와터러스에 의해 도입되었으며, 존 와터러스는 [1]키타예프와 함께[2] QIP = QIP(3)가 다항 라운드 양자 대화형 프로토콜을 시뮬레이션하는 데 3개의 메시지로 충분함을 증명했다.QIP(3)는 이미 QIP이므로 BQP인QIP(0), QMA인QIP(1), QIP(2) 및 QIP의 4개의 클래스가 남습니다.
Kitaev와 Waturous는 또한 QIP가 EXP에 포함되어 있다는 것을 보여주었는데, EXP는 지수 시간에 [2]결정론적 튜링 기계에 의해 해결될 수 있는 문제 클래스이다.QIP(2)는 다항식 [3]공간에서 결정론적 튜링 기계가 해결할 수 있는 문제 집합인 PSPACE에 포함된 것으로 나타났다.두 결과 모두 QIP가 PSPACE에 [4]포함되어 있다는 2009년 결과에 의해 가정되었다. 이는 또한 PSPACE가 IP = PSPACE 결과를 사용하여 QIP에 있는 것으로 쉽게 나타나기 때문에 QIP = IP = PSPACE임을 증명한다.
레퍼런스
- ^ Watrous, John (2003), "PSPACE has constant-round quantum interactive proof systems", Theor. Comput. Sci., Essex, UK: Elsevier Science Publishers Ltd., 292 (3): 575–588, doi:10.1016/S0304-3975(01)00375-9, ISSN 0304-3975
- ^ a b Kitaev, Alexei; Watrous, John (2000), "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems", STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM, pp. 608–617, ISBN 978-1-58113-184-0
- ^ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009), "Two-Message Quantum Interactive Proofs Are in PSPACE", FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 534–543, ISBN 978-0-7695-3850-1
- ^ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010), "QIP = PSPACE", STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing, ACM, pp. 573–582, ISBN 978-1-4503-0050-6
