A New Model of Quantum Analogue Computation

量子模拟计算的新模型

• 批准号: 13680402
• 负责人: NISHINO Tetsuro
• 金额: $ 2.5万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680402/
• 关键词: quantum computation; analogue computation; NP-complete problem; 量子コンピュータ; アナログ量子計算; グラフの3彩色問題; 断熱量子計算; 計算機シミュレーション; ニューロイダルネット; 量子ニューラルネット; 量子アナログ計算; ニューラルネット; 脳型計算; 量子ニューロイダルネット

In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Then, in 1994, Peter Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. Since it is widely believed that any deterministic Turing machines cannot factor integers in polynomial time, it is very likely that QTM is an essentially new model of computation. On the other hand, many researchers are studying how to physically implement quantum computers. In this research, we propose a quantum analogue computation model solving the graph 3-colorability problem which is known to be NP-complete. Our computer simulation shows that this model offers an appealing prospect for implementation of quantum computers because of a number of reasons.

1985年，David Deutsch将量子图灵机（简称为QTM）作为图灵机，可以执行所谓的量子并行计算。然后，在1994年，彼得·谢尔（Peter Shor）表明，QTM可以在多项式时间内任意较小的误差概率。由于人们普遍认为，任何确定性的图灵机都不能在多项式时间内考虑整数，因此QTM很可能是一种本质上是一种新的计算模型。另一方面，许多研究人员正在研究如何物理实施量子计算机。在这项研究中，我们提出了一个量子模拟计算模型，该模型求解了图3色问题，该模型已知NP完整。我们的计算机模拟表明，由于多种原因，该模型为实施量子计算机提供了吸引人的前景。

项目成果

Junnosuke Moriya, Tetsuro Nishino: "Relationships between the Computational Capabilities of Simple Recurrent Networks and Finite Automata"IEICE Transactions on Fundamentals. Vol.E84-A, No.5. 1184-1194 (2001)

Junnosuke Moriya、Tetsuro Nishino：“简单循环网络和有限自动机的计算能力之间的关系”IEICE Transactions on Fundamentals。

Kazuo Ohta, Tetsuro Nishino, Seiya Okubo, Noboru Kunihiro: "A Quantum Algorithm using NMR Computers to Break Secret-Key Crypto systems"New Generation Computing. 21. 347-361 (2003)

Kazuo Ohta、Tetsuro Nishino、Seiya Okubo、Noboru Kunihiro：“使用 NMR 计算机破解秘密密钥加密系统的量子算法”新一代计算。

守谷 元介, 西野 哲朗: "制限された離散的拡張単純回帰ネットワークと実時間DPDAの等価性"電子情報通信学会論文誌D-1. J85-D-1No.2. 160-167 (2002)

Motosuke Moriya、Tetsuro Nishino：“受限离散扩展简单回归网络与实时 DPDA 的等价”IEICE Transactions D-1 J85-D-1No.2 (2002)。

Kazuo Ohta, Tetsuro Nishino, Seiya Okubo, Noboru Kunihiro: "A Quantum Algorithm using NMR Computers to Break Secret-Key Cryptosystems"New Generation Computing. Vol.21. 347-361 (2003)

Kazuo Ohta、Tetsuro Nishino、Seiya Okubo、Noboru Kunihiro：“使用 NMR 计算机破解密钥密码系统的量子算法”新一代计算。

Junnosuke Moriya, Tetsuro Nishino: "Equivalence of Real-Time DPDAs and Discrete Extended Simple Recurrent Networks with Some Restriction"Systems and Computers in Japan. Vol.34, No.7. 55-62 (2003)

Junnosuke Moriya、Tetsuro Nishino：“实时 DPDA 和带有某些限制的离散扩展简单循环网络的等效性”系统和计算机在日本。