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

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

基本信息

批准号：
19K11816
负责人：
中西正樹
金额：
$ 2.83万
依托单位：
Yamagata University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2019
资助国家：
日本
起止时间：
2019-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

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

与传统计算机（经典计算机）不同，量子计算机根据量子力学运行。因此，量子算法与常规算法根本不同，因此可以实现传统算法无法实现的加速。另一方面，实现量子计算机存在许多技术困难，预计要实现的量子计算机的早期阶段将受到有关状态过渡和内存处理的各种限制。这项研究的目的是在这些约束下分析量子计算机的理论和实验方面。今年，我们比较了仿射计数器自动机和其他模型的功能，例如表明，在执行无错误计算时，仿射计数器自动机的性质与量子计数器自动机的功能相似，在执行无错误计算时所需的状态数量和执行无错误计算时所需的状态数量优于经典计算模型。此外，我们还对GPGPU的并行合并处理进行了详细分析，我们于去年提出了这一方法，主要是用于量子自动机仿真的基本技术。该方法应用了一种称为MergePath的合并处理方法的方法，并且可以减少合并处理时的粒度，可以减少分区所需的处理时间，从而可以充分利用全局内存的带宽。根据去年的结果，使用其他实验进行了详细的验证，以研究提出的方法有效工作的条件。尽管已经确认它的性能接近大规模输入的极限，但我们进行了详细的性能比较，包括与常规方法相比的优势。此外，提出的方法能够证明它是一种算法，即使消除了保留记忆区域的需求，也可以通过合并元素的数量来降低性能恶化。

项目成果

期刊论文数量（9）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Fast Parallel Merge Algorithm Based on Coarse-Grained Decomposition

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

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

A hardware simulator architecture for quantum heuristic search algorithms

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

DOI：
发表时间：
2020
期刊：
影响因子：
0
作者：
Ayaka Kobori;Rio Takahashi;and Masaki Nakanishi
通讯作者：
and Masaki Nakanishi

A hardware architecture for the Walsh?Hadamard transform toward fast simulation of quantum algorithms

用于量子算法快速模拟的 Walsh?Hadamard 变换的硬件架构

DOI：
10.1007/s42514-020-00028-7
发表时间：
2020
期刊：
CCF Transactions on High Performance Computing
影响因子：
0.9
作者：
Ayaka Kobori;Rio Takahashi;and Masaki Nakanishi
通讯作者：
and Masaki Nakanishi

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

University of Latvia(ラトビア)

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