Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
该论文研究 F_3^n 上的向量子集和问题：给定 m 个取自 F_3^n 的随机向量，要求找出一个非空子集使其向量和为零；m 越小，问题越难。该问题与后量子密码（尤其是基于 LWE 的构造）以及组合优化密切相关，也是量子优势研究中的经典试验
#complexity-theory
共收录 13 条相关情报。
← 返回所有主题Need for Coherent Access in Constructing Quantum Cryptography
该论文研究量子密码学中伪随机态（PRS）构造的可实现性问题，属于量子计算复杂性理论中的黑盒分离（oracle separation）研究。已知结论表明，存在从量子安全单向函数（quantum-secure OWF）构造 PRS 生成器的黑盒
Verifiable quantum advantage based on polynomials with planted structures
该论文研究的是量子优势（quantum advantage）理论中的一个核心开放问题：是否存在一类量子优势协议，其资源需求与随机电路采样（random circuit sampling, RCS）相当，同时又能仅凭量子计算输出的经典数据被经
Path-Finding, Orbit State Preparation, and the Security of Invariant Quantum Money
本文研究基于纽结（knot）的量子货币及其推广形式——不变量货币（invariant money）的安全性基础。这类方案的核心假设是「路径搜索困难」：给定两个具有相同不变量的等价对象（例如两个纽结），找到它们之间的一串等价变换（move）是
Computational Cryptography from Pseudoentanglement
该论文研究量子信息理论与计算密码学的交叉地带，核心问题是：伪纠缠（pseudoentanglement）这一源自计算纠缠理论的资源，能否以及如何转化为密码学意义上的计算困难性。研究背景有两个并行脉络：一是伪纠缠与计算纠缠理论的提出，引发了计
New lower bounds for CDS and $f$-routing
本论文研究非局域量子计算（NLQC, non-local quantum computation）中纠缠代价的下界问题，这一问题与计算复杂性理论、密码学、量子引力等领域相关。NLQC 的一个核心特例是 f-routing，其动机部分来自量子
Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
该论文研究量子算法中「查询次数与内存（量子比特）之间的权衡」这一核心问题。经典背景下，对于均匀随机函数 f:[N]→[N]，BHT 算法用 O(N^{1/3}) 次查询加上一张 O(N^{1/3}) 规模的量子可访问经典表即可找到碰撞，而仅
A Note on Binary Quadratic Systems and their relation to complexity theory
本文研究二元域 F2 上多元二次方程系统（MQ 系统）的解计数及其与复杂度理论的关系。判定一个平方二次系统（方程数等于变量数）是否有解是经典的 NP 完全问题，其困难性是构造后量子密码方案的基石。令 MQ_0(n) 和 MQ_1(n) 分别
Distinctness threshold for pseudorandom unitaries
本文研究量子信息理论中两种伪随机性概念——统计伪随机性（以酉 t-design 为代表）与计算伪随机性（以伪随机酉 PRU 为代表）之间的关系。此前已知的 PRU 构造通常需要将统计随机化成分（如酉 2-design）与经典密码学原语结合，
A Complexity-Theoretic Approach to Proofs of Space
本文提出了一种基于复杂性理论构建空间证明（Proof of Space, PoS）的新框架。空间证明由Dziembowski等人于CRYPTO 2015引入，是一个两阶段协议，允许证明者向高效的验证者证明其已分配大量持久性内存来存储某些信息
Witness Complexity of Short Descriptions: A Cryptographic Perspective
本论文从密码学实践视角出发，系统性地研究了短描述（如密钥、证书）的“可验证复杂性”问题。在密码协议中，密钥或证书通常要求能够在有限时间（多项式时间）内完成展开或验证，否则一个紧凑表示即使理论上存在，也无法在实际有界时间协议中提供操作保障。作
The Observer World: A Cryptographic Extension of Impagliazzo's Five Worlds
本文提出对Impagliazzo五世界理论的一种密码学扩展。Impagliazzo的五世界框架沿着单一轴（即密码原语的存在性）对计算假设进行分类，且所有世界都隐含一个默认假设：包括敌手在内的每一方都观测完整的输入，即观测者始终处于最高层级（
On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
本文研究可扩展伪随机酉矩阵（PRU）的构造问题，即安全性参数可独立于维度（或输入比特长度）变化的PRU族。目前尚不清楚是否存在这样的构造。作者证明，如果通过当前主流范式（随机预言机模型）可以构造可扩展PRU，那么Aaronson-Kuper