Fugu-MT 論文翻訳(概要): Optimal compression with quantum retrieval

論文の概要: Optimal compression with quantum retrieval

arxiv url: http://arxiv.org/abs/2610.06702v1
Date: Mon, 05 Oct 2026 17:00:30 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-08 23:31:13.672624
Title: Optimal compression with quantum retrieval
Title（参考訳）: 量子検索による最適圧縮
Abstract要約: 0,1m の文字列 $x in 0,1m$ of Hamming weight at most $n$, compress it into a short $y in 0,1s$ すると、任意のビット $x_i$ of $x$ はエラーなしで取り出すことができる。対数係数に対する最適圧縮がいかに達成できるかを示す。
参考スコア（独自算出の注目度）: 1.5803859198837156
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.
Abstract（参考訳）: 以下のデータ圧縮問題を考察する。文字列 $x \in \{0,1\}^m$ of Hamming weight at most $n$ を与えられたとき、それを短い文字列 $y \in \{0,1\}^s$ に圧縮し、任意のビット $x_i$ of $x$ を任意の誤りなしに、$y$ の標準的なオラクルエンコーディングに少なくとも$t$ の量子量を用いて取り出すことができる。もしクエリが適応可能であるとすれば、対数係数までの最適な圧縮が達成できることを示す。クエリを非適応的に行う必要がある場合、対数係数を除いて、$m$への依存において空間が最適であるスキームを示し、$n$への依存において最適である場合と比較して2次的に劣る。

関連論文リスト

Transducer-based linear combination of unitaries: theory and applications [12.58662650841309]
線形ユニタリ結合(英: Linear combination of Unitary、LCU)は、量子アルゴリズムにおける基本的なプリミティブであり、そのコストは最も高価なユニタリによって管理される。我々はトランスデューサベースのLCUフレームワークを開発し、この最悪のケース依存を重み付き平均クエリの複雑さに還元する。応用として、スパース行列のブロックエンコーディングの改善が得られ、スパースハミルトンシミュレーションと量子線形系のための量子アルゴリズムが導かれる。
論文参考訳（メタデータ） (2026-09-30T16:25:28Z)
PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization [25.919321923997412]
大規模言語モデル(LLM)は、長期コンテキストのシナリオにますます多くデプロイされている。長いプロンプトはコストとレイテンシを高め、失った中間者現象を悪化させる。我々は、knapsack制約の下で正規化モノトン部分モジュラーとして選択的プロンプト圧縮を定式化するフレームワークであるPC-SubMaxを提案する。
論文参考訳（メタデータ） (2026-09-26T11:07:23Z)
Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。 f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
論文参考訳（メタデータ） (2026-05-13T17:34:24Z)
Quantum Sketches, Hashing, and Approximate Nearest Neighbors [0.0]
広い量子スケッチモデルでは、データセット$P$は$m$-qubit state $_P$としてエンコードされ、各クエリは、$_P$の新しいコピーに対する任意のクエリ依存の測定によって答えられる。すべての近似係数 $cge 1$ と一定の成功確率 $p>1/2$ に対して、ハミング空間 $0,1d$ と $d=(log n)$ に$n$-point のインスタンスを示し、そのようなスケッチは $m=(n)$ qubits を必要とする。
論文参考訳（メタデータ） (2026-02-22T16:18:36Z)
Quantum Data Structure for Range Minimum Query [30.186099880107964]
RMQクエリとレンジ更新をサポートする量子データ構造を提案する。我々は、量子ランダムアクセスメモリを使わずに、$k$-minimum発見のための時間効率の量子アルゴリズムを得る。
論文参考訳（メタデータ） (2026-01-19T16:19:44Z)
Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文参考訳（メタデータ） (2026-01-07T22:07:44Z)
A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文参考訳（メタデータ） (2024-06-17T20:54:11Z)
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文参考訳（メタデータ） (2023-11-03T09:09:23Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
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)

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