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

量子图灵机停机问题研究

• 批准号: 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機械が構成できることを示した。

由于关于量子图灵机停止问题的数学研究，获得了以下研究结果。 1。给出了量子图灵机的局部过渡功能的表征，并讨论了制备，测量和停止的方案。它已经证明，在没有添加停止Q位的新停止协议下，可以在不干扰计算的情况下确认停止。 2。为了解决量子图灵机的停止问题，我们完善了德意志提出的停止协议，以证明对停止标志的测量以确认量子计算的完成并不会干扰计算结果的概率分布，尽管这扰乱了状态。 3。对于没有停止标志的普通量子图灵机，我们新定义了与路径一致的计算概率，并且我们已经表明，对于任何量子图灵机，可以使用多项式时间的开销来复制计算概率，并且可以构建具有适当吊装标志的量子图型机器。 4。使用上述结果，我们表明，与几种文献中提出的相反，可以构建具有适当停止标志的通用量子图灵机。

项目成果

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

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

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

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

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

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