Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.13239 · IEEE Transactions on Cybernetics

A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs

Lu Bai, Luca Rossi, Lixin Cui, Jian Cheng, Edwin R. Hancock

Published Jul 11, 2019• 30 citations
arXivHTMLPDF

Abstract

We develop a novel method for measuring the similarity between complete weighted graphs, which are probed by means of the discrete-time quantum walks. Directly probing complete graphs using discrete-time quantum walks is intractable due to the cost of simulating the quantum walk. We overcome this problem by extracting a commute time minimum spanning tree from the complete weighted graph. The spanning tree is probed by a discrete-time quantum walk which is initialized using a weighted version of the Perron-Frobenius operator. This naturally encapsulates the edge weight information for the spanning tree extracted from the original graph. For each pair of complete weighted graphs to be compared, we simulate a discrete-time quantum walk on each of the corresponding commute time minimum spanning trees and, then, compute the associated density matrices for the quantum walks. The probability of the walk visiting each edge of the spanning tree is given by the diagonal elements of the density matrices. The similarity between each pair of graphs is then computed using either: 1) the inner product or 2) the negative exponential of the Jensen-Shannon divergence between the probability distributions. We show that in both cases the resulting similarity measure is positive definite and, therefore, corresponds to a kernel on the graphs. We perform a series of experiments on publicly available graph datasets from a variety of different domains, together with time-varying financial networks extracted from data for the New York Stock Exchange. Our experiments demonstrate the effectiveness of the proposed similarity measures.

DOI
10.1109/tcyb.2019.2913038

Related papers

Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence

Luca Rossi, Andrea Torsello A, Edwin R. Hancock

In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.

Physical Review E•Feb 23, 2015•48 citations

Can a Quantum Walk Tell Which Is Which?A Study of Quantum Walk-Based Graph Similarity

Giorgia Minello, Luca Rossi, Andrea Torsello A

We consider the problem of measuring the similarity between two graphs using continuous-time quantum walks and comparing their time-evolution by means of the quantum Jensen-Shannon divergence. Contrary to previous works that focused solely on undirected graphs, here we consider the case of both directed and undirected graphs. We also consider the use of alternative Hamiltonians as well as the possibility of integrating additional node-level topological information into the proposed framework. We set up a graph classification task and we provide empirical evidence that: (1) our similarity measure can effectively incorporate the edge directionality information, leading to a significant improvement in classification accuracy; (2) the choice of the quantum walk Hamiltonian does not have a significant effect on the classification accuracy; (3) the addition of node-level topological information improves the classification accuracy in some but not all cases. We also theoretically prove that under certain constraints, the proposed similarity measure is positive definite and thus a valid kernel measure. Finally, we describe a fully quantum procedure to compute the kernel.

Entropy•Mar 26, 2019•14 citations

A link prediction algorithm based on discrete-time quantum walk model on weighted graphs

Wei-Min Shi, Li-Na Wu, Jia-Wei Liang +2 more

Compared with the classical random walk, the quantum walk has the advantages of less time to find the target node and less time scattered from the source node to all nodes. Therefore, in order to further improve the accuracy of link prediction algorithms, a link prediction algorithm based on discrete-time quantum walk (DTQW) on weighted graphs is proposed by integrating node attributes and introducing the idea of assigning weights to edges in network dynamics. In this algorithm, a weighted graph is first constructed based on the attribute information of nodes in the graph, and then a DTQW model is constructed based on the weighted graph. Then, under the control of the evolution operator, the walker performs a DTQW on the weighted graph; Finally, the link prediction algorithm is implemented by defining the similarity between nodes based on the average probability of the walker reaching each node. The experimental results show that in three real social networks, Douban, Weibo and Zhihu, this algorithm has different degrees of improvement in prediction accuracy and the algorithm stability is among the top in comparison with the optimal benchmark prediction algorithm.

International Journal of Modern Physics C•Apr 11, 2025•0 citations

QuantumSim: Practical Simulation and Analysis of Discrete-Time Quantum Walks on Line and Cycle Graphs

Karuna Kadian, Sunita Garhwal, Ajay Kumar

The article describes how Discrete Time Quantum Walks (DTQWs) provide a useful means for recreating-quantum physical behaviour on graph structures, focusing on the effects of ballistic propagating effects and destructive interference, Methods were developed to simulate DTQWs using classical methods to visualise the changes in the probability distribution of the walker over time, specifically focusing on the Distal Path of the walker. A hybrid quantum machine learning model has been developed which combines the quantum features of quantum walk dynamics with classic technical indicators such as Relative Strength Index (RSI) and Moving Average Convergence Divergence (MACD), to enable the classification of financial trends. The classification model was trained on a synthetically balanced dataset created using Synthetic Minority Over-sampling Technique SMOTE and performance was assessed using standard metrics such as accuracy, precision and recall. The simulation results were evaluated and visualised in terms of their probability distributions. A successful model has been found which produces similar forecasting results compared with those achieved by normal benchmark methods for stock movement and portfolio construction.

International Conference on Artificial Intelligence and Speech Technology (AIST)•Nov 27, 2025•0 citations

Continuous-time quantum walk based centrality testing on weighted graphs

Yang Wang, Shichuan Xue, Junjie Wu +1 more

Centrality measure is an essential tool in network analysis and widely used in the domain of computer science, biology and sociology. Taking advantage of the speedup offered by quantum computation, various quantum centrality measures have been proposed. However, few work of quantum centrality involves weighted graphs, while the weight of edges should be considered in certain real-world networks. In this work, we extend the centrality measure based on continuous-time quantum walk to weighted graphs. We testify the feasibility and reliability of this quantum centrality using an ensemble of 41,675 graphs with various topologies and comparing with the eigenvector centrality measure. The average Vigna's correlation index of all the tested graphs with all edge weights in [1, 10] is as high as 0.967, indicating the pretty good consistency of rankings by the continuous-time quantum walk centrality and the eigenvector centrality. The intuitive consistency of the top-ranked vertices given by this quantum centrality measure and classical centrality measures is also demonstrated on large-scale weighted graphs. Moreover, the range of the continuous-time quantum walk centrality values is much bigger than that of classical centralities, which exhibits better distinguishing ability to pick the important vertices from the ones with less importance. All these results show that the centrality measure based on continuous-time quantum walk still works well on weighted graphs.

Scientific Reports•Apr 9, 2022•15 citations

Universal Mixing of Quantum Walk on Graphs

William Carlson, Allison For, Elizabeth Marie Harris +3 more

We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph $G$ is {\em universal mixing} if the instantaneous or average probability distribution of the quantum walk on $G$ ranges over all probability distributions on the vertices as the weights are varied over non-negative reals. The graph is {\em uniform} mixing if it visits the uniform distribution. Our results include the following: 1) All weighted complete multipartite graphs are instantaneous universal mixing. This is in contrast to the fact that no {\em unweighted} complete multipartite graphs are uniform mixing (except for the four-cycle $K_{2,2}$). 2) For all $n \ge 1$, the weighted claw $K_{1,n}$ is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted $K_{1,n}$ is instantaneous uniform mixing. This adds a new family of uniform mixing graphs to a list that so far contains only the hypercubes. 3) Any weighted graph is average almost-uniform mixing unless its spectral type is sublinear in the size of the graph. This provides a nearly tight characterization for average uniform mixing on circulant graphs. 4) No weighted graphs are average universal mixing. This shows that weights do not help to achieve average universal mixing, unlike the instantaneous case. Our proofs exploit the spectra of the underlying weighted graphs and path collapsing arguments.

arXiv:quant-ph/0608044•Quantum Information and Computation•Nov 1, 2007•21 citations
We develop a novel method for measuring the similarity between complete weighted graphs, which are probed by means of the discrete-time quantum walks. Directly probing complete graphs using discrete-time quantum walks is intractable due to the cost of simulating the quantum walk. We overcome this problem by extracting a commute time minimum spanning tree from the complete weighted graph. The spanning tree is probed by a discrete-time quantum walk which is initialized using a weighted version of the Perron-Frobenius operator. This naturally encapsulates the edge weight information for the spanning tree extracted from the original graph. For each pair of complete weighted graphs to be compared, we simulate a discrete-time quantum walk on each of the corresponding commute time minimum spanning trees and, then, compute the associated density matrices for the quantum walks. The probability of the walk visiting each edge of the spanning tree is given by the diagonal elements of the density matrices. The similarity between each pair of graphs is then computed using either: 1) the inner product or 2) the negative exponential of the Jensen-Shannon divergence between the probability distributions. We show that in both cases the resulting similarity measure is positive definite and, therefore, corresponds to a kernel on the graphs. We perform a series of experiments on publicly available graph datasets from a variety of different domains, together with time-varying financial networks extracted from data for the New York Stock Exchange. Our experiments demonstrate the effectiveness of the proposed similarity measures.
In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.
We consider the problem of measuring the similarity between two graphs using continuous-time quantum walks and comparing their time-evolution by means of the quantum Jensen-Shannon divergence. Contrary to previous works that focused solely on undirected graphs, here we consider the case of both directed and undirected graphs. We also consider the use of alternative Hamiltonians as well as the possibility of integrating additional node-level topological information into the proposed framework. We set up a graph classification task and we provide empirical evidence that: (1) our similarity measure can effectively incorporate the edge directionality information, leading to a significant improvement in classification accuracy; (2) the choice of the quantum walk Hamiltonian does not have a significant effect on the classification accuracy; (3) the addition of node-level topological information improves the classification accuracy in some but not all cases. We also theoretically prove that under certain constraints, the proposed similarity measure is positive definite and thus a valid kernel measure. Finally, we describe a fully quantum procedure to compute the kernel.
Compared with the classical random walk, the quantum walk has the advantages of less time to find the target node and less time scattered from the source node to all nodes. Therefore, in order to further improve the accuracy of link prediction algorithms, a link prediction algorithm based on discrete-time quantum walk (DTQW) on weighted graphs is proposed by integrating node attributes and introducing the idea of assigning weights to edges in network dynamics. In this algorithm, a weighted graph is first constructed based on the attribute information of nodes in the graph, and then a DTQW model is constructed based on the weighted graph. Then, under the control of the evolution operator, the walker performs a DTQW on the weighted graph; Finally, the link prediction algorithm is implemented by defining the similarity between nodes based on the average probability of the walker reaching each node. The experimental results show that in three real social networks, Douban, Weibo and Zhihu, this algorithm has different degrees of improvement in prediction accuracy and the algorithm stability is among the top in comparison with the optimal benchmark prediction algorithm.
The article describes how Discrete Time Quantum Walks (DTQWs) provide a useful means for recreating-quantum physical behaviour on graph structures, focusing on the effects of ballistic propagating effects and destructive interference, Methods were developed to simulate DTQWs using classical methods to visualise the changes in the probability distribution of the walker over time, specifically focusing on the Distal Path of the walker. A hybrid quantum machine learning model has been developed which combines the quantum features of quantum walk dynamics with classic technical indicators such as Relative Strength Index (RSI) and Moving Average Convergence Divergence (MACD), to enable the classification of financial trends. The classification model was trained on a synthetically balanced dataset created using Synthetic Minority Over-sampling Technique SMOTE and performance was assessed using standard metrics such as accuracy, precision and recall. The simulation results were evaluated and visualised in terms of their probability distributions. A successful model has been found which produces similar forecasting results compared with those achieved by normal benchmark methods for stock movement and portfolio construction.
Centrality measure is an essential tool in network analysis and widely used in the domain of computer science, biology and sociology. Taking advantage of the speedup offered by quantum computation, various quantum centrality measures have been proposed. However, few work of quantum centrality involves weighted graphs, while the weight of edges should be considered in certain real-world networks. In this work, we extend the centrality measure based on continuous-time quantum walk to weighted graphs. We testify the feasibility and reliability of this quantum centrality using an ensemble of 41,675 graphs with various topologies and comparing with the eigenvector centrality measure. The average Vigna's correlation index of all the tested graphs with all edge weights in [1, 10] is as high as 0.967, indicating the pretty good consistency of rankings by the continuous-time quantum walk centrality and the eigenvector centrality. The intuitive consistency of the top-ranked vertices given by this quantum centrality measure and classical centrality measures is also demonstrated on large-scale weighted graphs. Moreover, the range of the continuous-time quantum walk centrality values is much bigger than that of classical centralities, which exhibits better distinguishing ability to pick the important vertices from the ones with less importance. All these results show that the centrality measure based on continuous-time quantum walk still works well on weighted graphs.
We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph GGG is {\em universal mixing} if the instantaneous or average probability distribution of the quantum walk on GGG ranges over all probability distributions on the vertices as the weights are varied over non-negative reals. The graph is {\em uniform} mixing if it visits the uniform distribution. Our results include the following: 1) All weighted complete multipartite graphs are instantaneous universal mixing. This is in contrast to the fact that no {\em unweighted} complete multipartite graphs are uniform mixing (except for the four-cycle K2,2K_{2,2}K2,2​). 2) For all n≥1n \ge 1n≥1, the weighted claw K1,nK_{1,n}K1,n​ is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted K1,nK_{1,n}K1,n​ is instantaneous uniform mixing. This adds a new family of uniform mixing graphs to a list that so far contains only the hypercubes. 3) Any weighted graph is average almost-uniform mixing unless its spectral type is sublinear in the size of the graph. This provides a nearly tight characterization for average uniform mixing on circulant graphs. 4) No weighted graphs are average universal mixing. This shows that weights do not help to achieve average universal mixing, unlike the instantaneous case. Our proofs exploit the spectra of the underlying weighted graphs and path collapsing arguments.