4 papers · 1 filter
Torsion detection in clique complexes is conditionally -hard
Adam Wesołowski
Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combina…
Average-case hardness of Betti number estimation
Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski
We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction imp…
Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
Adam Wesołowski, Jinge Bao
The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph.…
Advances in quantum algorithms for the shortest path problem
Adam Wesołowski, Stephen Piddock
Given an undirected, weighted graph, with vertices and edges, and two special vertices and , the problem is to find the shortest path between them. We give two bound…