論文の概要: Quantum Communication Complexity of Classical Auctions

• arxiv url: http://arxiv.org/abs/2311.12444v2
• Date: Mon, 06 Jan 2025 03:40:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-07 17:02:27.213139
• Title: Quantum Communication Complexity of Classical Auctions
• Title（参考訳）: 古典的オークションにおける量子コミュニケーションの複雑さ
• Authors: Aviad Rubinstein, Zixin Zhou,
• Abstract要約: 量子通信が従来の通信よりも効率的かどうかを問う。 まず,ほぼ最適なオークションの通信複雑性について検討する。 そして、非常に単純な設定で、正確に最適なオークションの最悪の通信複雑性について研究する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本研究では、買い手と売り手とのコミュニケーションの複雑さのレンズの下で、ベイズ収益を最大化する単一購入者によるオークションの基本的な古典的メカニズム設計問題について検討する。 具体的には、従来の通信よりも量子通信の方が効率的かどうかを問う。 これは、非ストラテジックなパーティにおける量子通信と、メカニズム設計における古典的なコミュニケーションの両方とはまったく異なるように見える。 まず,ほぼ最適なオークションの通信複雑性について検討する。 我々は、単価または組合せのバリュエーションを持つ買い手に対して量子オークションプロトコルを提供し、古典的なほぼ最適なオークションに比べて指数的に効率的なコミュニケーションをしながら、最適な収益の任意に良い近似を得る。 しかし、これらのオークションは、売り手が逸脱した買い手から指数関数的に大きな支払いを請求する可能性があるという注意が必要である。 期待される量子通信と最大支払いの積に指数的に低い境界を与える。 次に、非常に単純な設定で、正確に最適なオークションの最悪の通信複雑性を調査する。 1) 最適な古典的オークションプロトコルは無限に多くのビットを必要とするが、1キュービットと2つの古典的ビットの一方のメッセージは十分である。 2. 有限の一方向量子オークションプロトコルが最適収益を得ることができない先例が存在する。 しかし、ほとんど相互作用のない収益最適化量子オークションプロトコルが存在する。 3. 通信複雑性に制限のあるマルチラウンド量子オークションプロトコルが最適収益を得ることができるような先例は存在しない。

関連論文リスト

• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
  量子リソースは、この課題に対処する上で、古典的な手法よりも有利である。 受信機と送信機がマルチキュービットのGreenberger-Horne-Zeilinger(GHZ)状態を共有すると、分散入力のある種のグローバル関数は、送信機からの古典的通信の1ビットでしか計算できないことを示す。 また, 絡み合いに基づくプロトコルは, 白色雑音下では顕著な堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2024-09-20T05:17:09Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  量子計算を古典的な結果によって補う手法を提案する。 予測の利点を生かして、新しいタイプの量子測度がもたらされる。 予測量子測定では、古典計算と量子計算の結果の組み合わせは最後にのみ起こる。
  論文  参考訳（メタデータ） (2022-09-12T15:47:44Z)
• Entanglement-assisted quantum communication with simple measurements [0.0]
  デンスコーディングは、絡み合いがキュービット通信をいかに促進するかを示す基礎的な例である。 測定により、強い、時には最適な絡み合い支援量子ビット通信プロトコルが実現可能であることを示す。 以上の結果から,量子通信の強化における絡み合いの力は,シンプルでスケーラブルな光学実験で得られることが判明した。
  論文  参考訳（メタデータ） (2022-05-19T14:47:38Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。 このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
  論文  参考訳（メタデータ） (2022-03-15T09:46:45Z)
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system [0.0]
  古典的共有ランダム性の助けのないキュービット通信は,その目的を達成することができることを示す。 また、対称多角形状態空間によって記述された古典的でない玩具類の通信ユーティリティについても検討する。
  論文  参考訳（メタデータ） (2022-02-14T15:29:59Z)
• Experimental quantum advantage with quantum coupon collector [10.81907025584207]
  我々は、コヒーレントな状態と単純な線形光学素子を用いて量子クーポンコレクタープロトコルを導入、分析する。 提案プロトコルは,クーポンコレクタの問題の古典的限界に比較して,特定の集合を学習するのに要するサンプル数を著しく削減できることを示す。 また、量子ブラインドボックスゲームを構築することにより、量子クーポンコレクタの潜在的な値と拡張についても論じる。
  論文  参考訳（メタデータ） (2021-12-15T04:54:47Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。 すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。 我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
  論文  参考訳（メタデータ） (2020-09-15T15:10:50Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。