Fugu-MT 論文翻訳(概要): Strong matchgate designs in nearly optimal depth

論文の概要: Strong matchgate designs in nearly optimal depth

arxiv url: http://arxiv.org/abs/2609.26677v1
Date: Tue, 22 Sep 2026 16:36:16 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-24 01:05:39.746253
Title: Strong matchgate designs in nearly optimal depth
Title（参考訳）: ほぼ最適深さにおける強整合設計
Abstract要約: 接続性のある回路は、サブ線形深さにおいてマッチゲート群上の設計を形成できないことを示す。フェミオンルーティング技術の現状を改善し、$mathcalO(rm rt(mathsfG)log n)$ depth routerを得る。この結果から,マッチングゲート3次元設計からの描画を必要とするフェルミオントモグラフィーの量子アルゴリズムは,量子コンピュータ上で指数関数的に高速化される可能性が示唆された。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Understanding the resources required to generate approximately random unitaries over various groups is a natural goal of quantum information theory. With respect to one notion of approximation, that of a design, it is known that the full unitary group can be approximated in logarithmic depth by one-dimensional circuits of nearest-neighbour 2-local gates. On the other hand, remarkably, circuits with this connectivity cannot form designs over the matchgate group in sublinear depth. Here we show that this dramatic slowdown can disappear when using a general qubit connectivity graph $\mathsf{G}$ of routing number ${\rm rt}(\mathsf{G})$. Indeed, in this setting one can obtain (strong) $\varepsilon$-approximate relative error matchgate $k$-designs in depth $\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))$. For all-to-all connectivity, ${\rm rt}(\mathsf{G})=2$. Our construction is conceptually simple, involving a random walk on the matchgate group, and no ancillae. As a technical byproduct, we improve upon the state of the art for fermionic routing, obtaining an $\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth router. Additionally, for $k=3$, we obtain an exact strong matchgate design in $\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth, again without ancillae. Under all-to-all connectivity, our fermionic router and 3-designs are optimal. Notably, our results imply that quantum algorithms for fermionic tomography which require drawing from a matchgate 3-design may be exponentially sped up on quantum computers with all-to-all connectivity, relative to their strictly one-dimensional counterparts.
Abstract（参考訳）: 様々な群にわたるおよそランダムなユニタリを生成するために必要なリソースを理解することは、量子情報理論の自然な目標である。設計上の近似の1つの概念に関して、完全ユニタリ群は、最も近い2つの局所ゲートの1次元回路で対数深さで近似できることが知られている。一方、驚くべきことに、この接続を持つ回路は、サブ線形深さのマッチゲート群上の設計を成すことはできない。ここでは、一般的なqubit接続グラフ $\mathsf{G}$ のルーティング番号 ${\rm rt}(\mathsf{G})$ を使用すると、この劇的なスローダウンが消えることを示す。実際、この設定では、(強く)$\varepsilon$-approximate relative error matchgate $k$-designs in depth $\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))$を得ることができる。全接続の場合、${\rm rt}(\mathsf{G})=2$である。我々の構成は概念的には単純で、マッチゲート群をランダムに歩いたり、アンシラを伴わない。技術的副産物として、フェミオンルーティングの最先端性を改善し、$\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth routerを得る。さらに、$k=3$ の場合、$\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth の真に強い整合性設計が得られる。全接続では、フェミオンルータと3つの設計が最適です。特に,本研究の結果から,マッチングゲート3次元設計からの描画を必要とするフェルミオントモグラフィーの量子アルゴリズムは,厳密な1次元モデルと比較して全接続性を持つ量子コンピュータ上で指数関数的に高速化される可能性が示唆された。

関連論文リスト

(Almost) quadruply optimal unitary designs in 1D [0.0]
回路深さ$O(log(n/varepsilon) + klog k)$を相対誤差で達成する。これは、回路深度が$(log(n/varepsilon) + k)$、必要数の$T$ゲートが$widetilde(nk)$と一致する。
論文参考訳（メタデータ） (2026-08-19T07:56:18Z)
Matchgate synthesis via Clifford matchgates and $T$ gates [0.0]
マッチゲートのユニタリは、相互作用しないフェルミオンとの関係のため、量子計算においてユビキタスである。我々は、マッチゲートゲートのみを用いてマッチゲートユニタリをコンパイルする。近似誤差 $varepsilon_mathbbSO (2n)$ は、この小さな次元の表現において、少なくとも指数関数的に大きいユニタリの$O(n,varepsilon_mathbbSO (2n))$ エラーに変換される。
論文参考訳（メタデータ） (2026-02-05T08:15:52Z)
No-go theorems for sublinear-depth group designs [0.0]
局所ゲートを持つ1次元のサブ線形回路からなる$G$の部分集合が、$G$に対して近似的な$k$-designを形成することを証明している。ほとんどの群について、そのようなアンサンブルは、高い確率で、一定深度測定の単一ショットで$k$-designsと区別できる。
論文参考訳（メタデータ） (2025-06-19T03:51:18Z)
Random unitaries in extremely low depth [0.8680580889074451]
1D線を含む任意の幾何学上のランダム量子回路は、$log n$ 深さで$n$ qubits以上の近似ユニタリな設計をすることができることを証明している。同様の方法で、1D回路では$textpoly(log n)$ depthで、全接続回路では$textpoly(log log n)$ depthで$textpoly(log log n)$ depthで擬似ランダムユニタリ(PRU)を構築する。
論文参考訳（メタデータ） (2024-07-10T15:27:48Z)
Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文参考訳（メタデータ） (2024-02-14T13:44:16Z)
On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文参考訳（メタデータ） (2023-05-09T20:53:27Z)
Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文参考訳（メタデータ） (2022-10-15T09:22:22Z)
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)
Epsilon-nets, unitary designs and random quantum circuits [0.11719282046304676]
エプシロンネット(Epsilon-nets)は、量子情報や量子コンピューティングにおける多くの応用に関連するユニタリ演算の概念である。固定された$d$に対して、$delta$-approx $t$-expanders を構成するユニタリが $epsilon$-nets for $tsimeqfracd5/2epsilon$ および $delta=left(fracepsilon3/2dright)d2$ となることを証明している。近似tdesign が生成可能であることを示す。
論文参考訳（メタデータ） (2020-07-21T15:16:28Z)

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

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