Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
该论文研究如何在标准模型下用密码学手段让经典验证者确认量子设备确实展现了量子优势，并对一般的 BQP 计算做经典验证。作者以量子不可区分混淆（qiO）为核心工具构造了三类协议。第一，在假设 qiO 存在、且 BQP≠BPP 的一个略强变体成
#theory
共收录 13 条相关情报。
← 返回所有主题Quantum Secret Sharing and Error Correction vs No-Cloning
该论文研究量子秘密共享（QSS）在「多份输入副本」设定下的可行性与不可能性边界。经典秘密共享中，任意访问结构都可行，阈值结构更有高效协议；但进入量子设定后，不可克隆定理（no-cloning）使大量访问结构变得不可能，而且对阈值结构而言，不
Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold
该论文研究一个源自密码学理论的基础问题：关于哈希函数的结构性知识，能否加速对它的黑盒碰撞检测？作者从「实例最优性」（instance optimality）这一超越最坏情况分析的极端标准切入。实例最优性要求存在单一算法，使其在每一个具体输入
An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting
本笔记是一篇数学论证性的综述/讲解文章，作者 Jalaj Upadhyay 针对差分隐私（DP）持续计数（continual counting）问题的下界证明，给出了尽可能详尽的推导说明。所谓持续计数，是指在数据流持续到达的场景下，每一次到
Witness Encryption via Prime-Order Generic Groups
该论文研究如何在不依赖不可区分混淆(iO)、多线性映射等强假设的前提下构造 NP 的见证加密(Witness Encryption, WE)。WE 允许发送方针对某个 NP 陈述 x 加密消息：持有 x 的有效见证者可解密，而当 x 不属于
Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
本文研究量子计算背景下伪随机原语之间的结构性关系，重点考察伪随机状态生成器（PRSG）、伪随机函数型状态生成器（PRFSG）与伪随机酉（PRU）是否可以相互推出。核心问题是：量子态的伪随机性是否足以构造量子酉的伪随机性？作者给出了一个完整的
Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
本文从形式语言理论的角度重新审视 Emil Post 提出的“生产性集合”(productive set) 概念，并据此构造出本质上不可判定的形式文法。背景上，Post 证明存在这样一类自然数集合：它们不是递归可枚举的，甚至连半可计算都做不
Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
差分隐私（Differential Privacy）为数据分析提供严格的隐私保证，但在回答大量线性查询时，必须在隐私预算、响应精度和随机位数之间权衡。经典机制（如 Hardt 与 Talwar 提出的 K-范数机制）虽能在给定隐私预算 ε
Equivalence Between Average-Case Hardness of Learning and Cryptography for Mixed Quantum States
该论文从理论计算机科学的角度，系统研究了量子机器学习中“平均情况困难性”与“密码学原语”之间的深层联系。传统上，经典密码学与学习理论之间存在著名的双向蕴含关系：密码学原语可推导出学习问题的困难性，而学习问题的困难性又可反过来构造密码方案。近
The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
本文研究了差分隐私（Differential Privacy, DP）下的持续计数问题（Continual Counting）。问题设定是：给定一个长度为 n 的二进制流，每个 1 代表一个个体的贡献，目标是在保护每个个体隐私的前提下，发布
Towards a Doubly Efficient IP=PSPACE
本文研究PSPACE语言的高效交互式证明系统。经典结论IP=PSPACE表明任何PSPACE语言都存在交互式证明，但验证者高效时，证明者可能需要指数时间。后续工作致力于构造“加倍高效”的证明系统，即证明者时间为T(n)的多项式，验证者时间为
Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses
本文研究了机器学习中的“遗忘”（unlearning）问题，即如何从已训练好的模型中移除某个用户数据的影响，以满足如“被遗忘权”等法律和用户需求。针对光滑强凸损失函数下的随机优化场景，前期工作已经提出了一些遗忘算法及其误差界，但遗忘的统计代
Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost
本文研究在诚实但好奇的服务器场景下，通过本地差分隐私（LDP）对 n 个用户持有的数值进行私有求和估计。传统上，本地差分隐私要求每个用户独立添加噪声，导致估计精度远低于集中式差分隐私（CDP）——后者在汇总数据后统一添加噪声。本文证明这一精