Problems in algebraic combinatorics

代数组合问题

• 批准号: 9439-2012
• 负责人: Godsil, Christopher
• 金额: $ 2.19万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568676
• 关键词: Problems; algebraic; combinatorics

Physicists, computer scientists and mathematicians are working to decide how we may best make use of quantum computers. Here the basic problem is to work out just what we might do with a quantum computer that we cannot do with the ordinary computers already on our desks. This raises many questions, and a number of these are related to problems that have long been studied by mathematicians. My research will concern three of these. (1) One of the strange features of quantum mechanics is that it is formulated in terms of complex, rather than real, space. A consequence of this is that questions about measurements are related to questions about certain families of lines in complex space. But the real analogs of these problems have already been extensively studied by mathematicians, and I would like to use these results as a guide to extend our knowledge in the complex case. (2) Operating a quantum computer will require us to move information around a network efficiently. One of the most efficient ways to do this involves what physicists call "perfect state transfer''. The underlying theory here is determined by the structure of the underlying network and, more precisely on the spectral properties of the underlying graph. This is a subject that mathematicians have studied for many years, and my aim is to apply what we have learned to these new problems. (3) Finally there are not many problems where we can expect a quantum computer to be more effective than a classical computer. One of these is the graph isomorphism problem. Physicists have proposed a number of algorithms for this, but cannot show that they will actually work in practice. I have shown that some of these do not work, and I plan to study the algorithms whose status is undecided.

物理学家、计算机科学家和数学家正在研究如何最好地利用量子计算机。这里的基本问题是，弄清楚我们可以用量子计算机做什么，而我们不能用桌上的普通计算机做什么。这就提出了许多问题，其中许多问题与数学家长期研究的问题有关。我的研究将涉及其中的三个方面。