ドイッチュ・ジョサのアルゴリズムとは？わかりやすく解説

ドイッチュ・ジョサのアルゴリズムは、量子アルゴリズムであり、1992年にデイビッド・ドイッチュ（英語版）とリチャード・ジョサ（英語版）によって提案され^[1]、 Richard Cleve, Artur Ekert, Chiara Macchiavello, そして Michele Mosca によって 1998 年に改良された^[2]。実用性は限られるが、既存のどの決定論的古典アルゴリズムよりも指数関数的に早い量子アルゴリズムのうち最も早期に発見されたものの一つである。また、これは決定的アルゴリズムであり、常に解を得ることができ、またその解は常に正しい。