コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

EQP (計算複雑性理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』

計算複雑性理論において、 EQP (exact quantum polynomial time, QP とも) は量子コンピュータが確率1で正しい答を、多項式時間内に与えることができる決定問題のクラスである。複雑性クラス P の量子的な相当物といえる。

逆に言えば、量子コンピュータを用いたアルゴリズム量子アルゴリズム英語版)の中には決定問題を決定的に、多項式時間内に解くものが存在するということである。

出典

[編集]
  • Complexity Zoo: EQP