論文の概要: Learning the closest product state

• arxiv url: http://arxiv.org/abs/2411.04283v1
• Date: Wed, 06 Nov 2024 22:08:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:38:21.364623
• Title: Learning the closest product state
• Title（参考訳）: 最寄りの製品状態を学ぶ
• Authors: Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Allen Liu, Ryan O'Donnell, Ewin Tang,
• Abstract要約: 我々は、$rho$のコピーを与えられた未知の$n$-qubit量子状態$rho$に対する最適忠実度を持つ積状態を見つける問題を研究する。 これは量子学習における基本的な問題の基本的例であり、任意の状態への単純な近似を効率的に学習することは可能か? 我々は、$N = ntextpoly (1/varepsilon)$ copy of $rho$ and $textpoly(N)$ classical overheadを用いて、Fidelity $varepsilon$-close で最適な製品状態を求めるアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 7.292570558048588
• License:
• Abstract: We study the problem of finding a product state with optimal fidelity to an unknown $n$-qubit quantum state $\rho$, given copies of $\rho$. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a simple approximation to an arbitrary state? We give an algorithm which finds a product state with fidelity $\varepsilon$-close to optimal, using $N = n^{\text{poly}(1/\varepsilon)}$ copies of $\rho$ and $\text{poly}(N)$ classical overhead. We further show that estimating the optimal fidelity is NP-hard for error $\varepsilon = 1/\text{poly}(n)$, showing that the error dependence cannot be significantly improved. For our algorithm, we build a carefully-defined cover over candidate product states, qubit by qubit, and then demonstrate that extending the cover can be reduced to approximate constrained polynomial optimization. For our proof of hardness, we give a formal reduction from polynomial optimization to finding the closest product state. Together, these results demonstrate a fundamental connection between these two seemingly unrelated questions. Building on our general approach, we also develop more efficient algorithms in three simpler settings: when the optimal fidelity exceeds $5/6$; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state.
• Abstract（参考訳）: 我々は、$\rho$のコピーを与えられた未知の$n$-qubit量子状態$\rho$に対する最適忠実度を持つ積状態を見つける問題を研究する。 これは量子学習における基本的な問題の基本的例であり、任意の状態への単純な近似を効率的に学習することは可能か? N = n^{\text{poly}(1/\varepsilon)}$ $\rho$と$\text{poly}(N)$ 古典的オーバーヘッドを用いて、フィデリティが$\varepsilon$-クロースな積状態を求めるアルゴリズムを与える。 さらに,誤差$\varepsilon = 1/\text{poly}(n)$に対して最適忠実度の推定がNPハードであることを示し,誤差依存を著しく改善できないことを示す。 提案アルゴリズムでは, 候補積状態, qubit by qubit に対して慎重に定義された被覆を構築し, カバーの拡張を近似的に制約された多項式最適化に還元できることを実証する。 硬さの証明のために、多項式最適化から最も近い積状態を見つけるための公式な還元を与える。 これらの結果は、これら2つの一見無関係な疑問の間に基礎的なつながりを示すものである。 我々の一般的なアプローチに基づいて、最適忠実度が5/6$を超えるとき、個別の製品状態に制限されるとき、行列積状態の出力が許されるとき、より効率的なアルゴリズムを3つの単純な設定で開発する。

関連論文リスト

• Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
  我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。 我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
  論文  参考訳（メタデータ） (2024-02-20T06:23:36Z)
• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
  精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。 また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
  論文  参考訳（メタデータ） (2023-05-08T17:46:01Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies [21.690446677016247]
  我々は, 在庫管理システムを, 計画的地平線上でのリードタイム$L$とみなし, 供給は不確実であり, 注文量の関数である。 提案アルゴリズムは,O(L+sqrtT)$が$Lgeqlog(T)$である場合に,そのアルゴリズムのコストと,O(L+sqrtT)$に対する最適ポリシーとの相違(英語版)を生じることを示す。
  論文  参考訳（メタデータ） (2022-07-10T22:11:32Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy [26.69391745812235]
  本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。 これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
  論文  参考訳（メタデータ） (2020-11-11T17:48:00Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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