論文の概要: DeComp2: Description Complexity aware Decomposition
- arxiv url: http://arxiv.org/abs/2607.23990v1
- Date: Mon, 27 Jul 2026 04:39:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:15.310345
- Title: DeComp2: Description Complexity aware Decomposition
- Title（参考訳）: DeComp2: 複雑な記述を意識した分解
- Abstract要約: 量子コンパイラは、ゲート数、深さ、忠実度などの実行のみのプロキシを最適化し、コンパイルされた回路をコストの単位として扱う。
本稿では、回路複雑性を$mathcalC_mathrmcirc$と説明複雑性を$mathcalC_mathrmKol$と組み合わせることで、コンパイラの目的を実行からライフサイクル複雑性に引き上げることを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Quantum compilers optimize execution-only proxies such as gate count, depth, and fidelity, treating the compiled circuit as the unit of cost. This conflates two distinct resources, how much the substrate has to do at run time, and how much has to be said to describe what to do. Unrolling a looped program leaves run-time cost unchanged while erasing the hierarchical structure on which downstream optimization and reuse rely. We propose lifting the compiler objective from execution to life cycle complexity by pairing the circuit complexity $\mathcal{C}_{\mathrm{circ}}$ with a Kolmogorov-style description complexity $\mathcal{C}_{\mathrm{Kol}}$ of the emitted circuit, and minimizing the additive total $\mathcal{C}_{\mathrm{tot}} = α\,\mathcal{C}_{\mathrm{circ}} + β\,\mathcal{C}_{\mathrm{Kol}}$. The mirrors the additive positional and kinetic entropy of the second law of quantum complexity, and reads as a minimum-description-length regularizer over the otherwise degenerate set of $\mathcal{C}_{\mathrm{circ}}$-minimizers. We instantiate the objective on $SU(2)$ through exhaustive HT-enumeration with compression-based surrogates upper-bounding $\mathcal{C}_{\mathrm{Kol}}$. Across a Haar-representative target grid the two surrogates correlate positively with $\mathcal{C}_{\mathrm{circ}}$ yet break its rank order on a non-trivial fraction of points, ruling out a tight functional dependence. With calibrated weights the joint cost selects, for a small but operationally meaningful fraction of targets, a candidate that is neither the shortest nor the most compressible HT-string in the $\varepsilon$-ball, exhibiting the compilation choices a $\mathcal{C}_{\mathrm{circ}}$-only optimizer discards and motivating $\mathcal{C}_{\mathrm{Kol}}$ as an active optimization signal for hierarchical intermediate representation for compiler.
- Abstract（参考訳）: 量子コンパイラは、ゲート数、深さ、忠実度などの実行のみのプロキシを最適化し、コンパイルされた回路をコストの単位として扱う。
これは2つの異なるリソース、実行時に基質がどれくらいの時間を実行する必要があるか、何をするかを記述するためにどれくらいの量を記述する必要があるか、を混同している。
ループプログラムのアンロールは、ダウンストリームの最適化と再利用が依存する階層構造を消去しながら、実行時のコストは変わらない。
回路複雑性のペア化により、コンパイラの目的を実行からライフサイクル複雑性へ引き上げることを提案する。 回路複雑性のペア化には、Kolmogorov型記述複雑性の$\mathcal{C}_{\mathrm{Kol}}$と、加算総和$\mathcal{C}_{\mathrm{tot}} = α\,\mathcal{C}_{\mathrm{circ}} + β\,\mathcal{C}_{\mathrm{Kol}}$を最小化する。
この鏡は量子複雑性の第2法則の加法的位置エントロピーと運動論的エントロピーを反映し、そうでなければ$\mathcal{C}_{\mathrm{circ}}$-minimizersの退化集合上の最小記述長正規化子として読む。
目的を$SU(2)$で、圧縮ベースのサロゲート付き全HT列挙により、上界$\mathcal{C}_{\mathrm{Kol}}$で初期化する。
ハール表現的対象格子の向こう側では、2つのサロゲートは正に $\mathcal{C}_{\mathrm{circ}}$ と相関するが、そのランク順序は非自明な点数で破り、関数的依存を強く排除する。
キャリブレーションされたウェイトによって、結合コストは小さなが運用上有意義なターゲットに対して選択され、$\varepsilon$-ballで最短でも最も圧縮可能なHTストリングでもなく、コンパイル選択が$\mathcal{C}_{\mathrm{circ}}$-only optr discards and motivating $\mathcal{C}_{\mathrm{Kol}}$をコンパイラの階層的中間表現のアクティブな最適化信号として表示する。
関連論文リスト
- Efficient Multinomial Logistic Bandit via Frequent Directions [36.600560776380874]
代表的な UCB 型アルゴリズムである OFUL-MLogB は $tildemathcalO(KdsqrtT)$ の残差を達成しているが、それでも $mathcalO(K3d3)$ と $mathcalO(K2d2)$ の時間を必要とする。
我々は、OFD-MLogBに頻繁に描画される方向行列を組み込んだEOFD-MLogBを提案する。
論文 参考訳（メタデータ） (2026-06-10T11:47:27Z) - Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits [0.0]
我々は、$n$-qubit 回路をシミュレートする2つの新しいアルゴリズムを提示する。
提案アルゴリズムは単純で、線形メモリしか必要とせず、自明に並列であり、ZX-ダイアグラムの単純化ルーチンとうまく相互作用する。
論文 参考訳（メタデータ） (2026-03-06T15:27:23Z) - Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring [0.0]
本稿では,有限グラフ上の拡散過程にのみアクセス可能な,整数分解のハイブリッド計算モデルについて検討する。
Shor のアルゴリズムとの比較は,概念的およびモデルベースである。
デジタルステップと拡散ステップの2つのコスト尺度で複雑性を報告する。
論文 参考訳（メタデータ） (2026-01-05T19:45:38Z) - Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。
このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
論文 参考訳（メタデータ） (2025-10-09T09:47:40Z) - Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。
我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。
数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - 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) - Distribution Compression in Near-linear Time [27.18971095426405]
シンニングアルゴリズムを高速化するシンプルなメタプロデューサであるCompress++を紹介する。
$sqrtn$ポイントを$mathcalO(sqrtlog n/n)$統合エラーで提供し、Monte-Carlo の最大誤差を最大化します。
論文 参考訳（メタデータ） (2021-11-15T17:42:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。