Quantum Communication Complexity of Classical Auctions

• URL: http://arxiv.org/abs/2311.12444v2
• Date: Mon, 06 Jan 2025 03:40:58 GMT
• Title: Quantum Communication Complexity of Classical Auctions
• Authors: Aviad Rubinstein, Zixin Zhou,
• Abstract summary: We ask whether using quantum communication can be more efficient than classical communication. We first study the expected communication complexity of approximately optimal auctions. We then study the worst-case communication complexity of exactly optimal auctions in an extremely simple setting.
• Score: 3.2059212159766095
• License:
• Abstract: We study the fundamental, classical mechanism design problem of single-buyer multi-item Bayesian revenue-maximizing auctions under the lens of communication complexity between the buyer and the seller. Specifically, we ask whether using quantum communication can be more efficient than classical communication. We have two sets of results, revealing a surprisingly rich landscape - which looks quite different from both quantum communication in non-strategic parties, and classical communication in mechanism design. We first study the expected communication complexity of approximately optimal auctions. We give quantum auction protocols for buyers with unit-demand or combinatorial valuations that obtain an arbitrarily good approximation of the optimal revenue while running in exponentially more efficient communication compared to classical approximately optimal auctions. However, these auctions come with the caveat that they may require the seller to charge exponentially large payments from a deviating buyer. We show that this caveat is necessary - we give an exponential lower bound on the product of the expected quantum communication and the maximum payment. We then study the worst-case communication complexity of exactly optimal auctions in an extremely simple setting: additive buyer's valuations over two items. We show the following separations: 1. There exists a prior where the optimal classical auction protocol requires infinitely many bits, but a one-way message of 1 qubit and 2 classical bits suffices. 2. There exists a prior where no finite one-way quantum auction protocol can obtain the optimal revenue. However, there is a barely-interactive revenue-optimal quantum auction protocol. 3. There exists a prior where no multi-round quantum auction protocol with a finite bound on communication complexity can obtain the optimal revenue.

Related papers

• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
  Quantum resources offer advantages over classical methods in addressing this challenge. We show that when the receiver and the senders share a multi-qubit Greenberger-Horne-Zeilinger (GHZ) state, certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. We also show that the entanglement-based protocol exhibits significant robustness under white noise.
  arXiv  Detail & Related papers  (2024-09-20T05:17:09Z)
• 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 as well as to the detection of Mutually Unbiased Bases.
  arXiv  Detail & Related papers  (2023-05-17T16:58:05Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Entanglement-assisted quantum communication with simple measurements [0.0]
  Dense coding is the seminal example of how entanglement can boost qubit communication. We show that measurements enable strong and sometimes even optimal entanglement-assisted qubit communication protocols. Our results reveal that there are scenarios in which the power of entanglement in enhancing quantum communication can be harvested in simple and scalable optical experiments.
  arXiv  Detail & Related papers  (2022-05-19T14:47:38Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system [0.0]
  We show that a qubit communication without any assistance of classical shared randomness can achieve the goal. We also study communication utility of a class of non-classical toy systems described by symmetric polygonal state spaces.
  arXiv  Detail & Related papers  (2022-02-14T15:29:59Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)
• 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 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)

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.