論文の概要: Quantum Communication Advantage in TFNP

• arxiv url: http://arxiv.org/abs/2411.03296v1
• Date: Tue, 05 Nov 2024 17:47:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:58:39.316961
• 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 whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of the class TFNP. 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)

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

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