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.