Matroid

识别隐藏字符串的量子算法及其在拟阵问题中的应用

在本文中，我们探索了受拟阵理论启发的量子加速问题，即使用最大内积预言机和子集预言机来识别一对 n 位二进制字符串，保证它们具有相同数量的 1，并且恰好有两位不同。更具体地说，给定两个满足上述约束的字符串 s，s ′ ∈{0, 1} n，对于任何 x ∈{0, 1} n，最大内积预言机 O max (x) 返回 s·x 和 s ′·x 之间的最大值，子集预言机 O sub (x) 指示 x 中 1 的索引集是否是 s 或 s ′ 中索引集的子集。我们提出了一个量子算法，该算法消耗 O (1) 次查询来获取最大内积预言机，用于识别对 { s, s ′ } ，并证明任何经典算法都需要 Ω( n/ log 2 n ) 次查询。此外，我们提出了一个量子算法，该算法消耗 n