ドイッチュ・ジョサのアルゴリズムは、量子アルゴリズムであり、1992年にデイビッド・ドイッチュ（英語版
）とリチャード・ジョサ（英語版）によって提案され[1]、 Richard Cleve, Artur Ekert, Chiara Macchiavello, そして Michele Mosca によって 1998 年に改良された[2]。実用性は限られるが、既存のどの決定論的古典アルゴリズムよりも指数関数的に早い量子アルゴリズムのうち最も早期に発見されたものの一つである。また、これは決定的アルゴリズムであり、常に解を得ることができ、またその解は常に正しい。ドイッチュ・ジョサの問題では、オラクルと呼ばれるある関数 f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}} が実装されたブラックボックス量子コンピュータが与えられている。わかりやすく言えば、オラクルはn桁の2進数値を入力として受け取り、0または1を出力する。
ここで、関数 f {\displaystyle f} は定値 (すべての量子ビットが0 またはすべての量子ビットが1)であるか、均等 (量子ビットの丁度半数が1で、残りの半数が0)であることが保証されている。
問題は、オラクルを用いて関数が定値か均等かを決定することである。 ドイッチュ・ジョサの問題は、量子アルゴリズムで解きやすく、かつ、決定的古典アルゴリズムでは解くのが難しいよう明示的に意図された問題である。この問題の動機付けは、決定的古典コンピューターでは問題を解くのに大量のクエリを必要とするブラックボックス問題を、量子コンピューターが誤りなく効率的に解くことが可能であることを示すことにある。
動機
脚注[脚注の使い方]^ Deutsch, D.; Jozsa, R. (1992-12-08). ⇒“Rapid Solution of Problems by Quantum Computation” (英語). Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 439 (1907): 553?558. doi:10.1098/rspa.1992.0167
表
話
編
歴
量子コンピュータ
全般
量子コンピュータ
量子力学
ハードウェア
超伝導
イオントラップ型
核磁気共鳴
光子
アルゴリズム?
プログラミング言語
量子プログラミング言語
ドイッチュ・ジョサのアルゴリズム
グローバーのアルゴリズム
ショアのアルゴリズム（英語版）
項目
量子ビット
量子回路
量子テレポーテーション
量子暗号
量子アニーリング
量子状態
量子もつれ
量子超越性
量子ウォーク
量子情報
関連分野
量子情報科学
情報工学
メーカー
IBM
D-Wave
Google
実機
九章
人物
ピーター・ショア
ロブ・グローバー（英語版）
デイヴィッド・ドイッチュ
リチャード・ジョサ（英語版）
カテゴリ
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}
この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}
表示
編集
