标题： 通过递归Oracle扩展的确定性量子搜索 显示英文标题

标题： Deterministic Quantum Search via Recursive Oracle Expansion

摘要： 我们引入了一种新的确定性量子搜索算法，它为传统的概率搜索方法提供了一个实际的替代方案。 我们的方案消除了量子搜索的固有不确定性，而无需依赖任意相位旋转，这是其他确定性方法的一个关键限制。 该算法通过递归扩展基本预言机，使其将与目标具有相同前两位的所有状态标记出来，涵盖恰好四分之一的搜索空间。 这使得可以逐步减少叠加，直到能够确定地测量目标状态。 该算法以查询复杂度为$O(N^{\log_2(3)/2}) \approx O(N^{0.7925})$实现确定性成功，介于格罗弗的$O(\sqrt{N})$缩放和经典$O(N)$之间。 我们的方法仅依赖于两量子比特最近邻扩散算子，完全避免了全局扩散。 我们证明，尽管查询复杂度增加，但对于至少18个量子比特的搜索空间，这种设计将扩散所需的两量子比特门总数减少了数量级，而在量子比特连接有限的硬件上优势更大。 该方案的固有确定性、对简单最近邻低深度操作的依赖以及可扩展的递归结构，使其非常适合硬件实现。 此外，我们表明该算法自然支持部分数据库搜索，能够在不进行完整搜索的情况下确定性地识别选定的目标位，进一步拓宽其适用性。 显示英文摘要

摘要： We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of $O(N^{\log_2(3)/2}) \approx O(N^{0.7925})$, falling between Grover's $O(\sqrt{N})$ scaling and the classical $O(N)$. Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.