量子Turing Machineの停止過程について

量子Turing Machineの停止プロセスについての問題提起を行う。量子Turing Machineの停止を知るためには、系を観測しつづけなければならないが、その観測という行為は計算過程を破壊してしまう可能性がある。そこで観測プロセスはminimalなものを選ばねばならないことが知られている。とりわけ、異なる停止時刻をもつ量子ブランチをもつような計算過程においては、注意が必要である。そのような状況を避けるためにBernsteinとVaziraniによる量子Turing Machineの基礎的研究においては、量子Turing Machine自体が全てのブランチが同時に停まるものか全く停まらないものだけに制限されていた。本講演では、適当な量子Turing Machine（の候補）が与えられた時に、それが彼らの条件を満たすものかどうかを判定するようなアルゴリズムは存在しないことを示す。この結果は、量子Turing Machineの「停止」は、自然に確率的なものになってしまうことを示唆する。