Speaker
Description
It is possible to formulate quantum states from the perspective of quantum information. Decomposing the wavefunction into a tensor network is dependent on the amount of entanglement in the wavefunction, implying for more strongly correlated quantum states that the problem becomes more and more expensive. All of the tensor operations can be formulated in terms of matrix operations, which must be efficient in order to solve problems. Traditional matrix multiplication runs in O(n^3), while the theoretical Strassen algorithm computes matrix multiplication in O(n^2.81) time. Unfortunately, constant factors become so large in the Strassen algorithm that it is impractical. There do exist practical variants however. We will present our findings on these variants, their advantages, and disadvantages.
A novel algorithm for matrix multiplication based on the Strassen equations, called the Partial-Strassen algorithm, will be presented. This new variant has the advantages that (1) memory consumption grows with input size only and not the additional parameter of depth k, and (2) for large matrices of dimension n and sufficiently large k the algorithm converges to running in O(n^3) time but more favourably than regular matrix multiplication in all cases. We will present our computational findings and the implementation steps required to obtain the largest theoretical speed up. Then we will cover the regime in which this algorithm is applicable.
A.D.~acknowledges support from the Undergraduate Student Research Award (USRA) from NSERC, the NSERC CREATE in Quantum Computing Program, grant number 543245, the Jamie Cassel's Undergraduate Research Award (JCURA). This research was undertaken, in part, thanks to funding from the Canada Research Chairs Program. This work has been supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) under grants RGPIN-2023-05510 and DGECR-2023-00026, and ALL-RP 590857-23.
| Keyword-1 | Entanglement renormalization |
|---|---|
| Keyword-2 | Classical method |
| Keyword-3 | Matrix multiplication |
