デモクリトスと量子計算

スコット・アーロンソン 著　森弘之 訳「デモクリトスと量子計算」メモ

デモクリトスと量子計算

スコット・アーロンソン　著　森弘之　訳

「デモクリトスと量子計算」メモ

第２０章　タイムトラベル

【まとめ】　

・計算を高速化させるための時間的閉曲線（ＣＴＣ）の利用方法は、答えを計算し、それを計算機が動き出す前の時刻に送り返すこと。
・親殺しのパラドックスを避けるには、「出力側の分布が入力側の分布と同じという条件を課せばよい。
・ＣＴＣコンピュータはＮＰ完全問題を多項式時間で解け、ＣＴＣが存在するとすると、量子コンピュータは古典的コンピュータと同じ能力になる。