CAREER: Discrete Structures and Orthogonal Systems

量子算法能在多大程度上超越经典算法？这个悬而未决的问题最近被表述为一个数学问题，它挑战了数学界，但尚未得到解决。这个问题与另一个问题有关：对给定信息进行编码和传输的最“有效”方式是什么？例如，a)人们可以尝试最小化在编码信息中使用的符号的数量，或者b)人们可以在编码的消息中保持“某些结构”(例如，通过重复某些“模式”)，以避免信息的丢失，前提是在其传输过程中可能出现几个错误。这个项目的目标是研究只使用0和1来近似给定信息或给定信号的最佳方法。首席调查员将让本科生和研究生参与提案中描述的研究项目。PI将为研究生组织一年一次的分析和概率暑期班。这将是博士生与顶尖专家参与研究讨论并了解新兴数学领域的一个很好的机会。上述量子算法问题可以表示为布尔立方体上的显式傅里叶解析问题。在技术层面上，该建议侧重于超缩性，即赋范空间之间的半群的有界性，它在复数域上的全纯扩张，在矩比较估计中的应用，马尔可夫-伯恩斯坦型不等式(对于生活在低频和高频上的多项式)，离散逼近理论，以及经典和量子算法的复杂性。其中一个重要的例子是汉明立方体，它配备了乘积测量。这个项目专注于维度独立的估计，并提出了一个计划，一系列基本问题以及解决这些问题的步骤(热流论证、鞅技术、保角映射和概率论证)，这是推进和发展布尔立方体上的傅立叶分析所必需的。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

How much can quantum algorithms outperform classical algorithms? This open question has been recently formulated as a mathematical problem that has challenged the mathematical community but has yet to be solved. The question is related to another one: what is the most "efficient" way to encode and transmit given information? For example, a) one can try to minimize the number of symbols used in encoding the information, or b) one can maintain "certain structures" (say by repeating some "pattern") in encoded messages in order to avoid loss of information, provided that a couple of errors can be made during its transmission. The goal of this project is to investigate what the best way is to approximate given information or a given signal using only zeros and ones. The principal investigator will involve undergraduate and graduate students in research projects described in the proposal. The PI will organize a yearly summer school in analysis and probability for graduate students. This will be a good opportunity for PhD students to participate in research discussions with leading experts and to learn about emerging areas in mathematics. The question of quantum algorithms described above can be formulated as an explicit Fourier–analytic question on the boolean cube. On a technical level the proposal focuses on hypercontractivity, i.e., boundedness of a semigroup between normed spaces, its holomorphic extensions to complex domains, applications in moment comparison estimates, Markov—Bernstein type inequalities (for polynomials living on low and high frequencies), discrete approximation theory, and complexity of classical and quantum algorithms. One of the important examples involves the Hamming cube, equipped with a product measure. This project focuses on dimension independent estimates and proposes a program, a series of fundamental questions together with steps towards the resolution of these questions (heat flow arguments, martingale techniques, conformal maps, and probabilistic arguments), necessary for advancing and developing Fourier analysis on the Boolean cube.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.