論文の概要: Classical bounds on correlation-type Bell expressions and linear prepare-and-measure witnesses: efficient computation in parallel environments such as graphics processing units
- arxiv url: http://arxiv.org/abs/2503.21596v1
- Date: Thu, 27 Mar 2025 15:14:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:51:58.836937
- Title: Classical bounds on correlation-type Bell expressions and linear prepare-and-measure witnesses: efficient computation in parallel environments such as graphics processing units
- Title(参考訳): 相関型ベル表現と線形準備・測定証人の古典的境界--グラフィックス処理ユニットのような並列環境での効率的な計算
- Authors: István Márton, Erika Bene, Péter Diviánszky, Gábor Drótos,
- Abstract要約: 提案プログラムは,グラフィクス処理ユニット(GPU)を用いた行列$M$の$L_d$ノルムのブルート力計算を高速化することを目的としている。
CPUの代替も実装されており、アルゴリズムは任意の並列環境に適用できる。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: The presented program aims at speeding up the brute force computation of the $L_d$ norm of a matrix $M$ using graphics processing units (GPUs). Alternatives for CPUs have also been implemented, and the algorithm is applicable to any parallel environment. The $n\times m$ matrix $M$ has real elements which may represent coefficients of a bipartite correlation-type Bell expression or those of a linear prepare-and-measure (PM) witness. In this interpretation, the $L_1$ norm is the local bound of the given Bell expression, and the $L_d$ norm for $d\ge 2$ is the classical $d$-dimensional bound of the given PM witness, which is associated with the communication of $d$-level classical messages in the PM scenario. In both scenarios, the output is assumed to be binary. The code for GPUs is written in CUDA C and can utilize one NVIDIA GPU in a computer. To illustrate the performance of our implementation, we refer to Brierley et al. [arXiv:1609.05011] who needed approximately three weeks to compute the local bound on a Bell expression defined by a $42\times 42$ matrix on a standard desktop using a single CPU core. In contrast, our efficient implementation of the brute force algorithm allows us to reduce this to three minutes using a single NVIDIA RTX 6000 Ada graphics card on a desktop. For CPUs, the algorithm was implemented with OpenMP and MPI according to the shared and distributed memory models, respectively, and achieves a comparable speedup at a number of CPU cores around 100.
- Abstract(参考訳): 提案プログラムは,グラフィクス処理ユニット(GPU)を用いた行列$M$の$L_d$ノルムのブルート力計算を高速化することを目的としている。
CPUの代替も実装されており、アルゴリズムは任意の並列環境に適用できる。
n\times m$ matrix $M$ は実元を持ち、二部相関型ベル式や線形準備測度(PM)証人の係数を表す。
この解釈では、$L_1$ normは与えられたベル表現の局所的境界であり、$d\ge 2$の$L_d$ normは、与えられたPM目撃者の古典的な$d$次元境界であり、PMシナリオにおける$d$レベルの古典的メッセージの通信と関連している。
どちらのシナリオでも、出力はバイナリであると仮定される。
GPUのコードはCUDA Cで記述されており、1つのNVIDIA GPUをコンピュータで使用することができる。
実装の性能を説明するために、Brianley et al [arXiv:1609.05011] を参照し、単一のCPUコアを使用して標準デスクトップ上の42ドル行列で定義されたベル式上の局所境界を計算するのに約3週間を要した。
対照的に、ブルートフォースアルゴリズムの効率的な実装により、デスクトップ上の1枚のNVIDIA RTX 6000 Adaグラフィックカードを使用して、これを3分に短縮できる。
CPUの場合、このアルゴリズムは共有メモリモデルと分散メモリモデルに従ってOpenMPとMPIで実装され、100前後のCPUコアで同等のスピードアップを達成する。
関連論文リスト
- ParaGraph: Weighted Graph Representation for Performance Optimization of
HPC Kernels [1.304892050913381]
抽象構文木を拡張した並列アプリケーションのためのグラフベースの新しいプログラム表現を提案する。
提案した表現は,OpenMPコード領域のランタイムを予測するために,グラフニューラルネットワーク(GNN)をトレーニングすることで評価する。
その結果,本手法は実効性があり,実行時予測では 0.004 から 0.01 に RMSE を正規化していることがわかった。
論文 参考訳(メタデータ) (2023-04-07T05:52:59Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳(メタデータ) (2022-07-09T09:14:12Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳(メタデータ) (2022-06-17T09:24:41Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳(メタデータ) (2022-03-07T21:40:14Z) - PLSSVM: A (multi-)GPGPU-accelerated Least Squares Support Vector Machine [68.8204255655161]
Support Vector Machines (SVM) は機械学習で広く使われている。
しかし、現代的で最適化された実装でさえ、最先端ハードウェア上の大きな非自明な高密度データセットにはうまくスケールしない。
PLSSVMはLVMのドロップイン代替として使用できる。
論文 参考訳(メタデータ) (2022-02-25T13:24:23Z) - Giga-scale Kernel Matrix Vector Multiplication on GPU [19.663081364196778]
Kernel matrix-vector multiplication (KMVM) は、機械学習と科学計算の基礎となる演算である。
KMVMはメモリと時間の両方で二次的にスケールする傾向があるため、アプリケーションはしばしばこれらの計算制約によって制限される。
本稿では,これらのスケーリング問題に対処するため,textitFaster-Fast and Free Memory Method(f30,000m$)という新しい近似手法を提案する。
論文 参考訳(メタデータ) (2022-02-02T15:28:15Z) - Simulation of quantum physics with Tensor Processing Units: brute-force
computation of ground states and time evolution [0.3232625980782302]
Processing Units (TPU) は、Googleが大規模機械学習タスクをサポートするために開発した。
本稿では、量子スピン系をシミュレーションする難しい問題に対して、TPUを再利用する。
2048コアを持つ TPU v3 pod では、最大$N=38$ qubits の波動関数 $|Psirangle$ をシミュレートする。
論文 参考訳(メタデータ) (2021-11-19T22:41:04Z) - VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。
textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
論文 参考訳(メタデータ) (2021-05-04T04:10:48Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Systolic Computing on GPUs for Productive Performance [2.8064596842326575]
我々は,GPU上で動作する高性能なシストリックアレイを生産的に構築する言語とコンパイラを提案する。
プログラマは、データフローのプロジェクションを線形シストリック配列に指定し、プロジェクションの詳細な実装はコンパイラに任せる。
コンパイラは指定されたプロジェクションを実装し、リニアシストリックアレイをGPUのSIMD実行ユニットとベクトルレジスタにマッピングする。
論文 参考訳(メタデータ) (2020-10-29T18:49:54Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳(メタデータ) (2020-04-16T16:20:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。