Analysis of the Bernstein--Vazirani Algorithm in the presence of Pauli Noise
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We analytically investigate the robustness of the Bernstein--Vazirani algorithm in the presence of bit flip, phase flip, and depolarizing noise using the density matrix formalism. We derive the exact expressions for the algorithm's success probability as a function of the error probability $\boldsymbol{p}$ and number of qubits $\boldsymbol{n}$. The analysis compares the three noise models and reveals how performance degrades with increasing system size under standard Pauli noise models. Most importantly, we show that scaling up quantum systems without simultaneously improving qubit quality leads to a sharp decline in ideal quantum speedup.