Entanglement and coherence in Bernstein-Vazirani algorithm

Abstract

Quantum algorithms allow to outperform their classical counterparts in various tasks, 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 superposition can lead to entanglement across different qubits of the processors, there also exists quantum algorithms which 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 Letter, 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 arbitrary little amount of multipartite entanglement, general quantum correlations, and coherence.

13 pages

References in corpus (13)

• Steering, Entanglement, Nonlocality, and the EPR Paradox
• Quantum discord and the power of one qubit
• Necessary and sufficient condition for non-zero quantum discord
• Measuring Quantum Coherence with Entanglement
• Experimental quantum computing without entanglement
• Entanglement, EPR-correlations, Bell-nonlocality, and Steering
• Frozen Quantum Coherence
• On the role of entanglement and correlations in mixed-state quantum computation
• Universal quantum computation with little entanglement
• Linking a distance measure of entanglement to its convex roof
• On the Role of Coherence in Shor's Algorithm
• Quantum Discord and its Role in Quantum Information Theory
• Maximally entangled three-qubit states via geometric measure of entanglement

Cited by in corpus (18)

• Demonstration of algorithmic quantum speedup
• Catalysis of entanglement and other quantum resources
• Tsallis relative $\alpha$ entropy of coherence dynamics in Grover's search algorithm
• Cohering and decohering power of massive scalar fields under instantaneous interactions
• Coherence dynamics in quantum algorithm for linear systems of equations
• Genuine Multipartite Entanglement in Quantum Optimization
• Quantum Speed Limit for Change of Basis
• Coherence and entanglement dynamics in Shor's algorithm
• Quantum resources in Harrow-Hassidim-Lloyd algorithm
• Information locking and its resource efficient extraction
• Limitation of maximally entangled probes for single-shot distinguishability of unitaries
• Coherence as a resource for phase estimation
• Entanglement of weighted graphs uncovers transitions in variable-range interacting models
• Tradeoff between noise and banding in a quantum adder with qudits
• Basis-independent Coherence in Noninertial Frames
• Quantum partial coherence measures constructed from Fisher information
• Quantum Advantage in Identifying the Parity of Permutations with Certainty
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm