Improving D2p Grover's algorithm to reach performance upper bound under
phase noise
- URL: http://arxiv.org/abs/2305.12300v1
- Date: Sat, 20 May 2023 23:49:31 GMT
- Title: Improving D2p Grover's algorithm to reach performance upper bound under
phase noise
- Authors: Jian Leng, Fan Yang, Xiang-Bin Wang
- Abstract summary: Grover's algorithm has a success probability to output a correct solution.
The success probability of deterministic Grover's algorithm decreases in noisy environment.
We prove that it is not possible to design any deterministic Grover's algorithm whose success probability is higher than our improved D2p protocol's under phase noise.
- Score: 3.803244458097104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The original Grover's algorithm has a success probability to output a correct
solution, while deterministic Grover's algorithms improve the success
probability to 100%. However, the success probability of deterministic Grover's
algorithm decreases in noisy environment. Here we improve the deterministic
two-parameter (D2p) Grover's algorithm to reach the upper bound for success
probability under phase noise. We prove that it is not possible to design any
deterministic Grover's algorithm whose success probability is higher than our
improved D2p protocol's under phase noise.
Related papers
- Near-deterministic quantum search algorithm without phase control [10.754825115553086]
Grover's algorithm can find the target item with certainty only if searching one out of four.
We propose a near-deterministic quantum search algorithm without the phase control.
arXiv Detail & Related papers (2024-07-15T14:20:47Z) - Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
This work is motivated by the growing demand for reproducible machine learning.
In particular, we consider a replicable algorithm that ensures, with high probability, that the algorithm's sequence of actions is not affected by the randomness inherent in the dataset.
arXiv Detail & Related papers (2024-02-12T03:31:34Z) - Quantum Advantage of Noisy Grover's Algorithm [3.803244458097104]
Grover's search algorithm is the only quantum algorithm with proven advantage to any possible classical search algorithm.
We present a noise-tolerant method that exponentially improves the noise threshold of Grover's algorithm.
arXiv Detail & Related papers (2023-06-19T11:17:32Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth.
We consider two kinds of zero-order projected gradient descent algorithms.
arXiv Detail & Related papers (2023-06-03T17:05:13Z) - Deterministic Grover search with a restricted oracle [2.976027966501599]
Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms.
We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.
arXiv Detail & Related papers (2022-01-01T02:04:11Z) - Performance of Grover's search algorithm with diagonalizable collective
noises [0.0]
Grover's search algorithm (GSA) is known to experience a loss of its quadratic speedup when exposed to quantum noise.
We show that the performance of GSA can be improved by certain types of noise, such as bit flip and bit-phase flip noise.
arXiv Detail & Related papers (2021-11-24T01:29:20Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
We study the fundamental online $k$-server problem in a learning-augmented setting.
We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
arXiv Detail & Related papers (2021-03-02T11:04:33Z) - Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with
Advanced Decomposition of $n$-qudit Toffoli Gate [2.9923891863939938]
Grover's algorithm can be extended to a $d$-ary (qudit) quantum system.
An $n$-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm.
arXiv Detail & Related papers (2020-12-08T14:33:04Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
We consider a best arm identification (BAI) problem for Sequential bandits with adversarial corruptions in the fixed-budget setting of T steps.
We design a novel randomized algorithm, Probabilistic Shrinking($u$) (PSS($u$)), which is agnostic to the amount of corruptions.
We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to $1$ as $Trightarrow infty$.
arXiv Detail & Related papers (2020-10-15T17:34:26Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
We show that the regret of the corralling algorithms is no worse than that of the best algorithm containing the arm with the highest reward.
We show that the gap between the highest reward and other rewards depends on the gap between the highest reward and other rewards.
arXiv Detail & Related papers (2020-06-16T15:33:12Z) - Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
We study the multi-armed bandit problem with subgaussian rewards.
We show that a variant of the explore-then-commit (ETC) algorithm can achieve the optimality for multi-armed bandit problems.
arXiv Detail & Related papers (2020-02-21T08:07:56Z)
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.