3 papers
quant-ph2025
Randomized and quantum approximate matrix multiplication
Simon Apers, Arjan Cornelissen, Samson Wang
The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers…
quant-ph2025
Quantum algorithms: A survey of applications and end-to-end complexities
Alexander M. Dalzell, Sam McArdle, Mario Berta +10
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learn…
quant-ph2025
Quantum computational complexity of matrix functions
Santiago Cifuentes, Samson Wang, Thais L. Silva +2
We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexi…