Grover search revisited; application to image pattern matching

• URL: http://arxiv.org/abs/2108.10854v2
• Date: Fri, 1 Oct 2021 02:27:06 GMT
• Title: Grover search revisited; application to image pattern matching
• Authors: Hiroyuki Tezuka, Kouhei Nakaji, Takahiko Satoh and Naoki Yamamoto
• Abstract summary: 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.
• Score: 0.8367938108534343
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum Enhanced Pattern Search Optimization [0.0]
  This paper introduces a quantum-classical hybrid algorithm for generalized pattern search (GPS) algorithms. We introduce a quantum search step algorithm using amplitude amplification, which reduces the number of oracle calls needed during the search step from O(N) classical calls to O(N(1/2)) quantum calls.
  arXiv  Detail & Related papers  (2023-05-02T18:13:49Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
  We introduce a quantum-control-inspired method for the characterization of variational quantum circuits using the rank of the dynamical Lie algebra. A promising connection is found between the Lie rank, the accuracy of calculated energies, and the requisite depth to attain target states via a given circuit architecture.
  arXiv  Detail & Related papers  (2022-09-28T20:24:53Z)
• Complement Grover's Search Algorithm: An Amplitude Suppression Implementation [0.5352699766206808]
  Grover's search algorithm was a groundbreaking advancement in quantum algorithms. An extension of Grover's search algorithm is derived where the focus of the query is on the undesirable items. Results are compared against QAOA.
  arXiv  Detail & Related papers  (2022-09-21T16:38:36Z)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  We propose an adaptive algorithm for interval estimation of amplitudes. The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision. We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
  arXiv  Detail & Related papers  (2022-06-16T21:11:15Z)
• Grover's Algorithm with Diffusion and Amplitude Steering [0.0]
  We present a generalization of Grover's algorithm that searches an arbitrary subspace of the multi-dimensional Hilbert space. We also outline a generalized Grover's algorithm that takes into account higher level correlations that could exist between database elements.
  arXiv  Detail & Related papers  (2021-10-21T14:15:32Z)
• A quantum algorithm for gravitational wave matched filtering [0.0]
  We propose the application of a quantum algorithm for the detection of unknown signals in noisy data. In comparison to the classical method, this provides a speed-up proportional to the square-root of the number of templates. We demonstrate both a proof-of-principle quantum circuit implementation, and a simulation of the algorithm's application to the detection of the first gravitational wave signal GW150914.
  arXiv  Detail & Related papers  (2021-09-03T13:58:58Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs.
  arXiv  Detail & Related papers  (2020-06-15T13:40:07Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.