XiaoMi-AI文件搜索系统
World File Search Systemfocs
量子计算的简洁经典验证
摘要。我们为量子计算 (BQP) 构建了一个经典可验证的简洁交互式论证，其通信复杂性和验证器运行时间在 BQP 计算的运行时间内是多对数的（在安全参数中是多项式的）。我们的协议是安全的，假设不可区分混淆 (iO) 和错误学习 (LWE) 的后量子安全性。这是第一个简洁的论证，适用于普通模型中的量子计算；先前的工作（Chia-Chung-Yamakawa，TCC '20）既需要较长的公共参考字符串，又需要非黑盒使用以随机预言机建模的哈希函数。在技术层面，我们重新审视了构建经典可验证量子计算的框架（Mahadev，FOCS '18）。我们为 Mahadev 的协议提供了一个独立的模块化安全性证明，我们认为这是有独立意义的。我们的证明很容易推广到验证者的第一条消息（包含许多公钥）被压缩的场景。接下来，我们将压缩公钥的概念形式化；我们将该对象视为受限/可编程 PRF 的泛化，并基于不可区分混淆对其进行实例化。最后，我们使用（足够可组合的）NP 简洁知识论证将上述协议编译成完全简洁的论证。使用我们的框架，我们获得了几个额外的结果，包括 - QMA 的简洁论证（给定见证的多个副本）， - 量子随机预言模型中 BQP（或 QMA）的简洁非交互式论证，以及 - 假设后量子 LWE（无 iO）的 BQP（或 QMA）的简洁批处理论证。
改进了量子Gibbs状态的热区法律和准线性时间算法
量子多体物理学中最根本的问题之一是热状态之间相关性的表征。是热区定律，它证明了张量网络近似与系统大小多项式生长的键尺寸的热状态。在足够低温的制度中，这对于实际应用至关重要，现有技术不会产生最佳界限。在这里，我们提出了一项新的热区法律，该法律适用于晶格上的通用多体系统。我们提高了从原始OðβÞ到Oðβ2= 3 = 3到对数因子的温度依赖性，从而提出了通过假想时间演化对纠缠的副球传播。这种定性与实时演化有所不同，这通常会诱导纠缠的线性生长。我们还证明了纯化和形成的纠缠的R'enyi纠缠的类似界限。我们的分析是基于对指数函数的多项式近似，该函数提供了假想时间演化与随机步行之间的关系。此外，对于带有N旋转的一维（1D）系统，我们证明了Gibbs状态由矩阵乘积运算符近似，具有sublinear键尺寸的β¼O½logðnÞ的均方根键尺寸。此证明使我们能够首次严格建立一种准时的经典算法，用于在β¼o½logðnÞ的任意温度下构建1D量子gibbs状态的矩阵量态表示。350 - 360]。我们的新技术成分是Gibbs状态的块分解，与Haah等人给出的实时进化的分解相似。[2018年IEEE第59届计算机科学基础年度研讨会（IEEE，纽约，2018年），pp。
通过经典信道进行安全的双方量子计算
摘要。安全的双方计算考虑双方计算其私有输入的联合函数而不透露计算输出以外的任何内容的问题。在这项工作中，我们迈出了理解以下情况的第一步：1）双方（Alice 和 Bob）只能通过经典信道进行通信，2）Bob 的输入是量子的，3）Alice 的输入是经典的。我们的第一个结果表明，在这种情况下，在恶意量子对手的情况下，通常不可能通过黑盒模拟实现双方量子功能。特别是，我们表明，仅依赖经典信道的安全量子计算协议的存在将与量子不可克隆论证相矛盾。我们通过三种不同的方法规避了这种不可能性。第一种方法是考虑一种较弱的安全概念，称为单边模拟安全。这个概念以标准的基于模拟的意义保护一方（量子 Bob）的输入，并保护另一方输入（经典 Alice）的隐私。我们展示了如何实现一个依赖于有错学习假设的满足这一概念的协议。第二种规避不可能结果的方法是假设量子输入具有有效的经典表示，同时提供基于标准模拟的安全性以抵御恶意 Bob。最后，我们将注意力集中在零知识函数类上，并提供一个编译器，该编译器以 QMA 关系 R 的经典量子知识证明 (PoQK) 协议作为输入（经典 PoQK 是可以由经典验证者验证的 PoQK），并输出可以由经典方验证的 R 的零知识 PoQK。我们的结果直接意味着 Mahadev 的量子计算经典验证协议 (FOCS'18) 可以转变为具有经典验证者的量子知识零知识证明。据我们所知，我们是第一个实例化这种原语的人。
理论计算机科学中的研究流教师职位
我们邀请有才华学者的申请在理论计算机科学的助理教授级别的终身任期内开始，于2025年7月1日开始。该部门拥有一个强大而活跃的理论小组，成员在TC和相关领域进行研究，包括算法，复杂性，密码学和逻辑。合格的候选人必须拥有博士学位。在计算机科学或同等领域或完成的一年之内，以及展示的研究成就记录，包括顶级国际理论场所的出版物（与苏打水，焦点和STOC相当），以及制定出色的研究计划的明确计划。申请人必须承诺在本科和研究生层面上教学理论课程，并能够在本科层面教授各种课程。优先的教学经验证据。申请人应为研究生监督提供计划，并在监督或指导学生的事先经验中被认为是资产。申请人必须表现出在大学学术环境中运作所需的专业精神，并有合作的证据被认为是资产。候选人的资格，经验和整体市场需求将决定候选人的最终工资要约。该职位的薪水包括助理教授的竞争薪水范围为$ 116,420- $ 143,813。UVIC致力于提供公平且有竞争力的工资，其中包括慷慨的福利计划，合格的叶子和养老金计划。我们积极鼓励来自遇到公平障碍的团体成员的申请。UVIC致力于维护我们的生活，学习和工作环境中的公平，多样性和包容性的价值。在追求我们的价值观时，我们寻求成员，他们将在差异和跨越权力的范围内尊重和建设性地工作。阅读我们的完整权益声明。维多利亚大学一直在加拿大研究密集型大学的顶级排名中排名。我们解决对人，地点和地球重要的基本问题。位于太平洋地区，我们的位置激发了我们以令人兴奋的方式来抗拒边界，发现和创新。我们在下一步的边缘生活，学习，工作和探索 - 对于我们的星球及其人民，尤其是该地区的土著人民。我们尊重Songhees，Esquimalt和Wsáneć人民，在其传统领土上，大学的历史关系一直持续到今天。位于工程和计算机科学学院内的计算机科学系提供了理学学士学位。专业，计算机科学领域的荣誉和次要学位以及与电气和计算机工程部共同提供的软件工程学士学位。它提供了多个联合计划，将计算机科学与地理，健康信息科学，数学，统计，音乐，物理，心理学，统计和视觉艺术相结合。该部门提供硕士和博士课程，目前有125名研究生。目前有34名教职员工，其中包括三位加拿大研究椅，有10张它与电气和计算机工程系共同提供了一年的应用数据科学工程硕士。