Oracle problems as communication tasks and optimization of quantum algorithms

• URL: http://arxiv.org/abs/2409.15549v1
• Date: Mon, 23 Sep 2024 21:03:39 GMT
• Title: Oracle problems as communication tasks and optimization of quantum algorithms
• Authors: Amit Te'eni, Zohar Schwartzman-Nowik, Marcin Nowakowski, Paweł Horodecki, Eliahu Cohen,
• Abstract summary: A key question is how well an algorithm can succeed with a 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum query complexity mainly studies the number of queries needed to learn some property of a black box with high probability. 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. A key observation is that if an algorithm is only allowed to make a single query and the goal is to optimize this mutual information, then we obtain a task which 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 formally considering the oracle as a separate subsystem, whose state records the unknown oracle identity. The oracle query prepares a state, which is then measured; and the target property of the oracle plays the role of a message that should be deduced from the measurement outcome. Thus we obtain a link between the optimal single-query algorithm and minimization of the extent of quantum correlations between the oracle and the computer subsystems. We also find a lower bound on this mutual information, which is related to quantum coherence. These results extend to multiple-query non-adaptive algorithms. As a result, we gain insight into the task of finding the optimal non-adaptive algorithm that uses at most a fixed number of queries, for any oracle problem.

Related papers

• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
  We present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections.
  arXiv  Detail & Related papers  (2023-04-10T19:12:25Z)
• Automatic Generation of an Efficient Less-Than Oracle for Quantum Amplitude Amplification [0.4374837991804085]
  Grover's algorithm is a well-known contribution to quantum computing. We present a classical algorithm that builds a phase-marking oracle for Amplitude Amplification.
  arXiv  Detail & Related papers  (2023-03-13T13:52:19Z)
• Quantum algorithm for finding minimum values in a Quantum Random Access Memory [0.0]
  The optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. We propose a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs.
  arXiv  Detail & Related papers  (2023-01-12T16:22:17Z)
• A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions [4.392337343771302]
  We propose a quantum algorithm that estimates the closeness of a given Boolean function to one that satisfies the strict avalanche criterion'' (SAC) This algorithm requires $n$ queries of the Boolean function oracle, where $n$ is the number of input variables. It is shown our algorithm verifies SAC with the fewest possible calls to quantum oracle and requires the fewest samples for a given confidence bound.
  arXiv  Detail & Related papers  (2022-11-25T12:32:01Z)
• Efficient algorithms for quantum information bottleneck [64.67104066707309]
  We propose a new and general algorithm for the quantum generalisation of information bottleneck. Our algorithm excels in the speed and the definiteness of convergence compared with prior results. Notably, we discover that a quantum system can achieve strictly better performance than a classical system of the same size regarding quantum information bottleneck.
  arXiv  Detail & Related papers  (2022-08-22T14:20:05Z)
• On Efficient Approximate Queries over Machine Learning Models [30.26180913049285]
  We develop a novel unified framework for approximate query answering by leveraging a proxy to minimize the oracle usage. Our framework uses a judicious combination of invoking the expensive oracle on data samples and applying the cheap proxy on the objects in the DB. Our algorithms outperform the state-of-the-art and achieve high result quality with provable statistical guarantees.
  arXiv  Detail & Related papers  (2022-06-06T18:35:19Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. 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.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.