論文の概要: Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation
- arxiv url: http://arxiv.org/abs/2611.16456v1
- Date: Thu, 12 Nov 2026 08:08:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.396327
- Title: Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation
- Title(参考訳): 局所的パウリ測定によるスパースグラフ状態の学習:厳密な非適応境界と適応分離
- Abstract要約: Ouyang と Tomamichel は$O(d2log n)$ copy suffice for $d$-regular graphs を示した。
d3ln nle n$の場合、すべての非適応戦略は$(d2log n)$コピーが必要である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study how many copies of an unknown $n$-qubit graph state are needed to identify its graph when every qubit is measured in the $X$, $Y$ or $Z$ basis. Ouyang and Tomamichel showed that $O(d^2\log n)$ copies suffice for $d$-regular graphs, while any measurement needs $Ω(d\log n)$, and asked whether the quadratic dependence on $d$ is necessary. We show that it is for nonadaptive learners: if $d^3\ln n\le n$, every nonadaptive strategy needs $Ω(d^2\log n)$ copies, even with an unrestricted classical decoder and even if a small constant fraction of the edges may be reported wrongly. We then show that adaptivity between copies can beat this barrier. On connected bipartite $d$-regular graphs of logarithmic diameter whose bipartition is hidden, nonadaptive learners still need $Θ(d^2\log n)$ copies, but a breadth-first adaptive learner needs only $O(d\log^2 n/\log\log n)$; revealing the bipartition brings the nonadaptive cost down to $Θ(d\log n)$. The lower bounds rest on a simple fact: one copy reveals at most the binary nullity of a principal submatrix of the adjacency matrix. We control this nullity for random unions of perfect matchings through Fourier estimates and, in the bipartite case, a method-of-types argument.
- Abstract(参考訳): 我々は、未知の$n$-qubitグラフ状態のコピー数を調べ、そのグラフが$X$、$Y$、または$Z$ベースで測定されたときにそのグラフを特定する。
Ouyang と Tomamichel は $O(d^2\log n)$ copy suffice for $d$-regular graphs を示したが、任意の測定には $Ω(d\log n)$ が必要であり、$d$ への二次依存は必要かどうかを問うた。
d^3\ln n\le n$ ならば、すべての非適応戦略は $Ω(d^2\log n)$ コピーが必要である。
次に、コピー間の適応性が、この障壁を破ることを示します。
連結二分法 $d$-正則な対数直径のグラフにおいて、二分法は隠蔽されているが、非適応学習者はまだ$(d^2\log n)$コピーを必要とするが、幅優先適応学習者は$O(d\log^2 n/\log\log n)$のみを必要とする。
1つのコピーは、隣接行列の主部分行列の少なくとも2進零性を明らかにする。
フーリエ推定(英語版)による完全マッチングのランダムな和に対して、この零性を制御し、バイパルタイトの場合、メソッド・オブ・タイプ(英語版)の議論を行う。
関連論文リスト
- Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting [1.0152838128195467]
我々は、全てのクエリが、結果が観測される前に固定される非適応的なスキームについて研究する。
我々のスキームは$O(barklog n)$クエリを使用し、$O(barklog n)$ decoding timeで正確なリカバリを実現する。
これにより、以前の$O(bark1+log n)$ decoding guarantee for any fixed $>0$, while maintain the same query order。
論文 参考訳(メタデータ) (2026-09-27T16:07:15Z) - High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。
我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文 参考訳(メタデータ) (2026-02-01T17:05:31Z) - Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳(メタデータ) (2026-01-07T22:07:44Z) - A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs [33.51066694357509]
ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討し、各クエリは、クエリされたノード間に少なくとも1つのエッジが存在するかどうかを報告する。
Erds--Rényi (ER) graphs $GsimmathrmER(n,q)$ in the non-adaptive set, where the expected number of edges is $bark=qbinomn2$。
我々は、最近非適応型グループテストのために開発されたバイナリ分割アプローチをERグラフ設定に拡張し、それを証明した。
論文 参考訳(メタデータ) (2025-11-21T13:34:29Z) - Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。
コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。
我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文 参考訳(メタデータ) (2025-09-25T07:39:25Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳(メタデータ) (2024-06-03T17:56:58Z) - Learning quantum graph states with product measurements [22.463154358632472]
我々は、未知の$n$-qubit量子グラフ状態の同一コピーを製品測定で学習する問題を考察する。
このようなグラフ状態の複数の同一コピー上で製品計測を用いて学習する明示的なアルゴリズムを詳述する。
論文 参考訳(メタデータ) (2022-05-13T02:55:21Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳(メタデータ) (2021-10-02T07:41:17Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。