We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of “welded trees” introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent “succinct” implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by “lifting” the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity. A full version of this paper can be found on arXiv [21].

Quantum machine learning algorithms could provide significant speed-ups over their classical counterparts; however, whether they could also achieve good generalization remains unclear. Recently, two quantum perceptron models which give a quadratic improvement over the classical perceptron algorithm using Grover’s search have been proposed by Wiebe et al. While the first model reduces the complexity with respect to the size of the training set, the second one improves the bound on the number of mistakes made by the perceptron. In this paper, we introduce a hybrid quantum-classical perceptron algorithm with lower complexity and better generalization ability than the classical perceptron. We show a quadratic improvement over the classical perceptron in both the number of samples and the margin of the data. We derive a bound on the expected error of the hypothesis returned by our algorithm, which compares favorably to the one obtained with the classical online perceptron. We use numerical experiments to illustrate the trade-off between computational complexity and statistical accuracy in quantum perceptron learning and discuss some of the key practical issues surrounding the implementation of quantum perceptron models into near-term quantum devices, whose practical implementation represents a serious challenge due to inherent noise. However, the potential benefits make correcting this worthwhile.