論文の概要: Faster classical Boson Sampling
- arxiv url: http://arxiv.org/abs/2005.04214v2
- Date: Tue, 26 May 2020 13:03:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-20 22:17:57.442344
- Title: Faster classical Boson Sampling
- Title（参考訳）: 古典ボソンサンプリングの高速化
- Authors: Peter Clifford and Rapha\"el Clifford
- Abstract要約: 平均ケースタイムの複雑さがより速く、$m$が$n$に比例するBoson Samplingのアルゴリズムを提案する。
この結果により、ボソンサンプリングによる量子計算の超越性を確立するために必要な問題サイズが増大する。
- 参考スコア（独自算出の注目度）: 0.15229257192293197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Since its introduction Boson Sampling has been the subject of intense study
in the world of quantum computing. The task is to sample independently from the
set of all $n \times n$ submatrices built from possibly repeated rows of a
larger $m \times n$ complex matrix according to a probability distribution
related to the permanents of the submatrices. Experimental systems exploiting
quantum photonic effects can in principle perform the task at great speed. In
the framework of classical computing, Aaronson and Arkhipov (2011) showed that
exact Boson Sampling problem cannot be solved in polynomial time unless the
polynomial hierarchy collapses to the third level. Indeed for a number of years
the fastest known exact classical algorithm ran in $O({m+n-1 \choose n} n 2^n
)$ time per sample, emphasising the potential speed advantage of quantum
computation. The advantage was reduced by Clifford and Clifford (2018) who gave
a significantly faster classical solution taking $O(n 2^n +
\operatorname{poly}(m,n))$ time and linear space, matching the complexity of
computing the permanent of a single matrix when $m$ is polynomial in $n$.
We continue by presenting an algorithm for Boson Sampling whose average-case
time complexity is much faster when $m$ is proportional to $n$. In particular,
when $m = n$ our algorithm runs in approximately $O(n\cdot1.69^n)$ time on
average. This result further increases the problem size needed to establish
quantum computational supremacy via Boson Sampling.
- Abstract（参考訳）: ボソンサンプリングの導入以来、量子コンピューティングの世界では激しい研究の対象となっている。
タスクは、すべての$n \times n$ submatricesの集合から独立にサンプリングすることであり、より大きい$m \times n$ complex matrixの行から、サブマトリクスの永続性に関連する確率分布に従って作られる。
量子フォトニック効果を利用した実験システムは、原理上、高速でタスクを実行することができる。
古典計算の枠組みにおいて、aaronson と arkhipov (2011) は多項式階層が3階に崩壊しない限り、正確なボソンサンプリング問題は多項式時間では解けないことを示した。
実際、何年もの間、最も正確な古典的アルゴリズムはサンプルあたりのO({m+n-1 \choose n} n 2^n )$時間で実行され、量子計算の潜在的な速度優位性を強調した。
この利点はcliffordとclifford (2018) によって減らされ、o(n 2^n + \operatorname{poly}(m,n))$の時間と線形空間を取り、m$が$n$の多項式であるとき、1つの行列の永続性を計算する複雑さと一致するという、かなり高速な古典解が与えられた。
平均ケースタイムの複雑さが、$m$が$n$に比例する場合、ずっと高速なBoson Smplingのアルゴリズムを提示し続けます。
特に、$m = n$のとき、我々のアルゴリズムは平均でおよそ$O(n\cdot1.69^n)の時間で動作する。
この結果は、ボーソンサンプリングによる量子計算超越性を確立するのに必要な問題サイズをさらに増加させる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。
また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
論文 参考訳（メタデータ） (2024-03-05T15:03:47Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-05-31T09:15:28Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。