Efficient quantum implementation of the generalized probabilistic bernstein-vazirani algorithm with applications

Abstract

Quantum computing leverages the principles of superposition, entanglement, and interference to perform computations that surpass classical capabilities. Among the earliest demonstrations of quantum advantage, the Bernstein-Vazirani (BV) algorithm illustrates how a quantum computer can identify an unknown n-bit string with just one query to the oracle, compared to n queries required classically, representing an improvement from O(n) to O(1). This thesis explores the BV algorithm and its variants, including the probabilistic BV algorithm, which is capable of identifying multiple secret keys that remain indistinguishable to classical algorithms. This thesis also presents an efficient variant of the generalized probabilistic Bernstein-Vazirani algorithm. This is done by integrating a resource-efficient method to generate uniform superposition states with the generalized probabilistic BV algorithm. This enhancement enables a more practical and scalable implementation, making it well-suited for near-term quantum hardware. Additionally, we discuss the broader cryptographic applications of this approach, highlighting its relevance in modern cryptography.