Combinatorial designs in quantum information theory and digital communications

如果没有卫星通信、手机、便携式音乐播放器、闪存驱动器、GPS(全球定位系统)导航和电影点播等数字通信技术，现代社会将变得不可识别。这些技术变得无处不在、被广泛接受和高度可靠的一个关键原因是嵌入式数学结构和算法提供的关键支持，这些结构和算法对用户来说是不可见的。 在这些技术中对嵌入数学的要求源于物理约束的组合，例如，希望有效地使用能量将信息从一个设备发送到另一个设备，或者即使外部人员可以监视交换也希望在双方之间安全地传递信息，或者尽管原始信号被噪声破坏，也希望正确地恢复所传输的信息。这些物理约束的组合对应于安排受多个约束的对象的数学问题；这种问题通过组合设计来解决。 这项提案的短期目标涉及使用组合设计来解决数字通信中三个众所周知的具有挑战性的问题： (1)构造大型复杂等角线集。 (2)约束最大数目的复杂的相互无偏碱基。 (3)构造具有大的渐近优点因子的二元序列族。 寻求这些问题的完全解决方案是非常雄心勃勃的：每个问题都抵制了无数数学家、物理学家和工程师几十年来的大量努力。 问题1和2出现在量子信息理论中，这是一个动态研究领域，涉及在非常小的尺度上处理信息，传统物理不再适用。解决这些问题将有利于量子版本的密码学(人们希望使消息难以被对手阅读)和量子版本的纠错码(相反，人们希望即使在噪声存在的情况下也能使消息更容易被他人阅读)。组合设计在解决这些问题中的重要性尚未确定，这是本提案的一个主要创新方面。 问题3出现在传统(非量子)数字通信和统计力学中。它的解决方案将允许设计更高效的雷达和无线通信，并创造可申请专利的技术。 其目的不仅是为了解决这些具体问题，而且在这样做的同时，也是为了创造新的工具和方法来分析与数字通信相关的广泛类别的组合结构。这与我的研究计划的长期目标相联系：结合组合、代数、分析和计算技术，从根本上改变对经典和新兴问题的研究，这些问题在实际和理论数字通信中都很重要。

Modern society would be unrecognizable without digital communications technologies such as satellite communication, cell phones, portable music players, flash drives, GPS (global positioning system) navigation, and movies on demand. A key reason these technologies have become ubiquitous, widely accepted, and highly dependable is the critical support provided by embedded mathematical structures and algorithms that remain invisible to the user. The requirement for embedded mathematics in these technologies derives from a combination of physical constraints, for example the desire to send information from one device to another using energy efficiently, or to pass information securely between two parties even though outsiders can monitor the exchange, or to recover transmitted information correctly despite corruption of the original signal by noise. These combinations of physical constraints correspond to mathematical problems of arranging objects subject to multiple constraints; such problems are solved by combinatorial designs. The short-term objectives of this proposal involve the use of combinatorial designs to solve three notoriously challenging problems of digital communications: (1) Construct large sets of complex equiangular lines. (2) Constrain the largest number of complex mutually unbiased bases. (3) Construct families of binary sequences with large asymptotic merit factor. Seeking a complete solution to these problems is highly ambitious: each has resisted considerable effort over decades by numerous mathematicians, physicists, and engineers. Problems 1 and 2 arise in quantum information theory, a dynamic research area dealing with the processing of information at very small scales where conventional physics no longer applies. Solving these problems would benefit the quantum version of cryptography (where one wishes to make messages difficult for an adversary to read) and the quantum version of error-correcting codes (where, on the contrary, one wishes to make messages easy for others to read even in the presence of noise). The importance of combinatorial designs in solving these problems has not yet been established, and is a major innovative aspect of this proposal. Problem 3 arises in conventional (non-quantum) digital communications and in statistical mechanics. Its solution would allow the design of more efficient radar and wireless communications, and the creation of patentable technology. The aim is not only to solve these specific problems, but in doing so to create new tools and methods for analyzing a wide class of combinatorial structures related to digital communications. This links to the long-term goal of my research program: to combine combinatorial, algebraic, analytical, and computational techniques to transform radically the study of classical and emerging problems that are important in practical and theoretical digital communications.