論文の概要: Laplace expansions and tree decompositions: polytime algorithm for shallow nearest-neighbour Boson Sampling

• arxiv url: http://arxiv.org/abs/2412.18664v1
• Date: Tue, 24 Dec 2024 19:34:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:25:59.377215
• Title: Laplace expansions and tree decompositions: polytime algorithm for shallow nearest-neighbour Boson Sampling
• Title（参考訳）: ラプラス展開と木分解:浅部近傍ボーソンサンプリングのためのポリ時間アルゴリズム
• Authors: Samo Novák, Raúl García-Patrón,
• Abstract要約: ボーソンサンプリング量子光学実験では、各光子を$m$モード干渉計に送信し、出力の占有パターンを測定する。 我々は,最寄りの浅層回路,すなわち深度$D = MathcalO(log m)$に対して,Cifuentes & Parrilo のアルゴリズムを適用して浅部干渉計の空間性を利用することができるという事実を利用する。
• 参考スコア（独自算出の注目度）: 0.30693357740321775
• License:
• Abstract: In a Boson Sampling quantum optical experiment we send $n$ individual photons into an $m$-mode interferometer and we measure the occupation pattern on the output. The statistics of this process depending on the permanent of a matrix representing the experiment, a #P-hard problem to compute, is the reason behind ideal and fully general Boson Sampling being hard to simulate on a classical computer. We exploit the fact that for a nearest-neighbour shallow circuit, i.e. depth $D = \mathcal{O}(\log m)$, one can adapt the algorithm by Clifford & Clifford (2018) to exploit the sparsity of the shallow interferometer using an algorithm by Cifuentes & Parrilo (2016) that can efficiently compute a permanent of a structured matrix from a tree decomposition. Our algorithm generates a sample from a shallow circuit in time $\mathcal{O}(n^22^\omega \omega^2) + \mathcal{O}(\omega n^3)$, where $\omega$ is the treewidth of the decomposition which satisfies $\omega \le 2D$ for nearest-neighbour shallow circuits. The key difference in our work with respect to previous work using similar methods is the reuse of the structure of the tree decomposition, allowing us to adapt the Laplace expansion used by Clifford & Clifford which removes a significant factor of $m$ from the running time, especially as $m>n^2$ is a requirement of the original Boson Sampling proposal.
• Abstract（参考訳）: ボーソンサンプリング量子光学実験では、各光子を$m$モード干渉計に送信し、出力の占有パターンを測定する。 この過程の統計は、実験を表す行列の永久性、計算すべき#Pハード問題に依存するが、これは、理想的で完全に一般的なボソンサンプリングが古典的なコンピュータ上でシミュレートするのが困難である理由である。 depth $D = \mathcal{O}(\log m)$ は Clifford & Clifford (2018) のアルゴリズムに適応し、木分解から構造行列の永久性を効率的に計算できる Cifuentes & Parrilo (2016) のアルゴリズムを用いる。 我々のアルゴリズムは, 浅部回路のサンプルを$\mathcal{O}(n^22^\omega \omega^2) + \mathcal{O}(\omega n^3)$, ここで$\omega$は, 近辺の浅部回路に対して$\omega \le 2D$を満たす分解のツリー幅である。 特に$m>n^2$はオリジナルのBoson Samplingの提案の要件であるので、Clifford & Clifford が使用した Laplace 拡張を実行時から重要な要素を除去できる。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging [8.990961435218544]
  本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。 Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。 量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
  論文  参考訳（メタデータ） (2023-11-05T03:33:44Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings [9.066817876491053]
  我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。 幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。 提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。 我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
  論文  参考訳（メタデータ） (2022-02-07T14:43:35Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。 我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
  論文  参考訳（メタデータ） (2021-12-15T21:44:05Z)
• Fast simulation of planar Clifford circuits [0.0]
  一般的な量子回路は指数時間で古典的にシミュレートすることができる。 ツリー幅と平面性はクリフォード回路シミュレーションの改善に有効であることを示す。
  論文  参考訳（メタデータ） (2020-09-07T16:27:09Z)
• Faster classical Boson Sampling [0.15229257192293197]
  平均ケースタイムの複雑さがより速く、$m$が$n$に比例するBoson Samplingのアルゴリズムを提案する。 この結果により、ボソンサンプリングによる量子計算の超越性を確立するために必要な問題サイズが増大する。
  論文  参考訳（メタデータ） (2020-05-07T20:01:02Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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