論文の概要: 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つの関数計算シナリオを示す。 しかし、あるケースでは量子伝送を古典的伝送に対して使用するという厳格な利点があるが、もう一方の場合ではそのような利点はない。

関連論文リスト

• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。 制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
  論文  参考訳（メタデータ） (2024-10-30T17:01:00Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。 我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T11:31:54Z)
• Transfer Operators from Batches of Unpaired Points via Entropic Transport Kernels [3.099885205621181]
  そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。 我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
  論文  参考訳（メタデータ） (2024-02-13T12:52:41Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。 これらの問題は、分散量子の優位性を認めないことを示している。
  論文  参考訳（メタデータ） (2023-07-18T17:17:27Z)
• Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
  共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。 我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
  論文  参考訳（メタデータ） (2023-01-01T08:30:35Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Amplification, inference, and the manifestation of objective classical information [0.0]
  Touilらは、量子古典状態(量子$mathcalS$から測定値$mathcalF$)から異なるホレボ量を調査した。 良いデコヒーレンスが存在する場合、x2013$, $mathcalE/mathcalF$ は量子チャネル $mathcalE/mathcalF$ によってしばしばアクセスされる。 特定のモデルでは、アクセス可能な情報は最適検出のための誤差確率と関連付けられ、したがって量子チャーンと同じ振る舞いを持つ。
  論文  参考訳（メタデータ） (2022-06-06T18:00:00Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• 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)
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs [6.305950347749109]
  本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。 我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
  論文  参考訳（メタデータ） (2021-10-08T15:24:31Z)
• On relating one-way classical and quantum communication complexities [6.316693022958221]
  通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。 量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
  論文  参考訳（メタデータ） (2021-07-24T14:35:09Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem [0.05076419064097732]
  指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題 効率的な通信プロトコルは、$f$の符号度に応じて提示される。
  論文  参考訳（メタデータ） (2020-01-15T21:05:32Z)

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

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