Graph isomorphism and quantisation of longest cycles by means of determinants and spectra

通过行列式和谱图同构和最长周期的量化

• 批准号: DP0984470
• 负责人: A/Prof Vladimir Ejov
• 金额: $ 18.17万
• 依托单位: University of South Australia
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2009
• 资助国家: 澳大利亚
• 起止时间: 2009-10-31 至 2012-03-30
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP0984470
• 关键词: Graph; isomorphism; quantisation; longest; cycles

A characterisation of the difficulty of the Hamiltonian cycle problem and the graphs isomorphism problem will be a significant conceptual advancement with repercussions in a number of fields including combinatorial optimisation and theoretical computer science, in particular, the Google PageRank. Applications of tensor networks technique will lead to a design of a quantum computer that enumerates all Hamiltonian cycles in a graph. Analysis of the determinant objective function in terms of the eigenvalues may lead to new spectral properties of stochastic matrices. Algorithmic advances exploiting such a characterisation will significantly contribute to existing technologies for solving problems in a wide range of applications.

对哈密顿循环问题和图同构问题的难度的描述将是一个重要的概念进步，在许多领域产生影响，包括组合优化和理论计算机科学，特别是谷歌PageRank。张量网络技术的应用将导致在一个图中枚举所有哈密顿循环的量子计算机的设计。用特征值来分析行列式目标函数可以得到随机矩阵新的谱性质。利用这种特征的算法进步将大大有助于解决广泛应用中的问题的现有技术。