Alwin Walter Zulehner, Robert Wille,
"Matrix-Vector vs. Matrix-Matrix Multiplication: Potential in DD-based Simulation of Quantum Computations"
: Design, Automation and Test in Europe (DATE), 2019
Original Titel:
Matrix-Vector vs. Matrix-Matrix Multiplication: Potential in DD-based Simulation of Quantum Computations
Sprache des Titels:
Englisch
Original Buchtitel:
Design, Automation and Test in Europe (DATE)
Original Kurzfassung:
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.
Forschungs-