Showing quant-phShow all
2 papers · 1 filter
quant-ph2025
Dequantization and Hardness of Spectral Sum Estimation
Roman Edenhofer, Atsuya Hasegawa, François Le Gall
We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarith…
quant-ph2024
Directed st-connectivity with few paths is in quantum logspace
Simon Apers, Roman Edenhofer
We present a -procedure to count -paths on directed graphs for which we are promised that there are at most polynomially many paths starting in …