In this dissertation we demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. We consider two aspects of this problem. First, it is known that the standard Continuous-Time Quantum Walk (CTQW), proposed by Childs and Goldstone, can propagate quickly on the infinite path graph. However, the Schr\"odinger equation requires the Hamiltonian to be symmetric, and thus only undirected graphs can be implemented. In this thesis, we address the question, whether it is possible to construct a continuous-time quantum walk on general directed graphs, preserving its propagation properties. Secondly, the quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. However, most of these graphs have very simple structures. The most advanced results concerned the Erd\H{o}s-R\'enyi model of random graphs, which is the most popular but not realistic random graph model, and Barab\'asi-Albert random graphs, for which full quadratic speed-up was not confirmed. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
翻译:在此解析中,我们证明连续时间量子漫步模型对于非三角图形结构仍然很强大。 我们考虑了这一问题的两个方面。 首先, 众所周知, Childs 和 Goldstone 提出的标准连续时量子漫步( CTQW ) 可以在无限路径图上迅速传播。 然而, Schr\'' odinger 方程式要求汉密尔顿语是对称的, 因此只能执行无方向的图形。 在此论文中, 我们处理的问题是, 能否在一般定向图形上构建一个持续时间量子漫步, 以保存其传播特性。 其次, CTQW 定义的量子空间搜索已被证明对各种非定向图案运作良好。 然而, 这些图表中的大多数结构非常简单。 最先进的结果涉及到随机图形的 Erd\ H{ o}s- R\\' enyi 模型, 这是最受欢迎但并非现实的随机图表模型, 以及 Barab\' as- Albert 随机图, 随机图, 其全四边速度结构是否被观察到。