種々の制約のある量子計算機の能力の解析

各种约束条件下量子计算机的能力分析

• 批准号: 19K11816
• 负责人: 中西 正樹
• 金额: $ 2.83万
• 依托单位: Yamagata University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11816/
• 关键词: 量子コンピュータ; 量子アルゴリズム; 量子オートマトン; GPGPU; マージ処理; 量子コンピュータシミュレータ

量子計算機は従来の計算機（古典計算機）とは異なり，量子力学に基づく動作をする。したがって，量子アルゴリズムは従来のアルゴリズムとは根本から異なるものであり，それゆえ従来のアルゴリズムでは成し得ない高速化を達成できる。その一方で，量子計算機の実現には技術的に困難な点も多く，量子計算機が実現した初期の段階では，状態遷移やメモリの扱いに関して様々な制約が付くものと予想されている。本研究では，このような制約の下で，量子計算機がどの程度の能力を発揮するのかを，理論・実験の両面から解析することが目標である。本年度は量子カウンタオートマトンに近い性質を持つaffineカウンタオートマトンについて，誤りのない計算を行う際に，言語の認識能力や必要となる状態数について，古典計算モデルよりも優れていることを示す等，affineカウンタオートマトンとその他のモデルの能力の比較を行った。さらに，主に量子オートマトンのシミュレーションのための要素技術として，昨年度提案したGPGPU向け並列マージ処理の高速化手法の詳細な分析も行った。本手法はMergePathと呼ばれるマージ処理の分割法を応用したものであり，マージ処理を分割する際の粒度を粗くすることで，分割に要する処理時間を低減し，大域メモリのバンド幅を最大限活用できる。昨年度の成果を基に，追加実験による詳細な検証を行い，提案手法が有効に働く条件を調査した。大規模な入力に対しては限界に近い性能を持つことをすでに確認していたが，従来手法と比較した場合の優位性も含め詳細な性能比較を行った。また，提案手法は，メモリ領域の確保を不要とすることにより，要素数の小さなマージに関しても，性能の劣化が少ないアルゴリズムであるという点についても示すことができた。

Quantum computers are very different from modern computers (classical computers) in that quantum mechanics is the basis of all operations. To achieve this goal, the quantum computer system is designed to be able to convert the computer system into a computer system. On the other hand, the implementation of quantum computers has many technical difficulties. Quantum computers have been implemented in the early stages, and state transitions and restrictions have been imposed on them. In this study, quantum computers have been developed to a high degree of capability under the constraints of theory, implementation and analysis. This year, we will continue to pay attention to the quality of quantum calculation, the calculation of errors, the cognitive ability of speech and the number of necessary states, the calculation of classical calculation, the comparison of affine calculation and other cognitive abilities. In addition, the main quantum technology and the annual proposal of GPGPU are analyzed in detail. This method reduces the processing time of the MergePath call processing and maximizes the utilization of the large domain call processing. Based on the results of the previous year, the detailed investigation was added, and the proposal method was investigated. Large scale penetration, close to the performance, confirm the superiority of the situation, and compare the performance. In addition, the proposed method is to ensure that the number of elements is small, and the performance is degraded.

项目成果

A Fast Parallel Merge Algorithm Based on Coarse-Grained Decomposition

一种基于粗粒度分解的快速并行合并算法

• DOI: 10.14923/transinfj.2022jdp7019
• 发表时间: 2023
• 期刊: 電子情報通信学会論文誌D 情報・システム
• 作者: 千葉 理揮;中西 正樹
• 通讯作者: 中西 正樹

A hardware simulator architecture for quantum heuristic search algorithms

用于量子启发式搜索算法的硬件模拟器架构

• 发表时间: 2020
• 作者: Ayaka Kobori;Rio Takahashi;and Masaki Nakanishi
• 通讯作者: and Masaki Nakanishi

University of Latvia(ラトビア)

拉脱维亚大学（拉脱维亚）

Kazan Federal University(ロシア連邦)

喀山联邦大学（俄罗斯联邦）

Exact Affine Counter Automata

精确仿射计数器自动机

• DOI: 10.1142/s012905412241009x
• 发表时间: 2022
• 期刊: International Journal of Foundations of Computer Science
• 影响因子: 0.8
• 作者: Nakanishi Masaki;Khadiev Kamil;Prusis Krisjanis;Vihrovs Jevgenijs;Yakaryilmaz Abuzer
• 通讯作者: Yakaryilmaz Abuzer