Lovasz's book Large networks and Graph Limits mentions that their study of graph limits is motivatived applications to quantum computers, statistical physics, and models for the internet. They don't mention any specific applications in quantum computing, though.

Can someone help me identify some applications of the study of large graphs (sparse or dense) and their limits in quantum computation? I am looking to see if the quantum computing has applications to offer on this front, especially in the study of quantum graph neural networks.


1 Answer 1


Because the adjacency matrix of undirected graphs are symmetric about the diagonal, these graphs are hermitian, and you are correct to suppose that quantum computing can be a natural vehicle for studying properties of these graphs.

One relatively famous quantum algorithm in graph theory, from Childs et al., is related to glued trees - a quantum computer can traverse a certain graph exponentially faster than a classical computer could.

Another interesting algorithm from Wang is to determine the resistance between two nodes of a large graph with a quantum algorithm.

I recommend reviewing the Quantum Algorithm Zoo and searching for "graph" - there are many (many) hits for review. One of my favorite papers, that I found out about by exploring the Zoo, is by Janzing and Wocjan called "BQP-complete problems concerning mixing properties of classical random walks on sparse graphs".

Take note that most such algorithms focus on very large but also very sparse, implicitly defined graphs. Such graphs may be counter to the graphons or graph limits mentioned in the question, as those appear to characterize properties of dense graphs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.