Optimal phase change for a generalized Grover's algorithm

• URL: http://arxiv.org/abs/2509.20610v1
• Date: Wed, 24 Sep 2025 23:12:20 GMT
• Title: Optimal phase change for a generalized Grover's algorithm
• Abstract summary: We study the generalized Grover's algorithm with an arbitrary amplitude vector.<n>We find that a phase change of $pi$ stays optimal until the probability of observing the target is quite close to 1.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the generalized Grover's algorithm with an arbitrary amplitude vector to find the optimal phase change for maximizing the gain in probability for the target of each iteration. In the classic setting of Grover's algorithm with a real initial amplitude vector, we find that a phase change of $\pi$ stays optimal until the probability of observing the target is quite close to 1. We provide a formula for identifying this cut-off point based on the size of the data set. When the amplitude is truly complex, we find that the optimal phase change depends non-trivially on the complexity of the amplitude vector. We provide an optimization formula to identify the required optimal phase change.

Related papers

• On the conditional equivalence of phase retrieval algorithms [0.34376560669160394]
  We show that the GS magnitude replacement step is exactly a unit gradient descent step on an amplitude least-squares loss.<n>This equivalence enables seamless integration of classical phase retrieval with differentiable physics pipelines.
  arXiv  Detail & Related papers  (2026-06-05T13:31:52Z)
• Phase Matching for a Generalized Grover's Algorithm [0.0]
  We study the fully generalized Grover's algorithm to find the optimal phase changes for each step of the iteration.<n>We show that for the final iteration the optimal phase changes differ from traditional Grover's algorithm and do not observe phase matching.
  arXiv  Detail & Related papers  (2026-05-13T16:39:34Z)
• Orthogonal Approximate Message Passing Algorithms for Rectangular Spiked Matrix Models with Rotationally Invariant Noise [4.705915211123485]
  We propose an approximate message passing (OAMP) algorithm for signal estimation in the rectangular spiked matrix model.<n>We establish a rigorous state evolution that exactly characterizes the high-dimensional dynamics of the algorithm.<n>Building on this framework, we derive an optimal variant of OAMP that minimizes the predicted mean-squared error at each iteration.
  arXiv  Detail & Related papers  (2026-02-03T09:06:20Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Enhancing Grover's Search Algorithm: A Modified Approach to Increase the Probability of Good States [0.0]
  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.
  arXiv  Detail & Related papers  (2024-01-31T04:55:06Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing Univariate Linear Losses [0.0]
  We show that the optimal mapping between score values and the target region is a rectangular function. Our approach has logarithmic time complexity per iteration and is optimally efficient.
  arXiv  Detail & Related papers  (2023-04-04T22:00:40Z)
• 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)
• Amplitude Amplification for Optimization via Subdivided Phase Oracle [0.9176056742068814]
  We propose an algorithm using a modified variant of amplitude amplification to solve optimization problems. We show via numerical simulation that for normal, skew normal, and exponential distribution of objective values, the algorithm can be used to amplify the probability of measuring the optimal solution.
  arXiv  Detail & Related papers  (2022-05-02T01:14:27Z)
• 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)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Deriving Differential Target Propagation from Iterating Approximate Inverses [91.3755431537592]
  We show that a particular form of target propagation, relying on learned inverses of each layer, which is differential, gives rise to an update rule which corresponds to an approximate Gauss-Newton gradient-based optimization. We consider several iterative calculations based on local auto-encoders at each layer in order to achieve more precise inversions for more accurate target propagation.
  arXiv  Detail & Related papers  (2020-07-29T22:34:45Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.