量子コンピュータによる効率的計算の研究

利用量子计算机进行高效计算的研究

• 批准号: 07780244
• 负责人: 西野 哲朗
• 金额: $ 0.64万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780244/
• 关键词: 量子計算; 量子チューリング機械; NP完全問題; 充足可能性判定問題; 計算量理論

本研究では、巡回セールスマン問題のような極めて難しい組合せ最適化問題に、状態の重ね合わせ等の、量子計算のメカニズムがどのように応用しうるかについて検討を重ねてきた。多項式時間アルゴリズムが知られていない問題が、量子チューリング機械を用いれば、少ない誤り確率で効率良く解けることを証明することは、量子チューリング機械の計算能力を明らかにする上で非常に重要である。そのような結果が証明できれば、少なくとも、量子並列化機能にによって得られた余分な計算能力を、古典的計算によって達成するのが難しいことが示されたことになる。ところで、ショアが対象とした因数分解の問題は、多項式時間では解けず、しかもNP完全でもないだろうと予想されている。そこで本研究では、量子チューリング機械上で、NP完全な組合せ最適化問題を少ない誤り率で効率良く解けるか否かについて検討を行なった。本研究において申請者は、量子チューリング機械を用いたSAT(論理式の充足可能性判定問題)の解法について研究を行ない、以下のような結果を得た。仮定 A: 様相の重ね合わせのなかに、ある特定の様相Cが存在することを観測したときに、Cがその重ね合わせ内に存在していれば、そのことを確率1でCの入力サイズに関する多項式時間で観測することができる。定理 仮定Aのもとでは、SATを多項式時間で解く量子チューリング機械が存在する。

这项研究反复研究了如何将诸如状态叠加之类的量子计算机制应用于极其困难的组合优化问题，例如旅行推销员问题。证明，多项式时间算法未知的问题可以有效地解决使用量子图灵机的误差概率，对于阐明量子图灵机的计算能力非常重要。至少可以证明这样的结果，已经表明，通过经典计算很难实现量子并行化函数获得的额外计算能力。顺便说一句，预计岸边针对的分解问题不能用多项式时间解决，并且在NP中不会完整。因此，在这项研究中，我们研究了NP完全组合优化问题是否可以通过量子图灵机上的错误率有效地解决。在这项研究中，申请人使用量子图灵机研究了SAT的解决方案（逻辑公式的效率确定问题），并获得了以下结果。假设A：当我们观察到特定方面C存在于特征的叠加中时，并且如果在该叠加中存在C时，可以在多项式时间内观察到C的输入大小，概率为1。假设A中的定理存在一个在多项式时间内解决的量子图灵机。

项目成果

T.Nishino & K.Tanaka: "On the Negation-Limited Circuit Complexity of Cliue Functions" IEICE Trnas. on Information and Systems. E78-D. 86-89 (1995)

西野T

T.Nishino & J.Radhakrishnan: "On the Number of Negations Needed to Compute Parity Functions" IEICE Trans. on Information and Systems. E78-D. 90-91 (1995)

西野T