論文の概要: Quantum advantage in zero-error function computation with side information

• arxiv url: http://arxiv.org/abs/2402.01549v2
• Date: Mon, 4 Mar 2024 23:02:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-07 00:40:45.512550
• Title: Quantum advantage in zero-error function computation with side information
• Title（参考訳）: サイド情報を用いたゼロエラー関数計算における量子アドバンテージ
• Authors: Ruoyu Meng and Aditya Ramamoorthy
• Abstract要約: 我々は、Alice氏がゼロエラーで発生するためにBobに送らなければならない最小限の情報量の特徴付けを目指している。 ある場合、古典的な伝送に対して量子伝送を使うことには厳格な優位性があるが、他方の場合ではそのような優位性はない。
• 参考スコア（独自算出の注目度）: 11.820804392113294
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of zero-error function computation with side information. Alice has a source $X$ and Bob has correlated source $Y$ and they can communicate via either classical or a quantum channel. Bob wants to calculate $f(X,Y)$ with zero error. We aim to characterize the minimum amount of information that Alice needs to send to Bob for this to happen with zero-error. In the classical setting, this quantity depends on the asymptotic growth of $\chi(G^{(m)})$, the chromatic number of an appropriately defined $m$-instance "confusion graph". In this work we present structural characterizations of $G^{(m)}$ and demonstrate two function computation scenarios that have the same single-instance confusion graph. However, in one case there a strict advantage in using quantum transmission as against classical transmission, whereas there is no such advantage in the other case.
• Abstract（参考訳）: サイド情報を用いたゼロエラー関数計算の問題を考える。 Alice はソース $X$ を持ち、Bob はソース $Y$ と相関しており、古典的または量子的チャネルを介して通信することができる。 Bobはゼロエラーで$f(X,Y)$を計算したい。 我々は、アリスがボブに送らなければならない最小限の情報量をゼロエラーで特徴付けることを目指している。 古典的な設定では、この量は、適切に定義された$m$-instance "confusion graph" の彩色数である$\chi(g^{(m)})$の漸近的な成長に依存する。 本稿では、$G^{(m)}$の構造的特徴を示し、同一の単一インスタンス混同グラフを持つ2つの関数計算シナリオを示す。 しかし、あるケースでは量子伝送を古典的伝送に対して使用するという厳格な利点があるが、もう一方の場合ではそのような利点はない。

関連論文リスト

• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。 我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T11:31:54Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。 これらの問題は、分散量子の優位性を認めないことを示している。
  論文  参考訳（メタデータ） (2023-07-18T17:17:27Z)
• Amplification, inference, and the manifestation of objective classical information [0.0]
  Touilらは、量子古典状態(量子$mathcalS$から測定値$mathcalF$)から異なるホレボ量を調査した。 良いデコヒーレンスが存在する場合、x2013$, $mathcalE/mathcalF$ は量子チャネル $mathcalE/mathcalF$ によってしばしばアクセスされる。 特定のモデルでは、アクセス可能な情報は最適検出のための誤差確率と関連付けられ、したがって量子チャーンと同じ振る舞いを持つ。
  論文  参考訳（メタデータ） (2022-06-06T18:00:00Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• On relating one-way classical and quantum communication complexities [6.316693022958221]
  通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。 量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
  論文  参考訳（メタデータ） (2021-07-24T14:35:09Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:05:09Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。 我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-29T02:02:40Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem [0.05076419064097732]
  指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題 効率的な通信プロトコルは、$f$の符号度に応じて提示される。
  論文  参考訳（メタデータ） (2020-01-15T21:05:32Z)

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

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