Complexity of Bernstein--Vazirani algorithm in the presence of noise

• URL: http://arxiv.org/abs/2508.01884v1
• Date: Sun, 03 Aug 2025 18:36:01 GMT
• Title: Complexity of Bernstein--Vazirani algorithm in the presence of noise
• Authors: Muhammad Faizan, Muhammad Faryad,
• Abstract summary: We analytically investigated the robustness of the Bernstein--Vazirani algorithm in the presence of depolarizing noise.<n>It was seen that scaling up quantum systems without simultaneously improving qubit quality leads to a sharp decline in the quantum advantage for this algorithm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We analytically investigated the robustness of the Bernstein--Vazirani algorithm in the presence of depolarizing noise using the density matrix formalism. We derive exact expressions for the algorithm's success probability as a function of the depolarizing error rate $\boldsymbol{p}$ and number of qubits $\boldsymbol{n}$. The analysis reveals how performance degrades with increasing system size under realistic noise conditions. Furthermore, it was seen that scaling up quantum systems without simultaneously improving qubit quality leads to a sharp decline in the quantum advantage for this algorithm.

Related papers

• An em algorithm for quantum Boltzmann machines [40.40469032705598]
  We develop a quantum version of the em algorithm for training quantum Boltzmann machines.<n>We implement the algorithm on a semi-quantum restricted Boltzmann machine, where quantum effects are confined to the hidden layer.
  arXiv  Detail & Related papers  (2025-07-29T07:59:22Z)
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  This paper considers the problem of decentralized optimization on compact submanifolds.<n>We propose an algorithm where agents update variables using quantized variables.<n>To the best of our knowledge, this is the first algorithm to achieve an $mathcalO (1/K)$ convergence rate in the presence of quantization.
  arXiv  Detail & Related papers  (2025-06-09T01:57:25Z)
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation [0.0]
  We present a hybrid quantum algorithm for estimating gaps in many-body energy spectra.<n>We employ error mitigation strategies that optimize the utilization of quantum resources.<n>Results underscore the potential to enable accurate quantum simulations on near-term noisy quantum devices.
  arXiv  Detail & Related papers  (2024-05-16T17:57:15Z)
• Noise-induced transition in optimal solutions of variational quantum algorithms [0.0]
  Variational quantum algorithms are promising candidates for delivering practical quantum advantage on noisy quantum hardware. We study the effect of noise on optimization by studying a variational quantum eigensolver (VQE) algorithm calculating the ground state of a spin chain model.
  arXiv  Detail & Related papers  (2024-03-05T08:31:49Z)
• Quantum Algorithm for Signal Denoising [32.77959665599749]
  The proposed algorithm is able to process textitboth classical and quantum signals. Numerical results show that it is efficient at removing noise of both classical and quantum origin.
  arXiv  Detail & Related papers  (2023-12-24T05:16:04Z)
• General noise-resilient quantum amplitude estimation [0.0]
  We present a novel algorithm that enhances the estimation of amplitude and observable under noise. Remarkably, our algorithm exhibits robustness against noise that varies across different depths of the quantum circuits.
  arXiv  Detail & Related papers  (2023-12-02T09:27:40Z)
• Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent [30.84181129503133]
  The last decade has witnessed an increasing number of stability for different algorithms applied on different loss functions. We make a novel connection between theory applied and introduce a unified guideline for proving stability for optimization algorithms. Our approach is flexible and can be readilyizable to other popular learning classes.
  arXiv  Detail & Related papers  (2023-05-20T01:49:58Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• On the Cryptographic Hardness of Learning Single Periodic Neurons [42.86685497609574]
  We show a simple reduction which demonstrates the cryptographic hardness of learning a single neuron over isotropic Gaussian distributions in the presence of noise. Our proposed algorithm is not a gradient-based or an adversarial SQ-time algorithm, but is rather based on the celebrated Lenstra-LenstraLov'asz (LLL) lattice basis reduction algorithm.
  arXiv  Detail & Related papers  (2021-06-20T20:03:52Z)
• 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)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.