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

• arxiv url: http://arxiv.org/abs/2402.01549v4
• Date: Wed, 19 Mar 2025 17:16:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-20 15:19:38.688386
• 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)$. Bob want to compute $f(X,Y)$ with zero error。
• 参考スコア（独自算出の注目度）: 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 encodes $m$-length blocks $(m \geq 1)$ of her observations to Bob over error-free channels, which can be classical or quantum. We consider two classical settings. (i) Alice communicates via a fixed length code (FLC), and (ii) Alice communicates via a variable length code (VLC). In the FLC scenario, 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 VLC scenario, the corresponding rate is characterized by the asymptotics of the chromatic entropy of $G^{(m)}$. %and has single-letter characterization in terms of K\"orner's graph entropy if $G^{(m)}$ is $m$-times graph OR product. In the quantum setting, we only consider fixed length codes; the corresponding rate depends on the asymptotic growth of the orthogonal rank of the complement of $G^{(m)}$. The behavior of the communication 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}$. Our work explores the multitude of possible behaviors of the quantum and classical (FLC/VLC) rates in the single-instance case and the asymptotic (in $m$) case for several classes of confusion graphs.
• Abstract（参考訳）: 本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。 Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_{XY}(\cdot, \cdot)$. Bobはゼロエラーで$f(X,Y)$を計算したい。 Alice encodes $m$-length blocks $(m \geq 1)$彼女の観察は、古典的または量子的なエラーのないチャネル上でBobに渡される。 古典的な設定を2つ検討する。 (i)アリスは固定長符号(FLC)を介して通信し、 (ii)アリスは可変長符号(VLC)を介して通信する。 FLCのシナリオでは、最小の通信速度は、適切に定義された$m$-instance ``confusion graph''' $G^{(m)}$の色の数の漸近的な成長に依存する。 VLCシナリオでは、対応する速度は、$G^{(m)}$の彩色エントロピーの漸近によって特徴づけられる。 %andはK\"orner's graph entropy if $G^{(m)}$ is $m$-times graph OR product。 量子設定では、固定長符号のみを考えるが、対応する速度は、$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}$ のいずれかである。 我々の研究は、単一インスタンスの場合における量子および古典的(FLC/VLC)速度と、混乱グラフのいくつかのクラスに対する漸近的($m$)ケースの様々な振る舞いを探索する。

関連論文リスト

• The classical limit of Quantum Max-Cut [0.18416014644193066]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。 我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
  論文  参考訳（メタデータ） (2020-08-16T21:26:46Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:05:09Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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