論文の概要: Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids
- arxiv url: http://arxiv.org/abs/2606.17589v1
- Date: Tue, 16 Jun 2026 06:51:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-17 17:15:32.316338
- Title: Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids
- Title（参考訳）: 二次元格子上の対角ユニタリ合成とコンパイルのための漸近的最適回路深さ
- Authors: Chengzhuo Xu, Xiao Chen, Zhihao Liu, Zhigang Li,
- Abstract要約: 対角ユニタリ(Diagonal Unitary)は、量子演算のリソース集約型クラスである。
合成と編集を共同で行う。
GPFを2次元近傍グリッドにコンパイルすることは、この最適性を保っていることを示す。
- 参考スコア（独自算出の注目度）: 12.16068230936605
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Diagonal unitaries are a fundamental but resource-intensive class of quantum operations, arising as the phase separators of QAOA and the time-evolution blocks of Hamiltonian simulation. Under all-to-all connectivity their optimal depth is established, but on nearest-neighbor hardware general-purpose compilers fall back on heuristic search, which yields no analyzable cost bound and becomes intractable at the very sizes where depth is the bottleneck. We address synthesis and compilation jointly. On the synthesis side, we develop a Gray-Path Framework (GPF) that realizes any $n$-qubit diagonal unitary in asymptotically optimal $R_z$ and CNOT depth $O(2^n/n)$ without ancillas. Our main result is that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality: routing adds depth $Θ(2^n/n)$ and gate count $Θ(2^n)$. Because GPF fixes its entire interaction structure in advance, routing reduces to scheduling a known sequence, with no heuristic search. We give the construction both with and without ancillas: the ancilla-free, cost-optimized layout is a two-row grid, and a $2k$-row layout introduces a space--time tradeoff that cuts depth by $1/k$ while remaining asymptotically optimal for the enlarged register; both are deterministic and analyzed in closed form. The same complexity is also attained on a linear nearest-neighbor chain, so the preservation is topology-independent, holding on any architecture that contains such a chain. All routing bounds are closed-form, giving the concrete resource estimates that heuristic compilers cannot provide at scale.
- Abstract（参考訳）: 対角ユニタリは、QAOAの位相分離子とハミルトンシミュレーションの時間進化ブロックとして生じる基本的だがリソース集約的な量子演算のクラスである。
オール・ツー・オール接続下では最適深度が確立されるが、最も近いハードウェアの汎用コンパイラはヒューリスティック検索に回帰する。
合成とコンパイルを共同で行う。
合成側では,漸近的に最適な$R_z$とCNOT深さ$O(2^n/n)$の任意の$n$-qubit対角ユニタリを実現するGray-Path Framework(GPF)を開発した。
我々の主な結果は、GPFを2次元近傍グリッドにコンパイルすると、この最適性が保たれることである: ルーティングには深さが$2^n/n)$とゲート数が$2^n)$が加算される。
GPFはその相互作用構造を事前に修正するため、ルーティングはヒューリスティックな探索を伴わずに、既知のシーケンスのスケジューリングに還元される。
アンシラのない,コスト最適化されたレイアウトは2列グリッドであり,2k$-rowレイアウトでは,拡張レジスタに対して漸近的に最適でありながら深さを1/k$に削減するスペースタイムトレードオフが導入される。
同じ複雑さが線形近傍鎖上でも達成されるので、保存はトポロジーに依存しず、そのような鎖を含むいかなるアーキテクチャも保持する。
すべてのルーティングバウンダリはクローズド形式で、ヒューリスティックコンパイラが大規模に提供できないと具体的なリソースを見積もる。
関連論文リスト
- SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas [1.0712892191688657]
量子ビットハードウェア上のフェルミオン系のシミュレーションは多くの非局所相互作用を含む。
近年の作業では、全接続時のJordan-Wignerルーティングオーバーヘッドを多対数深さに削減している。
本稿では,2次元グリッドアーキテクチャに適したフェルミオン置換プロトコルを提案し,最適な$O(sqrtN)$deepを実現する。
論文 参考訳（メタデータ） (2026-05-25T17:07:47Z) - An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
量子ビット効率の最適化を幾何学的問題として再検討する。
局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
論文 参考訳（メタデータ） (2025-11-11T15:38:57Z) - Clifford+V synthesis for multi-qubit unitary gates [0.0]
基本ゲートの有限集合を用いてターゲットゲートを合成するための一般的な枠組みを開発する。
マルチキュービット制御ゲートを合成するための準最適だが短い実行時アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-09T14:57:55Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - 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) - Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits [6.844618776091756]
近似ユニタリ$k$-デザインは、平均が最初の$k$モーメントまでのハールランダムアンサンブルに近いようなユニタリと測度のアンサンブルである。
我々はサブシステム間の通信がシステムサイズで$O(1)$である乗法誤り近似単位の$k$-designアンサンブルを構築する。
論文 参考訳（メタデータ） (2024-07-10T17:43:23Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth
optimal circuits [1.933681537640272]
我々は、ネストしたミート・イン・ザ・ミドル法を用いて、証明可能なエンフデプス・最適回路とemphT・深度・最適回路を合成するアルゴリズムを開発した。
T-深さ最適化回路を合成するために、空間と時間の複雑さを持つアルゴリズムを$Oleft(left(4n2right)lceil d/crceilright)$とする。
我々のアルゴリズムは空間と時間の複雑さを$poly(n,25.6n,d)$ (or $poly(nlog n,)
論文 参考訳（メタデータ） (2021-01-08T18:13:36Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。