本文研究量子计算中的酉算子合成问题。该问题由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）推动了复杂度理论中交互式证明的研究。适合理论计算机科学、密码学、复杂度理论研究者阅读。