Grover search revisited: Application to image pattern matching

Hiroyuki Tezuka, Kouhei Nakaji, Takahiko Satoh, Naoki Yamamoto

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


The landmark Grover algorithm for amplitude amplification serves as an essential subroutine in various types of quantum algorithms, with guaranteed quantum speedup in query complexity. However, there has been no proposal to realize the original motivating application of the algorithm, i.e., the database search or more broadly the pattern matching in a practical setting, mainly due to the technical difficulty in efficiently implementing the data loading and amplitude amplification processes. In this paper, we propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit, together with the easily implementable inversion-test operation for realizing the projected quantum state having similarity to the query data, followed by the amplitude amplification operation that is independent to the target data index. We provide a thorough demonstration of the algorithm in the problem of image pattern matching.

Original languageEnglish
Article number032440
JournalPhysical Review A
Issue number3
Publication statusPublished - 2022 Mar

ASJC Scopus subject areas

  • Atomic and Molecular Physics, and Optics


Dive into the research topics of 'Grover search revisited: Application to image pattern matching'. Together they form a unique fingerprint.

Cite this