Enhancing Grover's Search Algorithm: A Modified Approach to Increase the Probability of Good States

• URL: http://arxiv.org/abs/2402.00082v4
• Date: Sun, 24 Mar 2024 22:32:53 GMT
• Title: Enhancing Grover's Search Algorithm: A Modified Approach to Increase the Probability of Good States
• Abstract summary: This article introduces an enhancement to the Grover search algorithm to speed up computing the probability of finding good states. It suggests incorporating a rotation phase angle determined mathematically from the derivative of the model during the initial iteration.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This article introduces an enhancement to the Grover search algorithm to speed up computing the probability of finding good states. It suggests incorporating a rotation phase angle determined mathematically from the derivative of the model during the initial iteration. At each iteration, a new phase angle is computed and used in a rotation gate around y+z axis in the diffusion operator. The computed phase angles are optimized through an adaptive adjustment based on the estimated increasing ratio of the consecutive amplitudes. The findings indicate an average decrease of 28% in the required number of iterations resulting in a faster overall process and fewer number of quantum gates. For large search space, this improvement rises to 29.58%. Given the computational capabilities of the computer utilized for the simulation, the approach is applied to instances with up to 12 qubits or 4096 possible combination of search entries.

Related papers

• Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
  Federated matrices bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning.<n>Most existing federated bilevel optimization algorithms require the computation of second-order Hessian and Jacobian matrices.<n>We propose a novel federated convergence variance-reduced bilevel descent algorithm that relies solely on first-order oracles.
  arXiv  Detail & Related papers  (2026-09-14T21:12:59Z)
• Approximating Metric Magnitude of Point Sets [4.522729058300309]
  Metric magnitude is a measure of the "size" of point clouds with many desirable geometric properties. It has been adapted to various mathematical contexts and recent work suggests that it can enhance machine learning and optimization algorithms. In this paper, we study the magnitude problem, and show efficient ways of approximating it. We show that it can be cast as a convex optimization problem, but not as a submodular optimization. The paper describes two new algorithms - an iterative approximation algorithm that converges fast and is accurate, and a subset selection method that makes the computation even faster.
  arXiv  Detail & Related papers  (2024-09-06T17:15:28Z)
• Learning-to-Cache: Accelerating Diffusion Transformer via Layer Caching [56.286064975443026]
  We make an interesting and somehow surprising observation: the computation of a large proportion of layers in the diffusion transformer, through a caching mechanism, can be readily removed even without updating the model parameters. We introduce a novel scheme, named Learningto-Cache (L2C), that learns to conduct caching in a dynamic manner for diffusion transformers. Experimental results show that L2C largely outperforms samplers such as DDIM and DPM-r, alongside prior cache-based methods at the same inference speed.
  arXiv  Detail & Related papers  (2024-06-03T18:49:57Z)
• Proactively incremental-learning QAOA [9.677961025372115]
  We propose an advanced Quantum Approximate Optimization Algorithm (QAOA) based on incremental learning. Our method has superior performance on Approximation Ratio (AR) and training time compared to prevalent works of QAOA.
  arXiv  Detail & Related papers  (2023-11-04T02:15:26Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  We seek to find an ordering that can improve the convergence rates for the non-replacement form of the algorithm. We develop optimal orderings for constant and decreasing step sizes for strongly convex and convex functions. In addition, we are able to combine the ordering with mini-batch and further apply it to more complex neural networks.
  arXiv  Detail & Related papers  (2023-06-28T00:46:58Z)
• 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)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. We propose an accelerated primal-dual mirror descent algorithm with variance reduction. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $widetildeO(n2/epsilon)$ for solving OT.
  arXiv  Detail & Related papers  (2023-01-23T19:13:25Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• Quadratic speedup for simulating Gaussian boson sampling [0.9236074230806577]
  We introduce an algorithm for the classical simulation of Gaussian boson sampling that is quadratically faster than previously known methods. The complexity of the algorithm is exponential in the number of photon pairs detected, not the number of photons. We show that an improved loop hafnian algorithm can be used to compute pure-state probabilities without the need of a supercomputer.
  arXiv  Detail & Related papers  (2020-10-29T13:53:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)

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.