グラフ固有値の研究及び量子ウォークの周期性問題の代数的グラフ理論からのアプローチ

从代数图论研究图特征值和量子游走周期性问题的方法

基本信息

批准号：
18J10656
负责人：
久保田匠
金额：
$ 0.96万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-25 至 2020-03-31
项目状态：
已结题

项目摘要

グラフ上の量子ウォークでは現在、無向グラフ上で考察するのが慣例となっている。私は、これらの研究を有向グラフに拡張し、「代数的グラフ理論」の観点から「量子ウォーク」の考察を与えることを目的として研究を行った。先行研究で導入された twisted Szegedy walk を利用して、「有向グラフから定まる量子ウォーク」の研究を行った。まずは、時間発展行列の基本的な性質を調べる必要があったため、次のふたつの小課題を解決することを目指した：①スペクトル写像定理がこのモデルでも成立することの確認②時間発展行列の2乗の正台の構造定理の発見①について、時間発展行列の固有値解析は、いわゆるdiscriminant と呼ばれる別の行列の固有値解析に帰着される。本研究で取り扱う twisted Szegedy walk のdiscriminant は、実は GuoとMohar が定義したエルミート隣接行列をある意味で正規化したものと完全に一致する。そこで、まずは時間発展行列の固有値解析の基本的な道具であるスペクトル写像定理がこのモデルでも成立することを確認した。②では、時間発展行列の正台の構造を調べた。結果的に、「Grover walkの時間発展行列の正台と負台」と「1-form 関数θによる摂動を表す行列」が本質的に重要であることを突き止めた。「Grover walk の時間発展行列の正台」はよく研究されている。そこで、私は「Grover walk の時間発展行列の負台」と「θによる摂動を表す行列」を明らかにし、新たに定義した量子ウォークの時間発展行列の2乗の正台を明示的に表すことに成功した（実は同時に、2乗の負台を明らかにすることにも成功している）。

目前，通常考虑无向图上的量子游走。我进行研究的目的是将这些研究扩展到有向图，并从“代数图论”的角度考虑“量子行走”。利用之前研究中引入的扭曲塞格迪游走，我们对“由有向图确定的量子游走”进行了研究。首先，需要研究时间演化矩阵的基本性质，因此我们旨在解决以下两个小问题：（1）证实谱映射定理在该模型中也成立；（2）2.关于幂平方结构定理（1）的发现，时间演化矩阵的特征值分析被简化为另一个称为判别式的矩阵的特征值分析。本研究中处理的扭曲Szegedy游走的判别式实际上完全符合Guo和Mohar定义的归一化Hermitian邻接矩阵。首先，我们确认谱映射定理（时间演化矩阵特征值分析的基本工具）在该模型中也成立。在②中，我们研究了时间演化矩阵正级的结构。结果，我们发现“格罗弗行走时间演化矩阵的正侧和负侧”以及“代表 1-形式函数 θ 引起的扰动的矩阵”本质上很重要。 “格罗弗沃克时间演化矩阵的基础”已经得到了很好的研究。因此，我澄清了“格罗弗游走时间演化矩阵的负基”和“代表θ扰动的矩阵”，并明确表达了“格罗弗游走时间演化矩阵平方的正基”。新定义的量子行走。（实际上，同时他也成功地揭示了平方的负值。）