3 papers
quant-ph2026
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…
quant-ph2025
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.…
quant-ph2024
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…