Noise Thresholds for Quantum Advantage in the Bernstein-Vazirani and Deutsch-Jozsa Algorithms
The study analytically investigates how single-qubit Pauli noise (bit-flip, phase-flip, depolarizing) affects the Bernstein-Vazirani and Deutsch-Jozsa algorithms using density matrices. It derives exact success probabilities as a function of error rates and qubit number. The findings show that while certain noise types have operational thresholds, scaling up quantum systems requires drastically lower error rates to maintain performance.