Hindlycke Christoffer, Johansson Niklas, Larsson Jan-Åke
Department of Electrical Engineering, Linköping University, 581 83 Linköping, Sweden.
Entropy (Basel). 2025 Jun 2;27(6):596. doi: 10.3390/e27060596.
Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin-Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.
递归傅里叶采样（RFS）是最早展示量子优势的问题之一，并且已知它不属于梅林-亚瑟复杂度类。这项工作包含了用相空间术语对量子算法的新描述，展示了其在RFS中的应用，以及这如何以及为何能更好地理解RFS中的量子优势。最重要的是，用相空间术语描述量子计算的过程能让人更好地理解为什么在解决RFS时取消计算是必要的：只有当相坐标垃圾被取消计算时优势才会出现。这就是量子优势存在局限性的根本原因。
