Consumable Data via Quantum Communication

• URL: http://arxiv.org/abs/2409.08495v3
• Date: Tue, 15 Jul 2025 01:18:49 GMT
• Title: Consumable Data via Quantum Communication
• Abstract summary: Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy.<n>We show an application to a strategic data-selling game, and discuss other potential economic implications.
• Score: 5.2218810644773965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data $x$ and Bob holds $m$ inputs $y_1,... , y_m$. They want to compute $m$ instances of a bipartite relation $R$ on every pair $(x, y_1),\ldots, (x, y_m)$. We call this the asymmetric direct sum question for one-way communication. We give a number of examples where the quantum communication complexity of such problems scales polynomially with $m$, while the classical communication complexity depends at most logarithmically on $m$. Thus, for such problems, data behaves like a consumable resource that is effectively destroyed upon use when the owner stores and transmits it as quantum states, but not when transmitted classically. We show an application to a strategic data-selling game, and discuss other potential economic implications.

Related papers

• Precoding-based protocols for entanglement assisted linear computation over a quantum many-to-one network [9.27021252711692]
  We consider the problem of computing a linear combination over a noiseless quantum many-to-one network.<n>We present protocols that support the computation of a more general class of linear transformations.
  arXiv  Detail & Related papers  (2026-07-15T12:15:21Z)
• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  This paper introduces a novel proof technique based on a multi-player communication game.<n>We show that winning this communication game requires transmitting information proportional to the number of over-active users.<n>We show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
  arXiv  Detail & Related papers  (2026-02-12T17:49:07Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  conditional distributions is a central problem in machine learning. We propose a new learning paradigm that integrates both paired and unpaired data. Our approach also connects intriguingly with inverse entropic optimal transport (OT)
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• Complex Reasoning over Logical Queries on Commonsense Knowledge Graphs [61.796960984541464]
  We present COM2 (COMplex COMmonsense), a new dataset created by sampling logical queries. We verbalize them using handcrafted rules and large language models into multiple-choice and text generation questions. Experiments show that language models trained on COM2 exhibit significant improvements in complex reasoning ability.
  arXiv  Detail & Related papers  (2024-03-12T08:13:52Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  We show an it unbounded quantum advantage in relation reconstruction without public coins. We also highlight some applications of this task to semi-device-independent dimension witnessing and the detection of Mutually Unbiased Bases.
  arXiv  Detail & Related papers  (2023-05-17T16:58:05Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  We consider a multi-party computation problem with $n$ players, where players $2, dots, n$ need to communicate appropriate information to player 1. We exhibit a quantum protocol (with complexity $(n-1) log n$ bits) and a classical protocol (with complexity $(n-1)2 (log n2$) bits) This demonstrates that our quantum protocol is strictly better than classical protocols.
  arXiv  Detail & Related papers  (2023-05-08T03:10:08Z)
• Communication-efficient Quantum Algorithm for Distributed Machine Learning [14.546892420890943]
  Our quantum algorithm finds the model parameters with a communication complexity of $O(fraclog_2(N)epsilon)$, where $N$ is the number of data points and $epsilon$ is the bound on parameter errors. The building block of our algorithm, the quantum-accelerated estimation of distributed inner product and Hamming distance, could be further applied to various tasks in distributed machine learning to accelerate communication.
  arXiv  Detail & Related papers  (2022-09-11T15:03:58Z)
• Benchmarking Compositionality with Formal Languages [64.09083307778951]
  We investigate whether large neural models in NLP can acquire the ability tocombining primitive concepts into larger novel combinations while learning from data. By randomly sampling over many transducers, we explore which of their properties contribute to learnability of a compositional relation by a neural network. We find that the models either learn the relations completely or not at all. The key is transition coverage, setting a soft learnability limit at 400 examples per transition.
  arXiv  Detail & Related papers  (2022-08-17T10:03:18Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  We develop a novel connection between discrepancy minimization and (quantum) communication complexity. We show that for every collection of symmetric $n times n$ $A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ there exist signs $x in pm 1n such that the maximum eigenvalue of $sum_i leq n x_i A_i$ is at most
  arXiv  Detail & Related papers  (2021-10-19T16:51:11Z)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  We study the advantages of quantum communication and prior entanglement of the private simultaneous quantum messages model. We show that the privacy condition inevitably increases the communication cost in the two-party PSQM model. We also show an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings.
  arXiv  Detail & Related papers  (2021-05-15T03:08:01Z)
• Correlations in entanglement-assisted prepare-and-measure scenarios [0.0]
  We investigate the correlations that can arise between Alice and Bob in prepare-and-measure communication scenarios. We provide examples of correlations that actually require more general protocols based on higher-dimensional states.
  arXiv  Detail & Related papers  (2021-03-19T11:30:39Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Communication memento: Memoryless communication complexity [5.88864611435337]
  We study the communication complexity of computing functions $F:0,1ntimes 0,1n rightarrow 0,1$ in the memoryless communication model.
  arXiv  Detail & Related papers  (2020-05-08T14:33:25Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  We consider the problem of implementing two-party interactive quantum communication over noisy channels. For a noiseless qudit channel over a $mathrmpoly(n)$ size alphabet, our main result is a simulation method that fails with probability less than $2-Theta(nepsilon)$ We conjecture that it is optimal up to a constant factor in the $sqrtepsilon$ term.
  arXiv  Detail & Related papers  (2020-01-09T02:48:43Z)

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.