Tight Success Probabilities for Quantum Period Finding and Phase Estimation

• URL: http://arxiv.org/abs/2506.20527v2
• Date: Thu, 03 Jul 2025 19:14:18 GMT
• Title: Tight Success Probabilities for Quantum Period Finding and Phase Estimation
• Authors: Malik Magdon-Ismail, Khai Dong,
• Abstract summary: 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.
• Score: 2.2329417756084093
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Period finding and phase estimation are fundamental in quantum computing. Prior work has established lower bounds on their success probabilities. Such quantum algorithms measure a state $|\hat\ell\rangle$ in an $n$-qubit computational basis, $\hat\ell \in [0, 2^n - 1]$, and then post-process this measurement to produce the final output, in the case of period finding, a divisor of the period $r$. We consider a general post-processing algorithm which succeeds whenever the measured $\hat\ell$ is within some tolerance $M$ of a positive integer multiple of $2^n / r$. We give new (tight) lower and upper bounds on the success probability that converge to 1. The parameter $n$ captures the complexity of the quantum circuit. The parameter $M$ can be tuned by varying the post-processing algorithm (e.g., additional brute-force search, lattice methods). Our tight 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. We note that the most recent prior work in most recent work does not give tight bounds for general $M$.

Related papers

• Bounds on a Wavefunction Overlap with Hamiltonian Eigen-states: Performance Guarantees for the Quantum Phase Estimation Algorithm [0.0]
  Estimating the overlap between an approximate wavefunction and a target eigenstate of the system Hamiltonian is essential for the efficiency of quantum phase estimation.<n>We derive upper and lower bounds on this overlap using expectation values of Hamiltonian powers and bounds on target eigenenergies.
  arXiv  Detail & Related papers  (2025-03-15T18:24:12Z)
• Quantum Approximate $k$-Minimum Finding [2.810947654192424]
  We propose an optimal quantum $k$-minimum finding algorithm that works with approximate values for all $k geq 1$.<n>We present efficient quantum algorithms for identifying the $k$ smallest expectation values among multiple observables and for determining the $k$ lowest ground state energies of a Hamiltonian.
  arXiv  Detail & Related papers  (2024-12-21T11:21:15Z)
• Partition function estimation with a quantum coin toss [0.0]
  Estimating quantum partition functions is a critical task in a variety of fields.<n>This paper introduces a quantum algorithm for estimating the partition function $Z_beta$ of a generic Hamiltonian $H$ up to multiplicative error.
  arXiv  Detail & Related papers  (2024-11-26T19:01:19Z)
• A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques [0.0]
  In recent years, quantum algorithms have been proposed which use quantum phase estimation coherently as a subroutine without measurement. We show that the use of the Kaiser window function is currently the most practical choice for realizing QPE with high success probability.
  arXiv  Detail & Related papers  (2024-04-01T18:08:10Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Search for Multiple Adjacent Marked Vertices on the Hypercube by a Quantum Walk with Partial Phase Inversion [3.8436076642278754]
  We analyze the application of the Multi-self-loop Lackadaisical Quantum Walk on the hypercube. We show that with the use of partial phase inversion, it is possible to amplify their probability amplitudes to values close to 1.
  arXiv  Detail & Related papers  (2023-05-31T07:30:04Z)
• 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)
• Quantum Thermal State Preparation [39.91303506884272]
  We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations. We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
  arXiv  Detail & Related papers  (2023-03-31T17:29:56Z)
• 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)
• 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)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• On the success probability of quantum order finding [0.0]
  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.
  arXiv  Detail & Related papers  (2022-01-19T18:58:18Z)
• Success-or-Draw: A Strategy Allowing Repeat-Until-Success in Quantum Computation [4.014524824655106]
  We propose a new structure for probabilistic higher-order transformation named success-or-draw, which allows a repeat-until-success implementation. We then present a semidefinite programming approach to obtain optimal success-or-draw protocols and analyze in detail the problem of inverting a general unitary operation.
  arXiv  Detail & Related papers  (2020-11-02T15:38:16Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

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.