Grover search revisited; application to image pattern matching
arXiv:2108.10854 · doi:10.1103/PhysRevA.105.032440
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.
arXiv comment15 pages, 10 figures
References in corpus (27)
- Quantum Computing in the NISQ era and beyond
- Elementary gates for quantum computation
- Barren plateaus in quantum neural network training landscapes
- Quantum Amplitude Amplification and Estimation
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- Quantum random access memory
- Synthesis of Quantum Logic Circuits
- Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
- qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansatze on a quantum processor
- An initialization strategy for addressing barren plateaus in parametrized quantum circuits
- Quantum-state preparation with universal gate decompositions
- Architectures for a quantum random access memory
- Differentiable Learning of Quantum Circuit Born Machine
- Amplitude estimation without phase estimation
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Quantum Image Processing and Its Application to Edge Detection: Theory and Experiment
- Quantum circuits with uniformly controlled one-qubit gates
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
- Large gradients via correlation in random parameterized quantum circuits
- Black-box quantum state preparation without arithmetic
- Quantum Image Matching
- Correlation-Informed Permutation of Qubits for Reducing Ansatz Depth in VQE
- Tradeoffs in the Quantum Search Algorithm
- Faster Amplitude Estimation
- Implementation of efficient quantum search algorithms on NISQ computers
- Introducing Structure to Expedite Quantum Search
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