Problems in algebraic combinatorics

物理学家、计算机科学家和数学家正在努力决定我们如何最好地利用量子计算机。这里的基本问题是弄清楚，我们可以用一台量子计算机做什么，而我们办公桌上的普通计算机是做不到的。这引发了许多问题，其中一些问题与数学家长期以来研究的问题有关。我的研究将涉及其中的三个。 (1)量子力学的一个奇怪特征是，它是在复杂的空间中表述的，而不是真实的空间。其结果是，关于测量的问题与关于复杂空间中的某些线族的问题有关。但这些问题的真实类比已经被数学家广泛地研究过了，我想用这些结果作为指导，在复杂的情况下扩展我们的知识。 (2)操作量子计算机将需要我们在网络中高效地传输信息。要做到这一点，最有效的方法之一涉及物理学家所说的“完美状态转移”。这里的基本理论是由底层网络的结构决定的，更准确地说，是由底层图形的光谱属性决定的。这是数学家们多年来一直在研究的一个课题，我的目标是将我们所学到的应用到这些新的问题上。 (3)最后，我们可以期望量子计算机比经典计算机更有效的问题并不多。其中之一就是图的同构问题。物理学家已经提出了许多算法来解决这一问题，但无法证明它们在实践中确实有效。我已经证明了其中一些是不起作用的，我计划研究那些状态不确定的算法。

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.