論文の概要: Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance

• arxiv url: http://arxiv.org/abs/2604.00203v1
• Date: Tue, 31 Mar 2026 20:13:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-02 16:44:31.707896
• Title: Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance
• Title（参考訳）: ダイヤモンド距離におけるパウリスパース単位近傍の問合せ学習
• Authors: Zahra Honjani, Mohsen Heidari,
• Abstract要約: このクラスは、スパースユニタリ、量子$k$-juntas、2k$-Pauli次元チャネル、深さ$O(loglog n)$回路の構成を含むよく研究された族を一般化する。
• 参考スコア（独自算出の注目度）: 6.852394426719304
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of learning nearly $(s,ε)$-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most $s$ components with at most $ε$ residual mass in Pauli $\ell_1$-norm. This class generalizes well-studied families, including sparse unitaries, quantum $k$-juntas, $2^k$-Pauli dimensional channels, and compositions of depth $O(\log\log n)$ circuits with near-Clifford circuits. Given query access to an unknown nearly sparse unitary $U$, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to $U$. We design a learning algorithm achieving this guarantee using $\tilde{O}(s^6/ε^4)$ forward queries to $U$, and running time polynomial in relevant parameters. A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary $U$, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold $θ$, extending existing sparse recovery techniques to general unitaries. We also study the broader class of unitaries with bounded Pauli $\ell_1$-norm. For that class, we prove an exponential query lower bound $Ω(2^{n/2})$. We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli $\ell_1$-norm uniformly bounded by $L_1$ are learnable with $\tilde{O}(L_1^8/ε^{16})$.
• Abstract（参考訳）: 我々は、ほぼ$(s,ε)$-sparseユニタリを学習する問題を研究し、つまり、パウリスペクトルは、少なくとも$s$成分に集中しており、パウリ$\ell_1$-normにおいて、少なくとも$ε$残質量を持つことを意味する。 このクラスは、スパースユニタリ、量子$k$-juntas、2^k$-Pauli次元チャネル、深さ$O(\log\log n)$回路の合成を含むよく研究された族を一般化する。 未知のほとんどスパースなユニタリな$U$へのクエリアクセスを考えると、我々のゴールは、ダイヤモンド距離がU$に近い量子チャネルを効率的に(時間とクエリの複雑さの両方で)構築することである。 我々は,$\tilde{O}(s^6/ε^4)$ forward query to $U$,および関連するパラメータにおける時間多項式の実行を用いて,この保証を達成する学習アルゴリズムを設計する。 鍵となるコントリビューションは、任意の未知のユニタリ$U$へのクエリアクセスが与えられたとき、与えられた閾値$θ$を超える全てのパウリ係数(共有グローバルフェーズまで)を推定し、既存のスパースリカバリ技術を一般的なユニタリに拡張する効率的な量子アルゴリズムである。 また、有界なパウリ$\ell_1$-ノルムでより広いユニタリのクラスを研究する。 このクラスに対して、指数的なクエリを$Ω(2^{n/2})$以下で証明する。 入力状態のセットに制限されたダイヤモンド距離である、より緩和された精度測定基準を導入する。 そして、この計量の下では、パウリ$\ell_1$-ノルムが一様有界な$L_1$を持つユニタリが、$\tilde{O}(L_1^8/ε^{16})$で学習可能であることを示す。

関連論文リスト

• Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality [0.8594140167290097]
  パウリスペクトルが小部分群で支持されるユニタリチャネルのプロセストモグラフィーについて検討した。 我々は,$O(2k/epsilon)$クエリを用いてこれを実現するアルゴリズムを提案する。 また,近似クリフォード回路を用いた深度O(log n)$回路の構成を学習するための計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-09-30T18:40:42Z)
• Testing and learning structured quantum Hamiltonians [4.137418441736385]
  正規化フロベニウスノルムの下で、未知の$n$qubit Hamiltonian $H$をクエリからその進化作用素 $e-iHt$ までテストし、学習する問題を考察する。
  論文  参考訳（メタデータ） (2024-10-31T17:54:13Z)
• Optimal algorithms for learning quantum phase states [8.736370689844682]
  未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。 また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
  論文  参考訳（メタデータ） (2022-08-16T17:15:06Z)
• 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)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• 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)
• 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)

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

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