Qisheng Wang, Mingsheng Ying. Quantum Algorithm for Lexicographically Minimal String Rotation (2022)
Posted on
Edited on
Abstract. 本文是 https://doi.org/10.1007/s00224-023-10146-8 的阅读笔记。他们提出了求字符串最小字典序后缀的 $O(n^{3/4})$ 量子算法，但感觉非常套路。文章还证明了这个问题的平均复杂度下界 $\Omega(n^{1/2} / \log^{1/2} n)$ 和最坏复杂度下界 $\Omega(n^{1/2})$，但他自己并没有达到这个界。
关于管乐器泛音演奏（超吹）的一些探究
Abstract. 本文是 2024 秋季学期音乐与数学大作业的笔记，研究题目是“管乐器的超吹”，尤其是为何开管乐器能够吹出偶数倍泛音，闭管乐器只能够吹出奇数倍泛音，而锥形管乐器看似和闭管相同，但实际上也能吹出偶数倍泛音。对管乐器的分类参见第 3，第 4 节。
警告： 本文可能包含如下要素：
- 随便忽略高阶小量。
- 随便使用对称性。
- 随便交换微分算子。
- 对着参考文献人云亦云。
如您无法接受这些操作，我们推荐您不要阅读此文。
【Hanged】Shyan Akmal, Ce Jin. Near-Optimal Quantum Algorithms for String Problems
Abstract. 解决了三个问题：最长公共子串、最小字典序循环移位、最长平方子串。暂时只看懂了最小字典序循环移位。
【Under Construction】Yoder, Low, Chuang. Fixed-point quantum search with an optimal number of queries
Abstract.
H. Ramech, V.Vinay. String matching in $\tilde{O}(\sqrt n + \sqrt m)$ quantum time (2003)
Abstract. 本文是 https://doi.org/10.1016/S1570-8667(03)00010-8 的阅读笔记。他们尝试把 https://doi.org/10.1137/0220002 的技术用在了量子计算机上，发现很有道理。很遗憾的是作者好像不是量子计算从业者，他们的很多 approach 都是有问题的，但也不是不能修复。因为他的思路非常 trivial，所以我们有精力帮他们重新算一遍。最后一节“处理周期性串”看起来比较对，但我们放弃仔细验证了。
Uzi Vishkin. Deterministic Sampling–A New Technique for Fast Pattern Matching (1991)
Abstract. 本文是 https://doi.org/10.1137/0220002 的阅读笔记。文中提出了一种确定性的采样方法用于加速字符串匹配，由此得到了操作次数 $O(n)$ 时间 $O(\log^* n)$ 的并行算法。
文中用到了大量的分治、分块、复杂度平衡、递归的技巧，虽然这些无非是思考并行算法的时候的重点考虑方向，但第一次见的时候感觉还是比较奇妙，整个论文读完像做了一道超大的构造题。
Revision | 抽象代数小常识
Abstract. 本文实际上是离散数学与结构上半学期的笔记整理。本课实际上包含了其他内容，比如朴素集合论中的势理论，命题逻辑，一阶逻辑及（不）完备定理，在合集 category: Discrete Math 中有所收录，不再重复。本文只写抽象代数的内容。
本文最后一节有许多定理的证明有待补充，包括后两条 Sylow 定理的证明，分裂域相关理论，和最后因子分解算法中关于 $\pm 1$ 出现概率均等的断言。