論文の概要: (Almost) quadruply optimal unitary designs in 1D

• arxiv url: http://arxiv.org/abs/2608.18650v1
• Date: Wed, 19 Aug 2026 07:56:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-20 20:13:55.325747
• Title: (Almost) quadruply optimal unitary designs in 1D
• Title（参考訳）: 1次元における(ほぼ)4重最適ユニタリ設計
• Abstract要約: 回路深さ$O(log(n/varepsilon) + klog k)$を相対誤差で達成する。 これは、回路深度が$(log(n/varepsilon) + k)$、必要数の$T$ゲートが$widetilde(nk)$と一致する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct $n$-qubit approximate unitary $k$-designs in 1D systems, achieving circuit depth $O(\log(n/\varepsilon) + k\log k)$ with relative error $\varepsilon$ and requiring $O(nk\log k)$ magic gates. This matches existing lower bounds $Ω(\log(n/\varepsilon) + k)$ for circuit depth, and $\widetildeΩ(nk)$ for the required number of $T$ gates, up to a $\log k$ factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from $O(k\log k)$ to $O(\log k)$. We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making $O(\log k)$-local random unitaries realizable in depth $O(k\log k)$. As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.
• Abstract（参考訳）: 回路深度$O(\log(n/\varepsilon) + k\log k)$を相対誤差$\varepsilon$で達成し、O(nk\log k)$マジックゲートを必要とする。 これは、回路深度に対して$Ω(\log(n/\varepsilon) + k)$と、必要数の$T$ゲートに対して$\widetildeΩ(nk)$と一致し、すべてのパラメータにおいて同時に近い最適性を達成する。 我々の構築は、既存の2つの結果の組み合わせと改善に基づいている。 我々は、Zhang et al のマジック拡張回路構成において、クリフォード対称性を破るために必要なマジックブロックサイズを $O(k\log k)$ から $O(\log k)$ に削減する。 We improve thebreaking construction of Chen et al to construct a generation set of 1D local constant-deepth circuit for the unitary group with a constant spectrum gap, makes $O(\log k)$-local random unitary realizable in depth $O(k\log k)$。 副生成物として、クリフォード群に対して一定の大きさの 1D-局所生成集合を提供し、これは独立な興味を持つものと期待する。 この2つの結果とグルーリング補題を組み合わせることで,最終的な結果が証明される。

関連論文リスト

• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• Unitary designs in nearly optimal depth [40.28216388589026]
  回路深さ$O(log k log log n k / varepsilon)$。 深さは既知のすべての結果に対して指数関数的に改善され、すべてのパラメータは$n$, $k$, $varepsilon$である。 また,多数のクエリをランダムなユニタリーに格納する量子実験において,エラーをバウンディングするための新しい分析フレームワークを開発した。
  論文  参考訳（メタデータ） (2025-07-08T17:48:33Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  ディック状態は量子コンピューティングに広く応用された、絡み合った量子状態の重要なクラスを表す。 一般に見られる2つの量子ビット接続制約の下でDicke状態生成のための決定論的量子回路を提案する。
  論文  参考訳（メタデータ） (2025-05-21T11:55:17Z)
• Pseudorandomness Properties of Random Reversible Circuits [1.593690982728631]
  固定された2次元近辺アーキテクチャにおいて,各層が$Theta(n)$ランダムゲートからなる深さ$sqrtn cdot tildeO(k3)$のランダム回路により,およそ$k$の独立置換が得られることを示す。 我々の結果は、数ラウンドで$k$input-outputペアにアクセスする攻撃者に対して、証明可能な統計的セキュリティを提供する、特に単純で実践的なブロック暗号構築と見なすことができる。
  論文  参考訳（メタデータ） (2025-02-11T00:54:24Z)
• 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)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• 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)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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