论文标题
用于识别具有矩形问题应用的隐藏字符串的量子算法
Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems
论文作者
论文摘要
在本文中，我们探索了该问题的量子加速，灵感来自原始理论，以使用最大内部产品甲骨文和子甲级甲骨文来识别一对$ n $ bit的二进制字符串，并承诺具有相同数量的1s，并且在两个位上完全不同。更具体地说，给定两个字符串$ s，s'\ in \ {0，1 \}^n $满足上述约束，对于任何$ x \ in \ {0，1 \}^n $ max ninen Inner Product ucle oracle oracle oracle oracle oracle of o_ {max}（max}（x）$ $ o_ {sub}（x）$指示$ x $中1s的索引集是$ s $还是$ s'$中的一个子集。我们提出了一种消耗$ o（1）$查询的量子算法，以识别$ \ {s，s'\} $，并证明任何经典算法都需要$ω（n/\ log_ {2} n）$ queries。另外，我们提出了一种消耗$ \ frac {n} {2}+o（\ sqrt {n}）$ QUERIES $ QUERIES的量子算法，并证明任何经典算法都需要至少$ n+ω（1）$ QUERIES。因此，在两个Oracle模型中揭示了量子加速。此外，以上结果适用于Matroid理论的问题，即找到2个基线的Matroid的所有基础，如果它具有$ K $ bases，则矩阵称为$ k $ base。
In this paper, we explore quantum speedups for the problem, inspired by matroid theory, of identifying a pair of $n$-bit binary strings that are promised to have the same number of 1s and differ in exactly two bits, by using the max inner product oracle and the sub-set oracle. More specifically, given two string $s, s'\in\{0, 1\}^n$ satisfying the above constraints, for any $x\in\{0, 1\}^n$ the max inner product oracle $O_{max}(x)$ returns the max value between $s\cdot x$ and $s'\cdot x$, and the sub-set oracle $O_{sub}(x)$ indicates whether the index set of the 1s in $x$ is a subset of that in $s$ or $s'$. We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $\{s, s'\}$, and prove that any classical algorithm requires $Ω(n/\log_{2}n)$ queries. Also, we present a quantum algorithm consuming $\frac{n}{2}+O(\sqrt{n})$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+Ω(1)$ queries. Therefore, quantum speedups are revealed in the two oracle models. Furthermore, the above results are applied to the problem in matroid theory of finding all the bases of a 2-bases matroid, where a matroid is called $k$-bases if it has $k$ bases.
