本文研究分圆环上的格问题计算复杂性。具体而言，作者证明了在二维全秩自由子模上，以 ℓ2-范数定义的判定型最短向量问题（SVP）是 NP-完全的。设 q 为模 4 余 3 的素数，ζ_q 为本原 q 次单位根，K=Q(ζ_q)，环 O_K=Z[ζ_q]。固定模秩为 2，但作为 Z-格，秩为 2(q-1)，随 q 增长。主要障碍是 O_K 作用下的封闭性：模块中任一非零向量蕴含其所有 O_K 标量倍，其中一些可能更短，从而干扰判定。作者提出三个关键思路克服该障碍：1) 将 Bennett-Peikert Reed-Solomon 格映射到主分圆理想，并利用 Wan 的点计数估计证明该理想的陪集含大量二进制系数表示；2) 基于二次高斯和的“检查器”将 X3C（精确覆盖三集）方程转化为规范化平方范数；3) 检查器与第二模坐标结合，利用理想陪集分离界限排除 O_K 作用产生的所有非预期向量。每个构造实例包含素数 q≡3 mod 4、两个非零行列式的积分生成元、以及一个整数平方阈值。该构造还通过多项式时间 Turing 归约给出 search-SVP 的 NP-难性。该工作属于密码学与计算复杂性理论交叉领域，对基于格的密码学（尤其 cyclotomic 结构）安全性分析有理论意义。适合对格基密码、计算复杂性理论、代数数论感兴趣的科研人员阅读。

本文研究量子计算中的酉算子合成问题。该问题由Aaronson和Kuperberg于CCC 2007年提出，核心是判断是否每个n量子比特酉算子U都能通过相对于某个依赖于U的经典预言机的高效量子电路来计算。最近，Lombardi、Ma和Wright（STOC 2024）证明了Haar随机酉算子无法被仅进行1次查询或多项式次并行查询任意经典预言机的算法高效合成。本文在此基础上，对多个变体进行了系统的困难性与易处理性分析，主要贡献包括：（1）1查询与2查询酉合成的显式分离：作者证明合成随机置换酉算子和随机交替基相位酉算子需要至少1次查询的下界，而这些酉算子具有高效的2查询合成算法，从而为“显式”酉算子族提供了查询复杂度的分离。（2）复相位酉算子的上界：对于形式为|x⟩→α_x|x⟩的复相位酉算子，已知存在简洁的2查询合成算法，但未发现明显的1查询算法。本文证明存在相对于二进制相位预言机的1查询算法，可在钻石距离下常数逼近这类酉算子。（3）为证明下界，作者引入了两个新的密码学博弈：预言机态搜索博弈和预言机Choi态博弈。与先前工作相比，该框架在数学上更简单、更具灵活性，并能更精确地刻画非完全随机酉算子的合成难度。（4）利用搜索博弈，作者还证明了量子程序（即相对于量子建议合成酉算子）对相位酉算子的近似困难性新结果，给出了1查询酉合成与量子程序之间更尖锐的分离。这些结果加深了对量子计算中酉合成问题计算复杂性的理解，为量子算法设计与复杂性理论提供了新的技术工具。

本文研究PSPACE语言的高效交互式证明系统。经典结论IP=PSPACE表明任何PSPACE语言都存在交互式证明，但验证者高效时，证明者可能需要指数时间。后续工作致力于构造“加倍高效”的证明系统，即证明者时间为T(n)的多项式，验证者时间为输入长度n的多项式。此前最好结果由Berger等人（FOCS 2025）实现，将T(n)的上界拓展至n^{O(√(log n / log log n))}。本文将该上界进一步大幅提升至n^{O(log n)}，即任何T(n)=n^{O(log n)}时间内可判定的PSPACE语言均存在加倍高效的证明系统。方法上，不同于先前通过批量交互证明间接构造的复杂方案，本文直接构造了验证协议，不仅简化了证明过程，也为未来改进提供了更清晰的路径。实验上，本文是理论证明，无需实际实验。主要贡献：1）扩展了加倍高效证明系统的适用范围；2）提出了更简洁的直接构造方法；3）推动了复杂度理论中交互式证明的研究。适合理论计算机科学、密码学、复杂度理论研究者阅读。