On the success probability of quantum order finding
- URL: http://arxiv.org/abs/2201.07791v2
- Date: Mon, 28 Nov 2022 12:31:12 GMT
- Title: On the success probability of quantum order finding
- Authors: Martin Eker{\aa}
- Abstract summary: We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order $r$ in a single run.
Asymptotically, in the limit as $r$ tends to infinity, the probability of successfully recovering $r$ in a single run tends to one.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove a lower bound on the probability of Shor's order-finding algorithm
successfully recovering the order $r$ in a single run. The bound implies that
by performing two limited searches in the classical post-processing part of the
algorithm, a high success probability can be guaranteed, for any $r$, without
re-running the quantum part or increasing the exponent length compared to Shor.
Asymptotically, in the limit as $r$ tends to infinity, the probability of
successfully recovering $r$ in a single run tends to one. Already for moderate
$r$, a high success probability exceeding e.g. $1 - 10^{-4}$ can be guaranteed.
As corollaries, we prove analogous results for the probability of completely
factoring any integer $N$ in a single run of the order-finding algorithm.
Related papers
- Tight Success Probabilities for Quantum Period Finding and Phase Estimation [2.2329417756084093]
We consider a general post-processing algorithm which succeeds whenever the measured $hatell$ is within some tolerance $M$ of a positive integer multiple of $2n / r$.<n>We give new (tight) lower and upper bounds on the success probability that converge to 1.<n>Our analysis allows for the careful exploitation of the tradeoffs between the complexity of the quantum circuit and the effort spent in classical processing when optimizing the probability of success.
arXiv Detail & Related papers (2025-06-25T15:14:59Z) - Even-Cycle Detection in the Randomized and Quantum CONGEST Model [1.5566524830295314]
We show that for every $kgeq 2$, $C_2k$-freeness can be decided in $O(n1-1/k)$ rounds in the CONGEST model.
We also show how to quantize our algorithm for achieving a round-complexity $tilde O(nfrac12-frac12k)$ in the quantum setting.
arXiv Detail & Related papers (2024-02-19T10:23:37Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies.
We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z) - On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
This paper explores a fine-grained version of the Watrous conjecture.
It includes the randomized and quantum algorithms with success probabilities arbitrarily close to $1/2$.
arXiv Detail & Related papers (2023-09-20T13:04:45Z) - On the success probability of the quantum algorithm for the short DLP [0.0]
We prove a lower bound on the probability of Ekeraa-Haastad's algorithm recovering the short $d$ in a single run.
By our bound, the success probability can easily be pushed as high as $1 - 10-10$ for any short $d$.
arXiv Detail & Related papers (2023-09-04T18:26:45Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - 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) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
We propose a new, simplified high probability analysis of AdaGrad for smooth, non- probability problems.
We present our analysis in a modular way and obtain a complementary $mathcal O (1 / TT)$ convergence rate in the deterministic setting.
To the best of our knowledge, this is the first high probability for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness.
arXiv Detail & Related papers (2022-04-06T13:50:33Z) - 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) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
We find an algorithm which finds.
epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using.
$(epsilon,gamma)$surimate random random points.
Our lower bounds here are novel even in the noiseless case.
arXiv Detail & Related papers (2020-06-24T04:41:43Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
This paper analyzes the trajectories of gradient descent (SGD)
We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
arXiv Detail & Related papers (2020-06-19T14:11:26Z) - Revisiting Shor's quantum algorithm for computing general discrete logarithms [0.0]
We show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run.
By slightly increasing the number of group operations that are evaluated quantumly, we show how the algorithm can be further modified to achieve a success probability thatally exceeds 99% in a single run.
arXiv Detail & Related papers (2019-05-22T11:47:38Z)
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.