Abstract: I will talk about two related puzzles involving mathematics and computation. The first puzzle is about errors made when votes are counted during elections, and I will present a theory of noise stability and noise sensitivity of voting rules and other processes. The second puzzle is: are quantum computers possible? I will discuss the sensitivity of noisy intermediate scale quantum (NISQ) systems and provide an argument for why quantum computers are not possible
https://eta.impa.br/dl/PL008.pdf
https://arxiv.org/abs/1801.02602
本文分为三部分：第一部分讨论线性规划，多面体和单形算法。第二部分讨论噪声稳定性和灵敏度，以及与选举，渗透理论，对策论和计算复杂性的各种联系。第三部分讨论量子计算机。作者认为不可能构建量子计算所需的量子代码，也不可能在其他量子系统中证明量子计算优势。
相关附件
19-PL008 Kalai
