← 研踪 PaperTrailarXiv:2611.17541 · v1
Quantum Algorithm with Quadratic Speedup for 2D Pattern Matching
首次提交 2026-11-13 05:50
版本更新 2026-11-13 05:50
雷达观测 2026-11-17 04:58
摘要
We consider the problem of 2 dimensional pattern matching under Quantum Query model. Here, we are given a rectangular text and a pattern . We take and as the sizes of text and the pattern respectively (we assume ). Based upon the Quantum Advantage given by Grover's search (and subsequent Dürr-Høyer search), we create a solution which takes query complexity to answer if the pattern exists in . Our solution uses deterministic sampling as a primary component. As noted by earlier work in the literature, deterministic sampling is inadequate and witness tables are essential components for 2D matching. In our settings, we assume that the witness table of the pattern is precomputed classically and is available as an oracle to the quantum algorithm. Our main novel component is how to compute and employ a geometric structure called ``skyline" without losing the quantum advantage.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-13 05:50 · 最新观测版本
Quantum Algorithm with Quadratic Speedup for 2D Pattern Matching
We consider the problem of 2 dimensional pattern matching under Quantum Query model. Here, we are given a rectangular text and a pattern . We take and as the sizes of text and the pattern respectively (we assume ). Based upon the Quantum Advantage given by Grover's search (and subsequent Dürr-Høyer search), we create a solution which takes query complexity to answer if the pattern exists in . Our solution uses deterministic sampling as a primary component. As noted by earlier work in the literature, deterministic sampling is inadequate and witness tables are essential components for 2D matching. In our settings, we assume that the witness table of the pattern is precomputed classically and is available as an oracle to the quantum algorithm. Our main novel component is how to compute and employ a geometric structure called ``skyline" without losing the quantum advantage.
查看此版本解读 →查看此版本原文 ↗