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.

arXiv comment13 pages

References in corpus (51)

• Quantum entanglement
• A computable measure of entanglement
• Three qubits can be entangled in two inequivalent ways
• Quantifying Coherence
• Quantifying Entanglement
• Quantum Coherence as a Resource
• The classical-quantum boundary for correlations: discord and related measures
• Steering, Entanglement, Nonlocality, and the EPR Paradox
• Entanglement Measures and Purification Procedures
• On the volume of the set of mixed entangled states
• Quantum discord and the power of one qubit
• Necessary and sufficient condition for non-zero quantum discord
• Quantum Nonlocality without Entanglement
• Quantum algorithms: an overview
• Measuring Quantum Coherence with Entanglement
• On the Power of One Bit of Quantum Information
• Experimental quantum computing without entanglement
• Geometric measure of entanglement and applications to bipartite and multipartite quantum states
• On the role of entanglement in quantum computational speed-up
• Robustness of entanglement
• Robustness of coherence: An operational and observable measure of quantum coherence
• Separability of very noisy mixed states and implications for NMR quantum computing
• Entanglement, EPR-correlations, Bell-nonlocality, and Steering
• Quantum advantage with shallow circuits
• Entanglement and the Power of One Qubit
• The resource theory of informational nonequilibrium in thermodynamics
• Frozen Quantum Coherence
• Most quantum states are too entangled to be useful as computational resources
• Robustness of asymmetry and coherence of quantum states
• On the role of entanglement and correlations in mixed-state quantum computation
• Reversible transformations from pure to mixed states, and the unique measure of information
• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Maximal Coherence and the Resource Theory of Purity
• Genralized Robustness of Entanglement
• Strong Quantum Nonlocality without Entanglement
• Operational Advantage of Quantum Resources in Subchannel Discrimination
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Universal quantum computation with little entanglement
• Good dynamics versus bad kinematics. Is entanglement needed for quantum computation?
• Quantum Computing Without Entanglement
• Linking a distance measure of entanglement to its convex roof
• Cohering power of quantum operations
• On the Role of Coherence in Shor's Algorithm
• Quantum Discord and its Role in Quantum Information Theory
• Implementation of a quantum algorithm to solve Bernstein-Vazirani's parity problem without entanglement on an ensemble quantum computer
• Maximally entangled three-qubit states via geometric measure of entanglement
• Measuring geometric quantum discord using one bit of quantum information
• Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
• Disentanglement Cost of Quantum States
• Entanglement Simulations of Shor's Algorithm
• Spatially Encoded Pseudo-Pure States for NMR Quantum Information Processing

Cited by in corpus (19)

• Demonstration of algorithmic quantum speedup
• Catalysis of entanglement and other quantum resources
• Tsallis relative $\alpha$ entropy of coherence dynamics in Grover's search algorithm
• Using a resource theoretic perspective to witness and engineer quantum generalized contextuality for prepare-and-measure scenarios
• Cohering and decohering power of massive scalar fields under instantaneous interactions
• Genuine Multipartite Entanglement in Quantum Optimization
• Coherence dynamics in quantum algorithm for linear systems of equations
• Quantum Speed Limit for Change of Basis
• Coherence and entanglement dynamics in Shor's algorithm
• Information locking and its resource efficient extraction
• Quantum resources in Harrow-Hassidim-Lloyd algorithm
• 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