Grover search revisited; application to image pattern matching

Abstract

The landmark Grover algorithm for amplitude amplification serves as an essential subroutine in various type of quantum algorithms, with guaranteed quantum speedup in query complexity. However, there have 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.

15 pages, 10 figures

References in corpus (6)

• Quantum random access memory
• Synthesis of Quantum Logic Circuits
• Quantum-state preparation with universal gate decompositions
• Architectures for a quantum random access memory
• Quantum Image Processing and Its Application to Edge Detection: Theory and Experiment
• Implementation of efficient quantum search algorithms on NISQ computers

Cited by in corpus (6)

• Experimental quantum pattern recognition in IBMQ and diamond NVs
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Grover's search meets Ising models: a quantum algorithm for finding low-energy states
• Quantum Optics based Algorithm for Measuring the Similarity between Images
• Grover's Algorithm with Diffusion and Amplitude Steering