Fugu-MT 論文翻訳(概要): Quantum Communication Advantage in TFNP

論文の概要: Quantum Communication Advantage in TFNP

arxiv url: http://arxiv.org/abs/2411.03296v2
Date: Mon, 24 Feb 2025 21:17:24 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-26 15:17:52.895644
Title: Quantum Communication Advantage in TFNP
Title（参考訳）: TFNPにおける量子通信技術
Authors: Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li,
Abstract要約: 量子SMPモデルにおける通信複雑性は、古典的な双方向ランダム化モデルよりも指数関数的に小さいことを示す。通信プロトコルを解析するために,構造-vs-ランダム性パラダイムを用いて古典的な下界を証明した。
参考スコア（独自算出の注目度）: 8.777517901289341
License:
Abstract: We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.
Abstract（参考訳）: 量子SMPモデルにおける通信複雑性が古典的双方向ランダム化モデルよりも指数関数的に小さい古典的検証可能な解に対する全探索問題を示す。我々の問題は、最近山川とZhandry(JACM 2024)が導入したクエリ複雑性問題の2部構成である。通信プロトコルを解析するために,構造-vs-ランダム性パラダイムを用いて古典的な下界を証明した。

関連論文リスト

Classical and Quantum Distributed Algorithms for the Survivable Network Design Problem [0.0]
生存可能なネットワーク設計問題(SNDP)に対する分散古典的および量子的アプローチについて検討する。 SNDPの古典的あるいは量子的アルゴリズムは、我々が考慮している分散設定では定式化されていない。結果は、考慮された問題のアプリケーションスケールのインスタンスに対して、古典的モデルと量子的モデルが分離されているかどうかという問題を提起する。
論文参考訳（メタデータ） (2024-04-16T17:27:03Z)
Communication Complexity of Common Randomness Generation with Isotropic States [5.312109949216557]
本稿は、一方通行古典通信と一方通行量子通信の2つの通信モデルについて考察する。古典的通信の場合、量子等方性状態はノイズのある古典的相関に勝らないことを示す。量子通信の場合、量子等方性状態の超高密度符号化を用いることで、共通乱数率を増大させることができることを示す。
論文参考訳（メタデータ） (2023-11-08T14:48:15Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文参考訳（メタデータ） (2022-12-06T22:01:49Z)
Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文参考訳（メタデータ） (2022-11-01T07:52:47Z)
Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文参考訳（メタデータ） (2022-01-06T03:10:53Z)
Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文参考訳（メタデータ） (2021-07-05T17:45:41Z)
Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文参考訳（メタデータ） (2021-06-11T18:00:09Z)
Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文参考訳（メタデータ） (2020-06-26T09:05:58Z)

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