Quantum Computation: Foundations, Security, Cryptography and Group Theory

量子计算是基于在量子力学水平上运行的计算机，而不是经典电子学。这样做的好处是，在量子力学中，实体可以同时位于许多不同的位置：这使得量子计算机的状态在某些方面表现得像一堆平行的状态。不幸的是，这种并行堆栈并不是没有字符串的，而且由于量子力学的物理原理，很难找出在特定时间任何这样的堆栈中有什么：因此读取量子计算机的输出并不容易。一些强大的量子算法已经被开发出来：例如，Shor分解整数的速度比传统算法快得多。然而，我们所知的这类算法的数量并没有增长得很快。其中一个原因是，我们对如何构建量子计算算法没有系统的了解，实际上也没有一个全面的算法库，可以用来构建非常基本的函数和程序。这个项目的主要目标是为量子计算建立这样一个系统的基础，并建立基本过程的程序。我们将通过尝试为群论中出现的问题构建算法来测试我们在这些目标上的成功。这一数学领域提供了各种难度级别的无穷无尽的算法问题，因此是潜在计算系统的良好试验台。我们还将考虑如何将密码系统的分析从经典方案扩展到量子方案。特别是，这将使我们能够建立一个自动投票程序，不能被运行它的人篡改或破解。

Quantum computation is based on computers which operate on the level of quantum mechanics rather than classical electronics. The advantage of this is that in quantum mechanics entities can be simultaneously in many different positions at once: and this allows states of a quantum computer to behave in some ways like a stack of parallel states. This parallel stack does not unfortunately come without strings and, because of the physics of quantum mechanics, it is very difficult to find out what is in any such stack at a particular time: so reading the output of a quantum computer is not easy. Some powerful quantum algorithms have been developed: for example by Shor to factor integers much faster than convential algorithms can. However the number of such algorithms that we know is not growing very rapidly. One reason for this is that we do not have a systematic understanding of how to build up quantum computing algorithms and indeed do not have a comprehensive library of algorithms for very basic functions and procedures for building from them. The main aims of this project are to construct such a systematic foundation for quantum computation and to establish procedures for basic processes.We shall test our success in these objectives by attempting to construct algorithms for problems which arise in group theory. This area of mathematics provides an endless array of algorithmic problems at all levels of difficulty, so is a good test bed for a potential computation system. We shall also consider how to extend the analysis of cryptographic systems from classical schemes to quantum schemes. In particular this is expected to allow us to build an automated voting process which cannot be tampered with or broken into, by the people who run it.