Oracle problems as communication tasks and optimization of quantum algorithms

Abstract

Quantum query complexity studies the number of queries needed to learn some property of a black box. A closely related question is how well an algorithm can succeed with this learning task using only a fixed number of queries. In this work, we propose measuring an algorithm's performance using the mutual information between the output and the actual value. The task of optimizing this mutual information using a single query, is similar to a basic task of quantum communication, where one attempts to maximize the mutual information of the sender and receiver. We make this analogy precise by splitting the algorithm between two agents, obtaining a communication protocol. The oracle's target property plays the role of a message that Alice encodes into a quantum state, which is subsequently sent over to Bob. The first part of the algorithm performs this encoding, and the second part measures the state and aims to deduce the message from the outcome. Moreover, we formally consider the oracle as a separate subsystem, whose state records the unknown oracle identity. Within this construction, Bob's optimal measurement basis minimizes the quantum correlations between the two subsystems. We also find a lower bound on the mutual information, which is related to quantum coherence. These results extend to multiple-query non-adaptive algorithms. As a result, we describe the optimal non-adaptive algorithm that uses at most a fixed number of queries, for any oracle classification problem. Crucially, this mutual-information perspective carries direct practical utility for algorithmic design, providing the theoretical foundation to optimize iterative subroutines in hybrid quantum--classical schemes. Within the present work, we apply this framework to analyze the stage-by-stage information flow and track partial progress in several standard quantum algorithms.

60 pages, 1 figure, 5 tables, 9 appendices

References in corpus (37)

• Quantum entanglement
• Quantifying Coherence
• Efficient classical simulation of slightly entangled quantum computations
• The classical-quantum boundary for correlations: discord and related measures
• Quantum discord and the power of one qubit
• Quantum algorithms: an overview
• On the role of entanglement in quantum computational speed-up
• Non-locality and Communication Complexity
• Contextuality supplies the magic for quantum computation
• Converting Coherence to Quantum Correlations
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• Experimental Quantum Hamiltonian Learning
• Hamiltonian Learning and Certification Using Quantum Resources
• Negative weights make adversaries stronger
• Robust Online Hamiltonian Learning
• Quantum Computation by Communication
• Determining a local Hamiltonian from a single eigenstate
• Universal quantum computation with little entanglement
• Quantum Computing Without Entanglement
• Quantum Hamiltonian Learning Using Imperfect Quantum Resources
• Quantum discord as a resource in quantum communication
• The elusive source of quantum effectiveness
• A measure of physical reality
• Quantum Skew Divergence
• Quantum communication complexity advantage implies violation of a Bell inequality
• Quantum interference as a resource for quantum speedup
• Information-reality complementarity: The role of measurements and quantum reference frames
• Discord and quantum computational resources
• Information-based approach towards a unified resource theory
• Coherence and realism in the Aharonov-Bohm effect
• Characterization of exact one-query quantum algorithms
• Active Learning of Quantum System Hamiltonians yields Query Advantage
• State complexity and quantum computation
• Exact and Efficient Simulation of Concordant Computation
• Partial Boolean functions with exact quantum 1-query complexity
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
• Optimal Quantum Likelihood Estimation