量子チューリング機械の停止問題に関する研究

量子图灵机停机问题研究

• 批准号: 10874016
• 负责人: 小澤 正直
• 金额: $ 0.83万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10874016/
• 关键词: 量子計算; 量子チューリング機械; 量子回路; 停止問題; 量子アルゴリズム; 計算量; 量子力学; 量子測定

量子チューリング機械の停止問題に関する数理科学的研究を行なった結果、次の研究成果を得た。1.量子Turing機械の局所遷移関数の特徴付けを与え、準備、測定、停止のためのプロトコルを考察した。停止qビットを付加しない新しい停止プロトコルのもとで、計算を乱さずに停止を確認できることを証明した。2.量子Turing機械の停止問題を解決するために、Deutschの提案したHalting protocolを精密化して、量子計算完了を確認するためのHalting flagの測定が状態を乱すにもかかわらず、計算結果の確率分布を乱さないことを証明した。3.Halting flagをもたない一般の量子Turing機械に対して、経路に即した計算確率というものを新たに定義し、任意の量子Turing機械に対して、多項式時間のオーバーヘッドでその計算確率を再現し、適正なHalting flagをもつ量子Turing機械が構成できることとを示した。4.以上の、結果を利用して、これまでいくつかの文献で唱えられたことに反して、適正なHalting flagをもつ万能量子Turing機械が構成できることを示した。

The results of the research on quantum mechanics and the results of the second research are obtained. 1. The characteristics of quantum Turing machinery are related to the transfer, preparation, measurement and stop of the machine. Stop the search, stop the search. 2. Quantum Turing Machine Stop Problem Solution, Deutsch Proposal, Halting Protocol, Precision, Quantum Calculation Completion, Confirmation, Halting Flag Measurement Status, Calculation Result Accuracy Distribution, Chaos, Proof 3. Halting flag: general quantum turning mechanism, circuit, calculation accuracy, new definition, arbitrary quantum turning mechanism, polynomial time, calculation accuracy, reproduction, proper Halting flag, quantum turning mechanism construction, etc. 4. The above results are used to illustrate the structure of universal quantum turning machinery.

项目成果

小澤正直: "Local Transition Functions of Quantum Turing Machines"京都大学数理解析研究所講究録. 1100. 168-181 (1999)

小泽正直：“量子图灵机的局域转换函数”京都大学数学科学研究所 Kokyuroku。1100. 168-181 (1999)

H.Yamashita: "Nonstandard Representations of the Canonical Commutation Relations"Rev.Math.Phys.. (印刷中). (2000)

H.Yamashita：“规范交换关系的非标准表示”Rev.Math.Phys..（出版中）。

M.Ozawa: "Entanglement measures and the Hilbert-Schmidt distance"Phys.Lett.A. (印刷中). (2000)

M.Ozawa：“纠缠测量和希尔伯特-施密特距离”Phys.Lett.A（出版中）。