Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation

Abstract

That superpositions of states can be useful for performing tasks in quantum systems has been known since the early days of quantum information, but only recently has quantitative theory of quantum coherence been proposed. Here we apply that theory to an analysis of the Deutsch-Jozsa algorithm, which depends on quantum coherence for its operation. The Deutsch-Jozsa algorithm solves a decision problem, and we focus on a probabilistic version of that problem, comparing probability of being correct for both classical and quantum procedures. In addition, we study a related decision problem in which the quantum procedure has one-sided error while the classical procedure has two-sided error. The role of coherence on the quantum success probabilities in both of these problems is examined.

replaced with published version

Cited by in corpus (150)

• Quantum Coherence as a Resource
• Quantum coherence and geometric quantum discord
• Quantum-coherence quantifiers based on the Tsallis relative $\alpha$-entropies
• Coherence depletion in the Grover quantum search algorithm
• Operational one-to-one mapping between coherence and entanglement measures
• Entanglement and coherence in quantum state merging
• A resource theory of superposition
• Genuine quantum coherence
• One-shot coherence distillation
• Operational Resource Theory of Quantum Channels
• Quantifying Operations with an Application to Coherence
• Observation of time-invariant coherence in a room temperature quantum simulator
• Using and reusing coherence to realize quantum processes
• Probabilistic distillation of quantum coherence
• Operational relevance of resource theories of quantum measurements
• Steered quantum coherence as a signature of quantum phase transitions in spin chains
• When is a non-Markovian quantum process classical?
• Certification and Quantification of Multilevel Quantum Coherence
• Nonlocal advantage of quantum coherence in high-dimensional states
• Experimental progress on quantum coherence: detection, quantification, and manipulation
• Quantifying quantum coherence via nonreal Kirkwood-Dirac quasiprobability
• On the Role of Coherence in Shor's Algorithm
• Maximum coherence in the optimal basis
• Family of coherence measures and duality between quantum coherence and path distinguishability
• Axiomatic and operational connections between the $l_1$-norm of coherence and negativity
• Uncertainty Relations for Quantum Coherence
• Coherence, Quantum Fisher Information, Superradiance and Entanglement are Interconvertible Resources
• Logarithmic coherence: Operational interpretation of ${\ell }_1$-norm coherence
• Quantum coherence and state conversion: theory and experiment
• Operational interpretation of coherence in quantum key distribution
• Quantum NETwork: from theory to practice
• Dynamics of Quantum Coherence and Quantum Fisher Information After Sudden Quench
• Entanglement as the symmetric portion of correlated coherence
• Accessible and inaccessible quantum coherence in relativistic quantum systems
• Coherence number as a discrete quantum resource
• Maximal steered coherence and its conversion to entanglement in multiple bosonic reservoirs
• Experimental quantification of coherence of a tunable quantum detector
• Quantifying quantum coherence of optical cat states
• Activation of entanglement from quantum coherence and superposition
• The l1 Norm of Coherence of Assistance
• Uncertainty relations for quantum coherence with respect to mutually unbiased bases
• Geometric coherence and quantum state discrimination
• Coherence of quantum channels
• Quantitative wave-particle duality relations from the density matrix properties
• Converting quantum coherence to genuine multipartite entanglement and nonlocality
• Quantum coherence as asymmetry from complex weak values
• On the role of dealing with quantum coherence in amplitude amplification
• Coherence of operations and interferometry
• Quantum Coherence Witness with Untrusted Measurement Devices
• Coherence Depletion in Quantum Algorithms
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Lower Bounds on Quantum Annealing Times
• Coherence transformations in single qubit systems
• Complementary relation of quantum coherence and quantum correlations in multiple measurements
• Coherence makes quantum systems 'magical'
• Quantumness of quantum channels
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Universal Method to Estimate Quantum Coherence
• Quantum-state texture and gate identification
• Witnesses of coherence and dimension from multiphoton indistinguishability tests
• Quantifying coherence in terms of Fisher information
• Deterministic transformations of coherent states under incoherent operations
• Hilbert-Schmidt quantum coherence in multi-qudit systems
• Wave-particle duality employing quantum coherence in superposition with non-orthogonal pointers
• Experimental demonstration of one-shot coherence distillation: High-dimensional state conversions
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Impossibility of Cloning of Quantum Coherence
• Based-nonequilibrium-environment non-Markovianity, quantum Fisher information and quantum coherence
• Quantifying dynamical coherence with coherence measures
• Improvement in quantum communication using quantum switch
• Tsallis relative $\alpha$ entropy of coherence dynamics in Grover's search algorithm
• Partial coherence versus entanglement
• Converting coherence based on positive-operator-valued measures into entanglement
• Unification of quantum resources in distributed scenarios
• Attainable and usable coherence in X states over Markovian and non-Markovian channels
• Generation of Coherence via Gaussian Measurements
• Diagnostics of quantum-gate coherences via end-point-measurement statistics
• Estimating quantum coherence by noncommutativity of any observable and its incoherent part
• Finite Block Length Analysis on Quantum Coherence Distillation and Incoherent Randomness Extraction
• Identifying quantum phase transitions via geometric measures of nonclassicality
• Diagnosing Quantum Phases Using Long-Range Two-Site Quantum Resource Behaviors
• A study of coherence based measure of quantumness in (non) Markovian channels
• Quantum search degeneration under amplitude noise in queries to the oracle
• Cohering and decohering power of massive scalar fields under instantaneous interactions
• Common Coherence Witnesses and Common Coherent States
• The Average Quantum Coherence of Pure State Decomposition
• Coherence dynamics in quantum algorithm for linear systems of equations
• Determining quantum coherence with minimal resources
• Violating the Leggett-Garg inequalities with classical light
• Coherence Fraction in Grover Search Algorithm
• Entropic Diagram Characterization of Quantum Coherence: Degenerate Distillation and the Maximum Eigenvalue Uncertainty Bound
• Uncertainty and certainty relations for quantum coherence with respect to design-structured POVMs
• Experimental investigation of quantum uncertainty relations with classical shadows
• Incoherent Gaussian equivalence of $m-$mode Gaussian states
• Hardy-like Quantum Pigeonhole Paradox and the Projected-Coloring Graph State
• No-go theorems for deterministic purification and probabilistic enhancement of coherence
• Quantum coherence dynamics of displaced squeezed thermal state in a Non-Markovian environment
• A Compendious Review of Majorization-Based Resource Theories: Quantum Information and Quantum Thermodynamics
• Witnessing quantum coherence with prior knowledge of observables
• Thermal coherence of the Heisenberg model with Dzyaloshinsky-Moriya interactions in an inhomogenous external field
• Coherence of assistance and assisted maximally coherent states
• All multipartite entanglements are quantum coherences in locally distinguishable bases
• Frozen condition of quantum coherence
• Partial Distinguishability as a Coherence Resource in Boson Sampling
• Spread and asymmetry of typical quantum coherence and their inhibition in response to glassy disorder
• On coherence of quantum operations by using Choi-Jamiołkowski isomorphism
• Certifying Multilevel Coherence in the Motional State of a Trapped Ion
• Experimental implementation of Hardy-like quantum pigeonhole paradoxes
• Coherence, superposition, and Löwdin symmetric orthogonalization
• Controlling quantum coherence of a two-component Bose-Einstein condensate via an impurity atom
• Coherence via reiterated beam splitting
• Quantum resources in Harrow-Hassidim-Lloyd algorithm
• Quadrature Coherence Scale of Linear Combinations of Gaussian Functions in Phase Space
• Quantum coherence in neutrino spin-flavor oscillations
• On the role of coherence for quantum computational advantage
• Coherence as resource in scattering quantum walk search on complete graph
• Coherence and entanglement dynamics in Shor's algorithm
• Quantum coherence with incomplete set of pointers and corresponding wave-particle duality
• Noncommutative coherence and quantum phase estimation algorithm
• Correlation between resource-generating capacities of quantum gates
• Coherence as a resource for phase estimation
• Parameterized coherence measure
• Classical Invasive Description of Informationally-Complete Quantum Processes
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Experimental quantification of quantum coherence for a set of quantum states
• Tradeoff between noise and banding in a quantum adder with qudits
• A note on robustness of coherence for multipartite quantum states
• Coordinately Assisted Distillation of Quantum Coherence in Multipartite System
• Deterministic all-versus-nothing proofs of Bell nonlocality based on non-stabilizer states
• Coherence of quantum non-Gaussian states via nonlinear absorption of quanta
• Basis-independent Coherence in Noninertial Frames
• Remote Creation of Quantum Coherence via Indefinite Causal Order
• Experimental demonstration of robustness of Gaussian quantum coherence
• Can a qudit carry more information than a dit?
• State convertibility under genuinely incoherent operations
• The tightness of multipartite coherence from spectrum estimation
• Controlling Quantum Coherence of V-type Atom in Dissipative Cavity by Detuning and Weak Measurement Reversal
• Impact of quadrature measurement on quantum coherence
• Direct estimation of quantum coherence by collective measurements
• Quantifying coherence of quantum measurements
• Strictly incoherent operations for one-qubit systems
• Oracle problems as communication tasks and optimization of quantum algorithms
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• The reduction of the number of incoherent Kraus operations for qutrit systems
• Quantifying Dynamical Total Coherence in a Resource Non-increasing Framework
• Quantum-state block texture and its quantification
• Coherent preorder of quantum states
• Quantum coherence and counterdiabatic quantum computing
• Entanglement as the cross-symmetric part of quantum discord
• The uncertainty of quantum states with respect to the projective measurement