論文の概要: On computational complexity and average-case hardness of shallow-depth boson sampling
- arxiv url: http://arxiv.org/abs/2405.01786v1
- Date: Fri, 3 May 2024 00:12:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-06 14:05:10.209892
- Title: On computational complexity and average-case hardness of shallow-depth boson sampling
- Title(参考訳): 浅深度ボソンサンプリングにおける計算複雑性と平均ケース硬度について
- Authors: Byeongseon Go, Changhun Oh, Hyunseok Jeong,
- Abstract要約: 古典的にシミュレートが難しいと考えられる計算タスクであるボソンサンプリングは、量子計算の優位性を示すことを約束する。
実験的な実装におけるノイズは、古典的にシミュレート可能で、古典的なイントラクタビリティを妥協するボソンサンプリングをレンダリングする可能性があり、大きな課題となる。
浅深さ線形光回路を用いたボソンサンプリングによる量子計算の優位性の実現可能性について検討する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Boson sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering boson sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms under various noise models that can efficiently simulate boson sampling as noise rates increase with circuit depth. To address this issue particularly related to circuit depth, we explore the viability of achieving quantum computational advantage through boson sampling with shallow-depth linear optical circuits. Specifically, as the average-case hardness of estimating output probabilities of boson sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state boson sampling subject to lossy environments and for the logarithmic-depth Gaussian boson sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth boson sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth boson sampling.
- Abstract(参考訳): ボソンサンプリング(Boson sample)は、古典的にシミュレートするのが難しい計算タスクであり、短期的な量子デバイスを用いた量子計算の優位性を実証する約束を果たすことが期待されている。
しかし、実験的な実装におけるノイズは大きな課題となり、ボソンサンプリングを古典的にシミュレートし、古典的なインタラクタビリティを損なう可能性がある。
多くの研究が、回路深度でノイズ率が増加するにつれてボソンサンプリングを効率的にシミュレートできる様々なノイズモデルの下で古典的アルゴリズムを提案している。
特に回路深度に関連するこの問題に対処するため,浅深さ線形光回路を用いたボソンサンプリングによる量子計算の優位性の実現可能性について検討する。
具体的には、ボソンサンプリングの出力確率を推定する平均ケース硬度は、その古典的難易度を示す上で重要な要素であるため、対数-深度関係に限定した平均ケース硬度を確立する。
また,損失環境下での対数深度フォック状態ボソンサンプリングおよび対数深度ガウスボソンサンプリングのための平均ケース硬度を求める。
対数深度ボソンサンプリングの古典的シミュレーション硬度に対する複雑性理論的背景を提供することにより、浅度深度ボソンサンプリングによる量子優位性のよりノイズ耐性を示すための重要なステップとなることを期待する。
関連論文リスト
- Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond [0.0]
一般連続変数サンプリング問題に対する古典的シミュレーションツールを提案する。
我々はサンプリング問題を、単純な少数体ハミルトンの基底状態を見つけるための問題として再定式化する。
我々はガウスボソンサンプリングをシミュレートして手法を検証する。
論文 参考訳(メタデータ) (2024-10-24T13:43:06Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳(メタデータ) (2024-08-22T08:21:28Z) - QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEAはノイズ適応型量子回路のインタイムスパース探索である。
1)トレーニング中の暗黙の回路容量と(2)雑音の頑健さの2つの主要な目標を達成することを目的としている。
提案手法は, 量子ゲート数の半減と回路実行の2倍の時間節約で, 最先端の計算結果を確立する。
論文 参考訳(メタデータ) (2024-01-10T22:33:00Z) - Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy [1.7635061227370266]
ボソンサンプリング(英: Boson sample)は、古典的なコンピュータを用いて効率的にシミュレーションすることが難しいサンプリングタスクである。
本稿では,幾何学的局所的アーキテクチャに関連する問題を克服できる,浅部線形光回路アーキテクチャを提案する。
論文 参考訳(メタデータ) (2023-06-19T02:11:54Z) - Classical algorithm for simulating experimental Gaussian boson sampling [2.1684911254068906]
ガウスボソンサンプリングは実験的量子優位性を示す有望な候補である。
高い光子損失率とノイズの存在にもかかわらず、それらは現在、最もよく知られた古典的アルゴリズムで古典的にシミュレートすることが難しいと主張されている。
本稿ではガウスボソンサンプリングをシミュレートする古典的テンソルネットワークアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-06T14:19:48Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳(メタデータ) (2022-12-12T15:06:32Z) - Noise thresholds for classical simulability of non-linear Boson sampling [4.812718493682455]
我々は,高次非線形性を導入し,問題の計算複雑性とプロトコルの雑音に対する堅牢性を高める。
以上の結果から,入出力状態におけるシングルモードKerrの非線形性の追加は,線形光学的進化を維持しつつも,Bosonサンプリングプロトコルがノイズに対してより堅牢であることが示唆された。
論文 参考訳(メタデータ) (2022-02-24T12:17:28Z) - Simulating the Mott transition on a noisy digital quantum computer via
Cartan-based fast-forwarding circuits [62.73367618671969]
動的平均場理論(DMFT)は、ハバードモデルの局所グリーン関数をアンダーソン不純物のモデルにマッピングする。
不純物モデルを効率的に解くために、量子およびハイブリッド量子古典アルゴリズムが提案されている。
この研究は、ノイズの多いデジタル量子ハードウェアを用いたMott相転移の最初の計算を提示する。
論文 参考訳(メタデータ) (2021-12-10T17:32:15Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳(メタデータ) (2021-08-09T18:00:05Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳(メタデータ) (2020-05-05T20:11:53Z) - Boson Sampling with Gaussian input states: toward efficient scaling and certification [0.0]
本稿では,Boson Smpling実験を実際に実現可能な方法を提案する。
本稿では,切り替え可能なデュアルホモジンと単一光子検出,時間ループ技術,散乱ショットに基づくボソンサンプリングの組み合わせを提案する。
論文 参考訳(メタデータ) (2018-12-21T07:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。