Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. 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. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.
Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. 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. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.
Naseri et al. [Phys. Rev. A 106, 062429 (2022); arXiv:2205.13610] studied which quantum resources in initial states are essential for the probabilistic Bernstein-Vazirani (BV) algorithm, defining its performance as the optimal average success probability over all measurements. In this work, we consider a variant of BV algorithm, which is called the initialization-free (IF) BV algorithm, in which an arbitrary ancilla state as the oracle register is allowed, to improve the performance. We derive an explicit formula for the performance of the probabilistic IF-BV algorithm and obtain a necessary and sufficient condition for an initial state to achieve maximal performance. We further prove that, under a suitable ordering assumption on the coefficients of the initial state, the probabilistic IF-BV algorithm outperforms the standard probabilistic BV algorithm.
Quantum entanglement and coherence are crucial resources in quantum information theory. In some scenarios, however, it is not necessary to directly estimate entanglement or coherence measures to quantify the capabilities of a state in quantum information processing. Instead, fully entangled fraction and coherence fraction are two alternatives for entanglement and coherence in specific quantum tasks. Here, we establish a link between the coherence fraction and the Bernstein-Vazirani algorithm, which has several potential applications including cryptography and database search. We show that the success probability of the generalized Bernstein-Vazirani algorithm depends only on the coherence fraction of the initial state rather than its entanglement or coherence. Moreover, we discuss the coherence fraction dynamics and establish a relation between the operator's coherence fraction and the algorithm's success probability. Our findings highlight how quantum coherence fraction influences the efficiency of quantum algorithms.
This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.
Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant devices has remained elusive. Here, we unequivocally demonstrate such a speedup within the oracular model, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, using two different 27-qubit IBM Quantum superconducting processors. The speedup is observed on only one of the two processors when the quantum computation is protected by dynamical decoupling but not without it. The quantum speedup reported here does not rely on any additional assumptions or complexity-theoretic conjectures and solves a bona fide computational problem in the setting of a game with an oracle and a verifier.
The advent of quantum computing has ushered in a new era of computational capabilities, promising to revolutionize the resolution of complex problems. Unlike classical computers, which rely on binary digits (bits) to process information, quantum computers utilize quantum bits (qubits) that can exist in multiple states simultaneously due to the principles of superposition and entanglement inherent in quantum mechanics. This fundamental difference allows quantum computers to perform certain calculations exponentially faster than their classical counterparts, offering profound implications for fields ranging from cryptography to material science. At the heart of this transformative potential lie quantum algorithms, specifically designed to harness the unique properties of quantum systems to tackle problems currently intractable for classical computers. Notable examples include Shor's algorithm for integer factorization, which threatens the security of widely used cryptographic schemes, and Grover's algorithm for unstructured search, which provides a quadratic speedup over classical approaches. Beyond these pioneering works, ongoing research continues to uncover new quantum algorithms capable of addressing a broad spectrum of applications. The proposed method leverages the principles of quantum mechanics to develop efficient algorithms that outperform classical approaches in solving complex computational problems. By harnessing the unique properties of quantum bits (qubits), such as superposition and entanglement, the method aims to achieve superior accuracy and efficiency in various applications. The performance of the proposed method was evaluated using several key metrics: an accuracy of 94.8%, a Root Mean Squared Error (RMSE) of 0.208, and a Mean Absolute Error (MAE) of 0.406. These metrics collectively underscore the robustness and reliability of the proposed quantum algorithms, highlighting their potential to significantly enhance computational efficiency and accuracy across various domains. This study delves into the development of quantum algorithms, exploring their theoretical foundations, practical implementations, and the challenges faced in their realization. By leveraging the principles of quantum mechanics, these algorithms hold the promise of not only solving existing problems more efficiently but also unlocking new computational paradigms previously deemed unattainable. Through a comprehensive analysis, this research aims to elucidate the current state of quantum algorithm research, highlight the advancements made, and identify the pathways forward in this rapidly evolving field.
The quantum algorithms covered in this chapter, i.e., the Deutsch, Deutsch-Jozsa and Bernstein-Vazirani algorithms, have been chosen for their relative simplicity and theoretical interest. They do not address problems of real practical value, their purpose being to demonstrate, using simple examples, the great potential power of quantum computation relative to the digital case. The most significant breakthrough in quantum computing is Shor's integer factorisation algorithm. Shor's algorithm is beyond the scope of this introductory text, but its significance lies in the fact that it demonstrates the potential to factor large integers efficiently. No efficient digital algorithms for factoring large integers exist, and many current encryption algorithms rely on this being the case. Shor's algorithm therefore threatens current encryption methods, and is responsible for much of the recent accelerated interest in quantum computation.