Exact results on Quantum search algorithm
- URL: http://arxiv.org/abs/2207.09762v2
- Date: Fri, 29 Jul 2022 09:46:18 GMT
- Title: Exact results on Quantum search algorithm
- Authors: Saptarshi Roy Chowdhury and Swarupananda Pradhan
- Abstract summary: We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator.
We quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise.
- Score: 0.34376560669160383
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We generalize Grover algorithm with two arbitrary phases in a density matrix
set up. We give exact analytic expressions for the success probability after
arbitrary number of iteration of the generalized Grover operator as a function
of number of iterations, two phase angles ({\alpha}, \{beta}) and parameter
{\xi} introduced in the off diagonal terms of the density matrix in a sense to
capture the coherence present in the initial quantum register. We extend Li and
Li's idea and show for the phase matching condition {\alpha} = -\{beta} =
0.35{\pi} with two iterations and {\xi} = 1, we can achieve success probability
>= 0.8 only with a knowledge about the lower bound of {\lambda} = 0.166 where
{\lambda} is the ratio of marked to total number states in the database.
Finally we quantify success probability of the algorithm with decrease in
coherence of the initial quantum state against modest noise in this simple
model.
Related papers
- Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
We present quantum algorithms for sampling from nonlogconcave probability distributions.
$f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
arXiv Detail & Related papers (2023-10-17T17:55:32Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance.
No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
arXiv Detail & Related papers (2023-07-02T05:03:38Z) - On adaptive low-depth quantum algorithms for robust multiple-phase
estimation [11.678822620192438]
We present robust multiple-phase estimation (RMPE) algorithms with Heisenberg-limited scaling.
These algorithms are particularly suitable for early fault-tolerant quantum computers.
arXiv Detail & Related papers (2023-03-14T17:38:01Z) - Even shorter quantum circuit for phase estimation on early
fault-tolerant quantum computers with applications to ground-state energy
estimation [5.746732081406236]
We develop a phase estimation method with a distinct feature.
The total cost of the algorithm satisfies the Heisenberg-limited scaling $widetildemathcalO(epsilon-1)$.
Our algorithm may significantly reduce the circuit depth for performing phase estimation tasks on early fault-tolerant quantum computers.
arXiv Detail & Related papers (2022-11-22T03:15:40Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow.
In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems.
arXiv Detail & Related papers (2022-09-09T07:43:46Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
We study the problem of high-dimensional sparse mean estimation in the presence of an $epsilon$-fraction of adversarial outliers.
Our algorithms follow the Sum-of-Squares based, to algorithms approach.
arXiv Detail & Related papers (2022-06-07T16:49:54Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
We show how to generalize the quantum approximate counting technique developed by Brassard, Hoyer and Tapp [ICALP 1998] to estimating the number of marked states of a Markov chain.
This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha.
arXiv Detail & Related papers (2022-04-06T03:04:42Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - All-or-nothing statistical and computational phase transitions in sparse
spiked matrix estimation [35.035853993422506]
We analyze the approximate message passing algorithm in a sparse regime.
We find all-or-nothing phase transitions for the minimum and mean-square errors.
In the sparse regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing.
arXiv Detail & Related papers (2020-06-14T18:38:34Z)
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.