論文の概要: Classical simulation of boson sampling based on graph structure
- arxiv url: http://arxiv.org/abs/2110.01564v2
- Date: Tue, 22 Feb 2022 16:15:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-12 14:10:16.894201
- Title: Classical simulation of boson sampling based on graph structure
- Title（参考訳）: グラフ構造に基づくボソンサンプリングの古典シミュレーション
- Authors: Changhun Oh, Youngrong Lim, Bill Fefferman, Liang Jiang
- Abstract要約: 線形光回路のグラフ構造を利用する単一光子およびガウス入力状態に対する古典的なサンプリングアルゴリズムを提案する。
回路深さが格子間隔の二次よりも小さい場合、指数的に小さな誤差で効率的なシミュレーションが可能であることを示す。
近年の数値的なガウスボソンサンプリング実験により,木幅に制限のある木幅アルゴリズムが実験データよりも大きな可能性を示す可能性が示された。
- 参考スコア（独自算出の注目度）: 2.5496329090462626
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Boson sampling is a fundamentally and practically important task that can be
used to demonstrate quantum supremacy using noisy intermediate-scale quantum
devices. In this work, we present classical sampling algorithms for
single-photon and Gaussian input states that take advantage of a graph
structure of a linear-optical circuit. The algorithms' complexity grows as
so-called treewidth, which is closely related to the connectivity of a given
linear-optical circuit. Using the algorithms, we study approximated simulations
for local Haar-random linear-optical circuits. For equally spaced initial
sources, we show that when the circuit depth is less than the quadratic in the
lattice spacing, the efficient simulation is possible with an exponentially
small error. Notably, right after this depth, photons start to interfere each
other and the algorithms' complexity becomes sub-exponential in the number of
sources, implying that there is a sharp transition of its complexity. Finally,
when a circuit is sufficiently deep enough for photons to typically propagate
to all modes, the complexity becomes exponential as generic sampling
algorithms. We numerically implement a likelihood test with a recent Gaussian
boson sampling experiment and show that the treewidth-based algorithm with a
limited treewidth renders a larger likelihood than the experimental data.
- Abstract（参考訳）: ボソンサンプリングは、ノイズの多い中間スケールの量子デバイスを用いて量子超越性を実証するために、基本的で事実上重要なタスクである。
本稿では,線形光学回路のグラフ構造を利用した単一光子およびガウス入力状態の古典的なサンプリングアルゴリズムを提案する。
アルゴリズムの複雑さは、与えられた線形光学回路の接続と密接な関係を持ついわゆる木幅として増大する。
アルゴリズムを用いて局所ハールランダム線形光回路の近似シミュレーションについて検討した。
等間隔初期源の場合、回路深さが格子間隔の二次よりも小さい場合、指数的に小さな誤差で効率的なシミュレーションが可能であることを示す。
特に、この深さのすぐ後、光子は互いに干渉し合い始め、アルゴリズムの複雑さはソースの数にサブ指数的になり、その複雑さの急激な変化が示唆される。
最後に、回路が光子が通常すべてのモードに伝播するのに十分な深さを持つと、複雑性は一般的なサンプリングアルゴリズムとして指数関数的になる。
近年のガウスボソンサンプリング実験により,木幅に制限のある木幅アルゴリズムが実験データよりも高い可能性を示す可能性試験を数値的に実施した。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Quantum optical classifier with superexponential speedup [3.262230127283452]
本稿では,バイナリ分類タスクのための量子光学パターン認識手法を提案する。
香港・ウー・マンデル干渉計の出力における2光子偶然の速度で物体を分類する。
論文 参考訳（メタデータ） (2024-04-23T17:55:49Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Simulating lossy Gaussian boson sampling with matrix product operators [7.33258560389563]
N_textoutproptosqrtN$の生存光子のスケーリングにより,効率的なテンソルネットワークシミュレーションが可能であることを示す。
ハードウェアアクセラレーションによるガウスボソンサンプリングにおける局所空間次元の増大による過去の課題を克服する。
論文 参考訳（メタデータ） (2023-01-30T12:10:39Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Classical simulation of bosonic linear-optical random circuits beyond
linear light cone [2.5496329090462626]
線形光回路の出力光子数分布からのサンプリングの古典的シミュラビリティについて検討する。
アルゴリズムの誤差は、ソース間の距離の2倍以下の深さまで指数関数的に小さいことを示す。
論文 参考訳（メタデータ） (2021-02-19T18:33:31Z) - Quadratic speedup for simulating Gaussian boson sampling [0.9236074230806577]
本稿では,ガウスボソンサンプリングの古典的シミュレーションのためのアルゴリズムを提案する。
アルゴリズムの複雑さは、検出された光子対の数において指数関数的であり、光子の数ではない。
改良されたループハフニアンアルゴリズムはスーパーコンピュータを必要とせずに純粋状態確率を計算することができることを示す。
論文 参考訳（メタデータ） (2020-10-29T13:53:30Z) - Efficient sampling from shallow Gaussian quantum-optical circuits with
local interactions [0.9786690381850354]
本研究では,ガウス状態の光子数確率分布から,浅く局所的な光回路を用いて効率よくサンプリングできることを実証する。
指数スケーリング光子損失を伴うディープ光回路からのサンプリングは古典的にシミュレート可能であるため,我々は局所的な相互作用を持つフォトニックプラットフォーム上で量子超越性を示すことが可能であることを示す。
論文 参考訳（メタデータ） (2020-09-24T17:10:42Z) - Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。
行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-15T13:40:07Z) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。
典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。
また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
論文 参考訳（メタデータ） (2019-12-31T19:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。