量子計算の分野で知らぬ人はいないであろう，世界的に有名な David Deutsch（ドイッチュ）という人がいる。
この人が（たぶん1985年に書いた論文で）述べた問題およびその解法は Deutsch の問題だとか，Deutsch のアルゴリズムという言葉で呼ばれている。
その問題は "Deutsch's algorithm" と題するサイトによると，次のようなものである。
Deutsch 氏によると，このような関数の性能を一回の測定で調べるだけで，定数関数かそうでないかを決定できるということである。
実のところきちんとした状況設定と Deutsch の解法（アルゴリズム）を理解していないので，これ以上きちんと説明はできないが，正直者か嘘つきであるかのどちらかはわからないが，いずれかである人に一つの質問をするだけで進むべき正しい道を知るという論理パズルについて話しているときに，gk 氏が教えてくれた問題である。
ちなみに，今読んでいる Smullyan 氏の本にはこの手の問題がたくさん載っているので，この類の問題を "One-question problem" （略して OQP）と呼ぶことにする。（誤解のないように断っておくと，この呼称は僕が今ここで勝手に名づけただけで，Smullyan 氏がそう呼んでいるわけではない。）
ちょうど二週間前にそこそこ使える統一的な解法を一つ見出したが，それはまた機会があれば述べることにする。
Deutsch 氏の問題と OQP が関連あるかどうかは今のところよくわからないが，Deutsch 氏の問題の答えの結論そのものは，最初聞いたときには驚いたが，今では驚きはそれほどでもない。
ポイントは，この関数の 0 に対する出力と 1 に対する出力の排他的論理和 (EXOR) の値を何らかの方法で知ることにあるようだ。けれども，問題の設定として，問題の関数 f に「訊ける」のは一回だけであって，素朴に考えると 0 か 1 かのいずれかを入力することくらいしか思いつかない。しかし，それだと，例えば 0 に対して 0 が返ってきたとしても，1 を入力したら 0 なのか 1 なのかはそれだけの情報からは全くわからない。
そこで Deutsch 氏は量子状態に特有の entanglement（エンタングルメント，「もつれ」などと訳される）という状態をうまく利用すれば，ある意味，0 と 1 を同時に関数 f に入力し，その結果の排他的論理和を観測値として手に入れることができることを示したらしい。この場合，「観測値」というのはもはや f の出力そのものではないので，別にこしらえた何らかの装置が必要なはずであるが，それがおそらく entanglment している量子状態なのだろう。
詳細は，がんばってサイト "Deutsch's algorithm" を解読して勉強することとして，なぜ驚きが薄れたかを最後に述べて締めくくることにしよう。
「古典的」には 0，1 の二種類の入力を個別に与えることしかできず，それらに対する出力だけでは f が定数関数かそうでないかの特定までには至らない。けれども，f の特性のうち，「半分」だけはわかる。
つまり，0 を入力したら 0 を出すのか，1 を出すのか，という結果により，4通りある f の可能性のうち，2通りにまで減らすことができる。
一方，「量子的」な方法によると，f が2通りある定数関数タイプのいずれかか，そうでない残りの2通りのいずれかであることがわかるという意味では，やはり4通りの可能性を半分の2通りに減らすことができるわけであるが，しかし，0 を入力したら f が 0 と 1 のいずれを出力するのか，1 に対して何を返すのかは全くわからないのである。
つまり，「はい」か「いいえ」の一つの答えでもって4通りの可能性を2通りの可能性までにしか絞れない，という点では，常識的な範疇の話であるな，という気がする。そのような捉え方をすると，それほど逆説的な結果であるようには思えないのである。
ただ，0 に対して x，1 に対して y を返す関数を [x,y] という記号で表すことにすると，普通に考えただけでは，一回の測定の結果からは
[0,0] と [0,1] のいずれかであるか，あるいは [1,0] と [1,1] のいずれかであるか
というグループ分けしかできないのに対し，Deutsch 氏の方法では
[0,0] と [1,1] のいずれかであるか，あるいは [0,1] と [1,0] のいずれかであるか
という，全く異なる組み分けを可能にするわけだから，よくそんな方法を思いついたものだなぁ，という点については，驚嘆の念が強まりこそすれ，薄まることはない。
ちなみに，旅人が道を訊くタイプの OQP では，
「村人が正直者で右の道が正しい」か「村人が嘘つきで左の道が正しい」かの，どちらであるかを知りたければ，「右の道は正しいですか」と尋ねればよい。
答えが「はい」なら，右の道が正しくて村人が正直に答えたか，あるいは右の道は間違いで，村人が嘘をついたかのいずれかだからである。こう訊けばよいことは，僕が考えた OQP の解法を利用すれば直ちにわかる。
と，思わせぶりなことを言ってみたり。
この人が（たぶん1985年に書いた論文で）述べた問題およびその解法は Deutsch の問題だとか，Deutsch のアルゴリズムという言葉で呼ばれている。
その問題は "Deutsch's algorithm" と題するサイトによると，次のようなものである。
0 または 1 を入力すると，0 か 1 のいずれかを出力する関数 f がある（そのような関数は，2通りの入力 0，1 のそれぞれに 0 か 1 かを対応させるので，22=4 通りある）。この関数 f が定数関数（0 と 1 のどちらの入力に対しても 0 しか出力しないか，あるいは 1 しか出力しない）か，そうでないかを決定せよ。
Deutsch 氏によると，このような関数の性能を一回の測定で調べるだけで，定数関数かそうでないかを決定できるということである。
実のところきちんとした状況設定と Deutsch の解法（アルゴリズム）を理解していないので，これ以上きちんと説明はできないが，正直者か嘘つきであるかのどちらかはわからないが，いずれかである人に一つの質問をするだけで進むべき正しい道を知るという論理パズルについて話しているときに，gk 氏が教えてくれた問題である。
ちなみに，今読んでいる Smullyan 氏の本にはこの手の問題がたくさん載っているので，この類の問題を "One-question problem" （略して OQP）と呼ぶことにする。（誤解のないように断っておくと，この呼称は僕が今ここで勝手に名づけただけで，Smullyan 氏がそう呼んでいるわけではない。）
ちょうど二週間前にそこそこ使える統一的な解法を一つ見出したが，それはまた機会があれば述べることにする。
Deutsch 氏の問題と OQP が関連あるかどうかは今のところよくわからないが，Deutsch 氏の問題の答えの結論そのものは，最初聞いたときには驚いたが，今では驚きはそれほどでもない。
ポイントは，この関数の 0 に対する出力と 1 に対する出力の排他的論理和 (EXOR) の値を何らかの方法で知ることにあるようだ。けれども，問題の設定として，問題の関数 f に「訊ける」のは一回だけであって，素朴に考えると 0 か 1 かのいずれかを入力することくらいしか思いつかない。しかし，それだと，例えば 0 に対して 0 が返ってきたとしても，1 を入力したら 0 なのか 1 なのかはそれだけの情報からは全くわからない。
そこで Deutsch 氏は量子状態に特有の entanglement（エンタングルメント，「もつれ」などと訳される）という状態をうまく利用すれば，ある意味，0 と 1 を同時に関数 f に入力し，その結果の排他的論理和を観測値として手に入れることができることを示したらしい。この場合，「観測値」というのはもはや f の出力そのものではないので，別にこしらえた何らかの装置が必要なはずであるが，それがおそらく entanglment している量子状態なのだろう。
詳細は，がんばってサイト "Deutsch's algorithm" を解読して勉強することとして，なぜ驚きが薄れたかを最後に述べて締めくくることにしよう。
「古典的」には 0，1 の二種類の入力を個別に与えることしかできず，それらに対する出力だけでは f が定数関数かそうでないかの特定までには至らない。けれども，f の特性のうち，「半分」だけはわかる。
つまり，0 を入力したら 0 を出すのか，1 を出すのか，という結果により，4通りある f の可能性のうち，2通りにまで減らすことができる。
一方，「量子的」な方法によると，f が2通りある定数関数タイプのいずれかか，そうでない残りの2通りのいずれかであることがわかるという意味では，やはり4通りの可能性を半分の2通りに減らすことができるわけであるが，しかし，0 を入力したら f が 0 と 1 のいずれを出力するのか，1 に対して何を返すのかは全くわからないのである。
つまり，「はい」か「いいえ」の一つの答えでもって4通りの可能性を2通りの可能性までにしか絞れない，という点では，常識的な範疇の話であるな，という気がする。そのような捉え方をすると，それほど逆説的な結果であるようには思えないのである。
ただ，0 に対して x，1 に対して y を返す関数を [x,y] という記号で表すことにすると，普通に考えただけでは，一回の測定の結果からは
[0,0] と [0,1] のいずれかであるか，あるいは [1,0] と [1,1] のいずれかであるか
というグループ分けしかできないのに対し，Deutsch 氏の方法では
[0,0] と [1,1] のいずれかであるか，あるいは [0,1] と [1,0] のいずれかであるか
という，全く異なる組み分けを可能にするわけだから，よくそんな方法を思いついたものだなぁ，という点については，驚嘆の念が強まりこそすれ，薄まることはない。
ちなみに，旅人が道を訊くタイプの OQP では，
「村人が正直者で右の道が正しい」か「村人が嘘つきで左の道が正しい」かの，どちらであるかを知りたければ，「右の道は正しいですか」と尋ねればよい。
答えが「はい」なら，右の道が正しくて村人が正直に答えたか，あるいは右の道は間違いで，村人が嘘をついたかのいずれかだからである。こう訊けばよいことは，僕が考えた OQP の解法を利用すれば直ちにわかる。
と，思わせぶりなことを言ってみたり。
※コメント投稿者のブログIDはブログ作成者のみに通知されます