論文の概要: No Free Compression in Quantum Relaxations for Optimization
- arxiv url: http://arxiv.org/abs/2608.25151v1
- Date: Tue, 25 Aug 2026 20:57:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-27 14:15:15.446224
- Title: No Free Compression in Quantum Relaxations for Optimization
- Title（参考訳）: 最適化のための量子緩和における自由圧縮
- Abstract要約: 量子緩和は古典的な決定変数を、より少ない量子ビット上の期待値に圧縮する。
圧縮はコストを制限された期待値幾何、期待値の大きさの小さいもの、あるいはそれを取り除くよりも要求の多い情報回復にシフトできることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits. We ask what resource tradeoffs this compression entails for quantum optimization. For the complete quadratic-Majorana encoding on $n$ qubits, pairwise correlators can represent $m=Θ(n^2)$ binary variables. We define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign assignment. We show that it is exactly $Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)$, whereas uniformly random sign assignments retain $Θ(1/\sqrt n)$ target-specific margins. The stronger $1/n$ worst-case scaling is Majorana-specific. Moreover, arbitrary density operators and fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. Beyond Majoranas, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of $m$ designated binary observables on $n$ qubits, the universal margin is at most $\sqrt{(2\ln2\;n/m)}$, while arbitrary random access decoding from $N$ copies with constant success probability above $1/2$ requires $nN=Ω(m)$. For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.
- Abstract（参考訳）: 量子緩和は古典的な決定変数を、より少ない量子ビット上の期待値に圧縮する。
我々は、この圧縮が量子最適化に必要なリソースのトレードオフについて尋ねる。
n$ qubits 上の完備二次マヨラナ符号に対して、ペアワイズ相関子は$m=\(n^2)$二変数を表現できる。
我々は、ユニバーサルマージンを、目標記号の割り当て毎に所定の符号で保証できる最小の相関器等級と定義する。
正確に$Δ_{\rm Majであることを示す。
(n)=\tan\!
\left(\fracπ{4n}\right)=\(1/n)$ であるのに対し、一様ランダムな符号代入は$1/\sqrt を保持する。
n) ターゲット特定マージンを$
より強力な1/n$最悪のスケーリングはMajorana固有のものだ。
さらに、任意の密度作用素とフェルミオンガウス状態は同じ二次マヨラナ共分散体を生成するので、非ガウス状態資源はこの2点緩和を拡大することはできない。
Majoranas以外にも、標準的な量子ランダムアクセスコード境界は、一般的な情報理論ベースラインを提供する。
n$ qubits上の任意の固定された$m$のバイナリオブザーバブルに対して、ユニバーサルマージンは最大$\sqrt{(2\ln2\;n/m)}$であり、$N$コピーからの任意のランダムアクセス復号は、1/2$を超える一定の成功確率を持つ$nN=Ωである。
(m)$。
固定されたパウリ相関符号は全ての目標に対して一様に働く必要があり、スムーズな符号復号化の下で固定された非ゼロデコード等級を維持するためには、利用可能なマージンが縮小するにつれて増大する再スケーリングパラメータを必要とする。
したがって、相当な量子ビットの節約を提供する一方で、圧縮はコストを制限された期待値幾何、より小さい期待値の大きさ、あるいはそれを取り除くよりもより要求の多い情報回復へとシフトすることができる。
関連論文リスト
- A Single Fixed Shallow Circuit for Classical Shadows of Arbitrary n-Qubit States [2.5735476569508995]
我々は、再利用可能なシャドウスナップショットのラベルとして外部サンプル設定を置き換える、単一の固定された浅い量子アナライザを構築した。
アナライザは新しく用意された$n$-qubitfiducial register$A$と並列のBellreadout$A$と未知のシステム$S$を組み合わせて、1コピーあたり2n$-bitレコードを生成する。
論文 参考訳（メタデータ） (2026-09-07T04:36:39Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
for general max-k-XORSAT with $k geq 3$, no-time algorithm can be significantly better than random guessing on worst-case instance。
この接続を明示的にし、任意の有限体上の有界次数$D$および有界次数$E$k$-LINSAT$(q,r)$にハードネスを拡張する。
論文 参考訳（メタデータ） (2026-06-11T16:59:12Z) - Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
我々はウェーブレットスケーリング指数$$を臨界診断として同定する。
振幅符号化された量子カーネルの古典的シミュラビリティのシャープな遷移境界として$=1/2$を確立する。
この分散は、厳密には$Var[X] = (d-2)$としてスケールする。
論文 参考訳（メタデータ） (2026-05-12T05:41:12Z) - FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression [35.73320708128261]
固定レートベクトル量子化器のtextscFibQuant を導入する。
コードブックにはBeta-quantile radii, Fibonacci,/,Roberts--Kronecker quasi-Max が組み合わされている。
GPT-2の小さなKVキャッシュでは、textscFibQuantはメモリ-フィデリティフロンティアをトレースする。
論文 参考訳（メタデータ） (2026-05-12T03:45:53Z) - Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility [0.0]
正規化されたガウス確率ベクトルの正確なシミュレーションのための量子アルゴリズムを提案する。
ファイナンシャル・アプリケーションによって動機付けられ、エンド・ツー・エンドのリソース分析を提供する。
論文 参考訳（メタデータ） (2026-04-24T11:29:09Z) - 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) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - 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) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。