論文の概要: Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality
- arxiv url: http://arxiv.org/abs/2510.00168v1
- Date: Tue, 30 Sep 2025 18:40:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-03 14:32:17.17062
- Title: Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality
- Title（参考訳）: パウリ次元を用いた一意チャネルのクエリ-最適推定
- Authors: Sabee Grewal, Daniel Liang,
- Abstract要約: パウリスペクトルが小部分群で支持されるユニタリチャネルのプロセストモグラフィーについて検討した。
我々は,$O(2k/epsilon)$クエリを用いてこれを実現するアルゴリズムを提案する。
また,近似クリフォード回路を用いた深度O(log n)$回路の構成を学習するための計算効率のよいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.8594140167290097
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study process tomography of unitary channels whose Pauli spectrum is supported on a small subgroup. Given query access to an unknown unitary channel whose Pauli spectrum is supported on a subgroup of size $2^k$, our goal is to output a classical description that is $\epsilon$-close to the unknown unitary in diamond distance. We present an algorithm that achieves this using $O(2^k/\epsilon)$ queries, and we prove matching lower bounds, establishing query optimality of our algorithm. When $k = 2n$, so that the support is the full Pauli group, our result recovers the query-optimal $O(4^n/\epsilon)$-query algorithm of Haah, Kothari, O'Donnell, and Tang [FOCS '23]. Our result has two notable consequences. First, we give a query-optimal $O(4^k/\epsilon)$-query algorithm for learning quantum $k$-juntas -- unitary channels that act non-trivially on only $k$ of the $n$ qubits -- to accuracy $\epsilon$ in diamond distance. This represents an exponential improvement in both query and time complexity over prior work. Second, we give a computationally efficient algorithm for learning compositions of depth-$O(\log \log n)$ circuits with near-Clifford circuits, where "near-Clifford" means a Clifford circuit augmented with at most $O(\log n)$ non-Clifford single-qubit gates. This unifies prior work, which could handle only constant-depth circuits or near-Clifford circuits, but not their composition.
- Abstract（参考訳）: パウリスペクトルが小部分群で支持されるユニタリチャネルのプロセストモグラフィーについて検討した。
パウリスペクトルが2^k$のサブグループでサポートされている未知のユニタリチャネルへのクエリアクセスを考えると、我々のゴールはダイヤモンド距離の未知ユニタリに$\epsilon$-closeという古典的な記述を出力することである。
我々は,$O(2^k/\epsilon)$クエリを用いてこれを実現するアルゴリズムを提案する。
サポートがパウリ群であるような$k = 2n$の場合、我々の結果は、Haah, Kothari, O'Donnell, Tang [FOCS '23] のクエリ最適化 $O(4^n/\epsilon)$-query アルゴリズムを復元する。
私たちの結果は2つの顕著な結果をもたらす。
まず、クエリ最適化の$O(4^k/\epsilon)$-queryアルゴリズムで量子$k$-juntasを学習する。
これは、前処理よりもクエリと時間の複雑さの両方が指数関数的に改善したことを意味する。
第二に、深度$O(\log \log n)$回路を近クリフォード回路で学習するための計算効率のよいアルゴリズムを与え、そこでは「ニアクリフォード」とは、少なくともO(\log n)$非クリフォード単一キュービットゲートで拡張されたクリフォード回路を意味する。
これは、定数深度回路や近クリフォード回路のみを扱うことができるが、それらの構成は扱えない、以前の作業を統合するものである。
関連論文リスト
- Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。
コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。
我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文 参考訳（メタデータ） (2025-09-25T07:39:25Z) - Process Tomography for Clifford Unitaries [0.08594140167290097]
未知の$n$-qubitユニタリ$C$上で量子プロセストモグラフィーを行うアルゴリズムを提案する。
我々のアルゴリズムは$Cdagger$を問わずに同じ性能を達成する。
論文 参考訳（メタデータ） (2025-05-12T21:11:04Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.43123403062068827]
クリフォードゲートと$O(log n)$非クリフォードゲートで用意された量子状態を効率的に学習するアルゴリズムのペアを与える。
具体的には、$n$-qubit state $|psirangle$を少なくとも$t$非クリフォードゲートで準備するために、我々のアルゴリズムは$mathsfpoly(n,2t,1/varepsilon)$timeと$|psirangle$のコピーを使って、ほとんどのゲートで距離を追跡するために$|psirangle$を学ぶ。
論文 参考訳（メタデータ） (2023-05-22T18:49:52Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。