Classical bounds on two-outcome bipartite Bell expressions and linear prepare-and-measure witnesses: Efficient computation in parallel environments such as graphics processing units

The presented program aims at speeding up the brute force computation of the so-called 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 x m matrix M has real elements which may represent coefficients of a bipartite 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 correlation-type Bell expression, and the L_d norm for d ≥ 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. The program is also capable of calculating the local bound of Bell expressions including marginals. In all 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. [1] who needed approximately three weeks to compute the local bound on a Bell expression defined by a 42 x 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 workstation. 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.本程序旨在借助图形处理器（Graphics Processing Units, GPUs）加速矩阵M的L_d范数的蛮力计算。此外还实现了适用于中央处理器（Central Processing Units, CPUs）的替代方案，且该算法可适配任意并行环境。n×m维矩阵M的元素为实数，可用于表示二分贝尔表达式的系数，或线性制备-测量（prepare-and-measure, PM）见证的系数。在该解释框架下，L_1范数即为给定关联型贝尔表达式的局域上限，而当d≥2时，L_d范数则对应给定PM见证的经典d维上限，该上限与PM场景下的d级经典消息通信相关联。本程序还可计算包含边缘分布的贝尔表达式的局域上限，所有场景下均假设输出为二元形式。 GPU版本的代码采用CUDA C编写，可利用单台计算机中的一块NVIDIA GPU。为展示本实现的性能，我们参考Brierley等人[1]的工作：他们在标准桌面设备上使用单个CPU核心计算某42×42矩阵定义的贝尔表达式的局域上限时，耗时约三周。相较之下，我们的高效蛮力算法实现可将该耗时缩减至仅三分钟，所用设备为工作站上的单块NVIDIA RTX 6000 Ada图形显卡。对于CPU版本，算法分别基于共享内存与分布式内存模型，通过OpenMP与MPI实现，在约100个CPU核心的配置下可实现相当的加速比。