論文の概要: Bypassing orthogonalization in the quantum DPP sampler

• arxiv url: http://arxiv.org/abs/2503.05906v1
• Date: Fri, 07 Mar 2025 19:57:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-11 15:50:20.002437
• Title: Bypassing orthogonalization in the quantum DPP sampler
• Title（参考訳）: 量子DPPサンプリング器における直交化をバイパスする
• Authors: Michaël Fanuel, Rémi Bardenet,
• Abstract要約: 我々は、Kerenidisらの形式にインスパイアされた単純な回路が、2022年に我々がアプリケーションで遭遇したことのないタイプのDPPをサンプリングしたことを示す。 第2のコントリビューションは振幅増幅を用いて、回路深さの価格で受け入れ確率を$a$から$1-a$に上げることである。
• 参考スコア（独自算出の注目度）: 8.30255326875704
• License:
• Abstract: Given an $n\times r$ matrix $X$ of rank $r$, consider the problem of sampling $r$ integers $\mathtt{C}\subset \{1, \dots, n\}$ with probability proportional to the squared determinant of the rows of $X$ indexed by $\mathtt{C}$. The distribution of $\mathtt{C}$ is called a projection determinantal point process (DPP). The vanilla classical algorithm to sample a DPP works in two steps, an orthogonalization in $\mathcal{O}(nr^2)$ and a sampling step of the same cost. The bottleneck of recent quantum approaches to DPP sampling remains that preliminary orthogonalization step. For instance, (Kerenidis and Prakash, 2022) proposed an algorithm with the same $\mathcal{O}(nr^2)$ orthogonalization, followed by a $\mathcal{O}(nr)$ classical step to find the gates in a quantum circuit. The classical $\mathcal{O}(nr^2)$ orthogonalization thus still dominates the cost. Our first contribution is to reduce preprocessing to normalizing the columns of $X$, obtaining $\mathsf{X}$ in $\mathcal{O}(nr)$ classical operations. We show that a simple circuit inspired by the formalism of Kerenidis et al., 2022 samples a DPP of a type we had never encountered in applications, which is different from our target DPP. Plugging this circuit into a rejection sampling routine, we recover our target DPP after an expected $1/\det \mathsf{X}^\top\mathsf{X} = 1/a$ preparations of the quantum circuit. Using amplitude amplification, our second contribution is to boost the acceptance probability from $a$ to $1-a$ at the price of a circuit depth of $\mathcal{O}(r\log n/\sqrt{a})$ and $\mathcal{O}(\log n)$ extra qubits. Prepending a fast, sketching-based classical approximation of $a$, we obtain a pipeline to sample a projection DPP on a quantum computer, where the former $\mathcal{O}(nr^2)$ preprocessing bottleneck has been replaced by the $\mathcal{O}(nr)$ cost of normalizing the columns and the cost of our approximation of $a$.
• Abstract（参考訳）: $n\times r$ matrix $X$ of rank $r$を与えられたとき、$r$ integers $\matht{C}\subset \{1, \dots, n\}$をサンプリングする問題を考える。 $\mathtt{C}$ の分布は射影行列点過程 (DPP) と呼ばれる。 DPPをサンプリングするバニラ古典アルゴリズムは、$\mathcal{O}(nr^2)$の直交化と、同じコストのサンプリングステップの2つのステップで機能する。 DPPサンプリングに対する近年の量子アプローチのボトルネックは、その事前直交化段階のままである。 例えば (Kerenidis and Prakash, 2022) は同じ$\mathcal{O}(nr^2)$直交化のアルゴリズムを提案し、続いて$\mathcal{O}(nr)$ 古典的なステップで量子回路のゲートを見つける。 古典的な$\mathcal{O}(nr^2)$直交化は依然としてコストを支配している。 最初のコントリビューションは、プリプロセスを減らすことで、$X$の列を正規化し、$\mathsf{X}$ in $\mathcal{O}(nr)$ 古典演算を得ることです。 我々は、Kerenidis et al の定式化にインスパイアされた単純な回路が、アプリケーションで遭遇したことのないタイプの DPP を2022年にサンプリングし、ターゲットの DPP と異なることを示す。 この回路をリジェクションサンプリングルーチンに挿入すると、1/\det \mathsf{X}^\top\mathsf{X} = 1/a$の量子回路の準備が期待された後にターゲットDPPを回復する。 振幅増幅を用いて、回路深さ$\mathcal{O}(r\log n/\sqrt{a})$と$\mathcal{O}(\log n)$余剰量子ビットの価格で、受け入れ確率を$a$から$-a$に上げる。 高速でスケッチベースの古典近似が$a$になる前に、量子コンピュータ上の射影 DPP をサンプリングするためのパイプラインを取得し、そこでは以前の$\mathcal{O}(nr^2) のプリプロセッシングボトルネックが$\mathcal{O}(nr)$のカラムの正規化コストと $a$ の近似のコストに置き換えられた。

関連論文リスト

• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPは1970年代の量子光学のモデルとしてマッキによって導入された。 ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。 バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
  論文  参考訳（メタデータ） (2023-05-25T08:43:11Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• A Faster Sampler for Discrete Determinantal Point Processes [10.355938901584567]
  Discrete Determinantal Point Processs (DPP) は、データセットのサブサンプル化に幅広い可能性を持つ。 最悪の場合、サンプリングコストは$O(n3)$で、nは基底集合の要素の数である。 この禁止コストに対する一般的な回避策は、低ランクカーネルによって定義されたDPPをサンプリングすることである。
  論文  参考訳（メタデータ） (2022-10-31T14:37:54Z)
• Misspecified Phase Retrieval with Generative Priors [15.134280834597865]
  単一のインデックスモデル $y の $m$ i.d.realization から$n$-dimensional signal $mathbfx$ を推定する。 どちらのステップも、適切な条件下では、$sqrt(klog L)cdot (log m)/m$の統計的レートを享受できることが示される。
  論文  参考訳（メタデータ） (2022-10-11T16:04:11Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Denoising modulo samples: k-NN regression and tightness of SDP relaxation [5.025654873456756]
  サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。 サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
  論文  参考訳（メタデータ） (2020-09-10T13:32:46Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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