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

• arxiv url: http://arxiv.org/abs/2402.01549v3
• Date: Tue, 14 Jan 2025 23:45:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 19:05:11.923720
• Title: Quantum advantage in zero-error function computation with side information
• Title（参考訳）: サイド情報を用いたゼロエラー関数計算における量子優位性
• Authors: Ruoyu Meng, Aditya Ramamoorthy,
• Abstract要約: 本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。 Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. 単一インスタンスの場合における量子アドバンテージの挙動と、混乱グラフのいくつかのクラスについて検討する。
• 参考スコア（独自算出の注目度）: 10.0060346233449
• License:
• Abstract: We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources $X,Y$ with joint p.m.f. $p_{XY}(\cdot, \cdot)$. Bob wants to calculate $f(X,Y)$ with zero error. Alice communicates $m$-length blocks $(m \geq 1)$ with Bob over error-free channels: classical or quantum. In the classical setting, the minimum communication rate depends on the asymptotic growth of the chromatic number of an appropriately defined $m$-instance ``confusion graph'' $G^{(m)}$. In the quantum setting, it depends on the asymptotic growth of the orthogonal rank of the complement of $G^{(m)}$. The behavior of the quantum advantage (ratio of classical and quantum rates) depends critically on $G^{(m)}$ which is shown to be sandwiched between $G^{\boxtimes m}$ ($m$-times strong product) and $G^{\lor m}$ ($m$-times OR product) respectively. Our work presents necessary and sufficient conditions on the function $f(\cdot, \cdot)$ and joint p.m.f. $p_{XY}(\cdot,\cdot)$ such that $G^{(m)}$ equals either $G^{\boxtimes m}$ or $G^{\lor m}$. We study the behavior of the quantum advantage in the single-instance case and the asymptotic (in $m$) case for several classes of confusion graphs and demonstrate, e.g., that there exist problems where there is a quantum advantage in the single-instance rate but no quantum advantage in the asymptotic rate.
• Abstract（参考訳）: 本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。 Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_{XY}(\cdot, \cdot)$. Bobはゼロエラーで$f(X,Y)$を計算したい。 Aliceは、$m$-length blocks $(m \geq 1)$とBobとエラーのないチャネル(古典的または量子的)を通信する。 古典的な設定では、最小の通信速度は、適切に定義された$m$-instance ``confusion graph''' $G^{(m)}$の彩色数の漸近的な成長に依存する。 量子環境では、$G^{(m)}$の補集合の直交ランクの漸近的な成長に依存する。 量子優位性(古典的および量子速度の比)の挙動は、それぞれ$G^{\boxtimes m}$$$m$-times strong product)と$G^{\lor m}$$$m$-times OR product(英語版)の間に挟まれていることを示す$G^{(m)}$に依存する。 我々の研究は、関数 $f(\cdot, \cdot)$ と結合 p.m.f. $p_{XY}(\cdot,\cdot)$ に対して必要十分条件を示し、$G^{(m)}$ が $G^{\boxtimes m}$ または $G^{\lor m}$ のいずれかである。 単一インスタンスの場合の量子アドバンテージの挙動と、混乱グラフのいくつかのクラスに対する漸近($m$)の場合について検討し、例えば、単一インスタンスレートに量子アドバンテージがあるが漸近レートに量子アドバンテージがないという問題が存在することを示した。

関連論文リスト

• 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)

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

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