Matrix-Vector vs. Matrix-Matrix Multiplication: Potential in DD-based Simulation of Quantum Computations
Matrix-Vector vs. Matrix-Matrix Multiplication: Potential in DD-based Simulation of Quantum Computations
复制标题
DOI：
10.23919/date.2019.8714836
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Alwin Zulehner;R. Wille
中科院分区：
文献类型：
--
作者：
Alwin Zulehner;R. Wille
量子计算的模拟基本上可以归结为向量（描述各自的量子态）和矩阵（描述各自的量子运算）的乘法。然而，由于这些矩阵/向量的大小呈指数级增长，因此大多数现有解决方案（依赖于数组来表示）要么仅限于相当小的量子系统，要么需要大量的硬件资源。为了克服这些缺点，最近提出了基于决策图（基于DD的模拟）的解决方案。它们利用量子态和矩阵中的冗余，从而实现紧凑的表示和操作。这提供了进一步的（意想不到的）潜力。事实上，到目前为止，模拟已经通过应用一个又一个的运算（即一个矩阵向量乘法）来进行。除此之外，在将多个运算应用于向量之前，还可以组合它们（需要矩阵-矩阵乘法）。但从理论角度来看，矩阵-向量乘法比矩阵-矩阵乘法便宜得多，因此迄今为止该方向的潜力相当有限。在这项工作中，我们展示了使用决策图时情况会发生变化。事实上，它们更紧凑的表示常常使矩阵-矩阵乘法更加有益——通过利用运算组合带来显着的改进。实验结果证实，所提出的组合操作策略会导致多个因素的加速，或者当另外利用有关所考虑实例的进一步知识时，甚至会导致几个数量级的加速。
The simulation of quantum computations basically boils down to the multiplication of vectors (describing the respective quantum state) and matrices (describing the respective quantum operations). However, since those matrices/vectors are exponential in size, most of the existing solutions (relying on arrays for their representation) are either limited to rather small quantum systems or require substantial hardware resources. To overcome these shortcomings, solutions based on decision diagrams (DD-based simulation) have been proposed recently. They exploit redundancies in quantum states as well as matrices and, by this, allow for a compact representation and manipulation. This offers further (unexpected) potential. In fact, simulation has been conducted thus far by applying one operation (i.e. one matrix-vector multiplication) after another. Besides that, there is the possibility to combine several operations (requiring a matrix-matrix multiplication) before applying them to a vector. But since, from a theoretical perspective, matrix-vector multiplication is significantly cheaper than matrix-matrix multiplication, the potential of this direction was rather limited thus far. In this work, we show that this changes when decision diagrams are employed. In fact, their more compact representation frequently makes matrix-matrix multiplication more beneficial—leading to substantial improvements by exploiting the combination of operations. Experimental results confirm the proposed strategies for combining operations lead to speed-ups of several factors or—when additionally exploiting further knowledge about the considered instance—even of several orders of magnitudes.