論文の概要: Quantum Communication Complexity of Classical Auctions
- arxiv url: http://arxiv.org/abs/2311.12444v1
- Date: Tue, 21 Nov 2023 08:56:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 01:32:31.236627
- Title: Quantum Communication Complexity of Classical Auctions
- Title(参考訳): 古典オークションの量子通信複雑性
- Authors: Aviad Rubinstein and Zixin Zhou
- Abstract要約: 量子通信が従来の通信よりも効率的かどうかを問う。
まず,ほぼ最適なオークションの通信複雑性について検討する。
そして、非常に単純な設定で、正確に最適なオークションの最悪の通信複雑性について研究する。
- 参考スコア(独自算出の注目度): 3.78737122317863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。