Effects of noise on performance of Bernstein-Vazirani algorithm

• URL: http://arxiv.org/abs/2305.19745v2
• Date: Mon, 12 Aug 2024 07:35:37 GMT
• Title: Effects of noise on performance of Bernstein-Vazirani algorithm
• Authors: Archi Gupta, Priya Ghosh, Kornikar Sen, Ujjwal Sen,
• Abstract summary: We introduce various forms of glassy disorders into the effect of Hadamard gates used in the Bernstein-Vazirani circuit. We find that the effectiveness of the algorithm decreases with increasing disorder strength in all cases.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Bernstein-Vazirani (BV) algorithm offers exceptional accuracy in finding the hidden bit string of a function. We explore how the algorithm performs in real-world situations where noise can potentially interfere with its performance. In order to assess the impact of imperfect equipments, we introduce various forms of glassy disorders into the effect of the Hadamard gates used in the Bernstein-Vazirani circuit. We incorporated disorders of five different forms, viz., Haar-uniform with finite cutoff, spherical Gaussian, discrete circular, spherical Cauchy-Lorentz, and squeezed. We find that the effectiveness of the algorithm decreases with increasing disorder strength in all cases. Additionally, we demonstrate that as the number of bits in the secret string increases, the success probability of correctly guessing the string becomes increasingly insensitive to the type of disorder and instead depends only on the mean and spread of the disorder. We compare our results with the performance of the analogous classical algorithm in the presence of similar noise. When the length of the secret string is small or moderate, the quantum BV algorithm is found to be more efficient compared to the classical algorithm for almost all types of disorders under consideration, unless the strength of the disorder is very high and the disorder follows a discrete circular distribution. However, if we move to extremely large secret strings, the success probability of the disordered BV algorithm merges with the success probability of the disordered classical algorithm for all considered disorders having arbitrary strengths. The limit on the length of the string after which the efficiency of the quantum algorithm becomes equivalent to the classical algorithm depends on the amount of disorder and not on the type of disorder.

Related papers

• Resilience-Runtime Tradeoff Relations for Quantum Algorithms [0.7371081631199642]
  A leading approach to algorithm design aims to minimize the number of operations in an algorithm's compilation. We develop a framework to characterize the resilience of an algorithm to perturbative noises. We show how this framework can be leveraged to identify compilations of an algorithm that are better suited to withstand certain noises.
  arXiv  Detail & Related papers  (2024-08-05T18:31:14Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• 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)
• An adaptive Bayesian quantum algorithm for phase estimation [0.0]
  We present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound.
  arXiv  Detail & Related papers  (2023-03-02T19:00:01Z)
• 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)
• Better-than-classical Grover search via quantum error detection and suppression [0.0]
  Grover's search algorithm is one of the first quantum algorithms to exhibit a provable quantum advantage. Here, we report better-than-classical success probabilities for a complete Grover search algorithm on the largest scale demonstrated to date.
  arXiv  Detail & Related papers  (2022-11-08T20:31:02Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
  arXiv  Detail & Related papers  (2022-01-07T13:33:28Z)
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics [0.5249805590164902]
  We show that the algorithm scales similarly to the pure quantum version by deriving tight analytical lower bounds on its efficiency. We also study the behavior of the algorithm subject to noise, and find that under certain oracle and operational errors our measurement-based algorithm outperforms the standard algorithm.
  arXiv  Detail & Related papers  (2020-11-22T00:57:17Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)

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.