計算複雑性理論において、クラスQIP ( Quantum Interactive Proofの略) は、古典的複雑性クラスIPの量子コンピューティング版です。IP は、多項式時間検証器と1 つの計算量が無制限な証明器を備えた対話型証明システムで解決可能な問題の集合です。非公式には、IP は、計算量が無制限な証明器が、入力が言語である場合 (高い確率で) 多項式時間検証器を受け入れさせることができるが、入力が言語でない場合は (これも高い確率で) 検証器を受け入れさせることができない言語の集合です。言い換えると、証明器と検証器は多項式的に多くのラウンドで対話することができ、入力が言語である場合、検証器は 2/3 を超える確率で受け入れ、入力が言語でない場合は、検証器は 2/3 を超える確率で拒否されます。IP では、検証器はBPPマシンのようなものです。 QIPでは、証明者と検証者間の通信は量子的に行われ、検証者は量子計算を実行できます。この場合、検証者はBQPマシンのようなものです。
プロトコルで使用されるメッセージの数を最大kに制限することで、複雑性クラス QIP(k) が得られます。QIP と QIP(k) はJohn Watrous [ 1 ]によって導入されました。彼は Kitaev とともに後の論文[ 2 ]でQIP = QIP(3) であることを証明しました。これは、多項式ラウンドの量子インタラクティブ プロトコルをシミュレートするには 3 つのメッセージで十分であることを示しています。QIP(3) はすでに QIP であるため、4 つの異なるクラスが残ります。QIP(0) はBQP、QIP(1) はQMA、QIP(2)、および QIP です。
キタエフとワトラウスは、QIP が指数時間で決定性チューリングマシンによって解ける問題のクラスであるEXPに含まれることも示しました。 [ 2 ]その後、QIP(2) は、多項式空間で決定性チューリングマシンによって解ける問題の集合であるPSPACEに含まれることが示されました。 [ 3 ]両方の結果は、QIP が PSPACE に含まれるという 2009 年の結果に包含され、[ 4 ]結果 IP = PSPACE を使って PSPACE が QIP に含まれることが簡単に示されるため、QIP = IP = PSPACEであることも証明されます。
参考文献
- ^ Watrous, John (2003), 「PSPACEは定数ラウンドの量子インタラクティブ証明システムを持つ」, Theor. Comput. Sci. , 292 (3), エセックス, イギリス: Elsevier Science Publishers Ltd.: 575– 588, doi : 10.1016/S0304-3975(01)00375-9 , ISSN 0304-3975
- ^ a bキタエフ、アレクセイ、ワトラス、ジョン（2000）、「量子インタラクティブ証明システムの並列化、増幅、指数時間シミュレーション」、STOC '00：第32回ACMコンピューティング理論シンポジウムの議事録、ACM、pp. 608– 617、ISBN 978-1-58113-184-0
- ^ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009)、「2メッセージ量子インタラクティブ証明はPSPACEにある」、FOCS '09: 2009年第50回IEEEコンピュータサイエンス基礎シンポジウム議事録、IEEEコンピュータ協会、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
外部リンク
