論文の概要: Speeding up the classical simulation of Gaussian boson sampling with
limited connectivity
- arxiv url: http://arxiv.org/abs/2311.05355v2
- Date: Fri, 10 Nov 2023 14:12:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-13 12:28:31.177025
- Title: Speeding up the classical simulation of Gaussian boson sampling with
limited connectivity
- Title（参考訳）: 限られた接続性を持つガウスボソンサンプリングの古典シミュレーションの高速化
- Authors: Tian-Yu Yang, Xiang-Bin Wang
- Abstract要約: 限られた接続性でGBSプロセスをシミュレートする拡張された古典的アルゴリズムを提案する。
これは、帯域幅$w$ in $O(nw2w)$ Time を持つ$n倍 n$対称行列のループハフニアンを計算する。
このアルゴリズムは、GBSの計算複雑性に制限のある接続がどう影響するかを明らかにするのに有用である。
- 参考スコア（独自算出の注目度）: 14.858108798474222
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gaussian Boson sampling (GBS) plays a crucially important role in
demonstrating quantum advantage. As a major imperfection, the limited
connectivity of the linear optical network weakens the quantum advantage result
in recent experiments. Here we present a faster classical algorithm to simulate
the GBS process with limited connectivity. In this work, we introduce an
enhanced classical algorithm for simulating GBS processes with limited
connectivity. It computes the loop Hafnian of an $n \times n$ symmetric matrix
with bandwidth $w$ in $O(nw2^w)$ time which is better than the previous fastest
algorithm which runs in $O(nw^2 2^w)$ time. This classical algorithm is helpful
on clarifying how limited connectivity affects the computational complexity of
GBS and tightening the boundary of quantum advantage in the GBS problem.
- Abstract（参考訳）: ガウスボソンサンプリング(GBS)は量子優位性を示す上で重要な役割を果たす。
主な欠陥として、線形光ネットワークの限られた接続は、最近の実験で量子優位性を弱める。
ここでは、限られた接続でGBSプロセスをシミュレートする高速な古典的アルゴリズムを提案する。
本稿では,接続性が制限されたgbsプロセスシミュレーションのための拡張古典アルゴリズムを提案する。
ループhafnianをn \times n$対称行列で計算し、帯域幅$w$ in $o(nw2^w)$ time で計算する。
この古典的アルゴリズムは、GBSの計算複雑性に限定的な接続がどう影響するかを明確にし、GBS問題における量子優位性の境界を狭めるのに役立つ。
関連論文リスト
- Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。
また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
論文 参考訳（メタデータ） (2024-07-10T14:08:58Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳（メタデータ） (2023-10-09T03:10:42Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳（メタデータ） (2023-05-23T16:17:57Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law
Interactions [0.9634136878988853]
距離において1/ラルファ$の強度が減衰するパワーロー相互作用は、情報処理のための実験的に実現可能な資源を提供する。
我々はこれらの相互作用のパワーを活用して、任意の数のターゲットを持つ高速量子ファンアウトゲートを実装する。
我々は、ファリングが古典的に難解であるという標準的な仮定の下で、$alpha le D$ のパワーロー系は、短時間でも古典的にシミュレートすることは困難であることを示す。
論文 参考訳（メタデータ） (2020-07-01T18:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。