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

Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition

Graph drawing using quantum commute time

David Emms, Edwin R. Hancock, Richard C. Wilson

Published Dec 1, 2008• 1 citation
Publisher

Abstract

In this paper, we explore experimentally the use of the commute time of the continuous-time quantum walk for graph drawing. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. We analyse the quantum commute times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve commute-time.

DOI
10.1109/icpr.2008.4761274

Related papers

Graph embedding using quantum hitting time

David Emms, R. Wilson, Edwin R. Hancock

In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.

Quantum Information and Computation•Mar 1, 2009•3 citations

Graph embedding using a quasi-quantum analogue of the hitting times of continuous time quantum walks

David Emms, Richard C. Wilson, Edwin R. Hancock

In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuoustime quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.

Quantum Information and Computation•Mar 1, 2009•9 citations

Quantum walk on a chimera graph

Shu Xu, Xiangxiang Sun, Jizhou Wu +3 more

We analyse a continuous-time quantum walk on a chimera graph, which is a graph of choice for designing quantum annealers, and we discover beautiful quantum walk features such as localization that starkly distinguishes classical from quantum behaviour. Motivated by technological thrusts, we study continuous-time quantum walk on enhanced variants of the chimera graph and on diminished chimera graph with a random removal of vertices. We explain the quantum walk by constructing a generating set for a suitable subgroup of graph isomorphisms and corresponding symmetry operators that commute with the quantum walk Hamiltonian; the Hamiltonian and these symmetry operators provide a complete set of labels for the spectrum and the stationary states. Our quantum walk characterization of the chimera graph and its variants yields valuable insights into graphs used for designing quantum-annealers.

arXiv:1705.11036•New Journal of Physics•Mar 15, 2018•5 citations

Algorithms for finding the maximum clique based on continuous time quantum walks

Xi Li, Mingyou Wu, Hanwu Chen +1 more

In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N^6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this work.

Quantum Information and Computation•Feb 1, 2021•2 citations

An enhanced classical approach to graph isomorphism using continuous-time quantum walk

Xiaogang Qiang, Xuejun Yang, Junjie Wu +1 more

Studies on graph isomorphism play an important role in graph research, and graph isomorphism algorithms have a wide range of applications in image matching, pattern recognition, computer vision, biochemistry and other fields. Previous research demonstrated that involving discrete-time quantum walk in the graph isomorphism algorithm could achieve complexity O ( N 7 ) for general graphs, since quantum walk could be utilized as a new toolbox for solving graph problems. We develop an enhanced classical approach to graph isomorphism using continuous-time quantum walk, which has lower complexity O ( N 5 ) and can effectively distinguish the graphs that are generally considered difficult. In addition, we define a graph similarity measure based on the proposed algorithm, which can be used for graph isomorphism and graph clustering. In the experiment, we test a wide variety of classes of graphs; the results show that the algorithm has a wide range of applications rather than being limited to a specific type of graph.

Journal of Physics A Mathematical and Theoretical•Jan 4, 2012•23 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
In this paper, we explore experimentally the use of the commute time of the continuous-time quantum walk for graph drawing. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. We analyse the quantum commute times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve commute-time.
In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.
In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuoustime quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.
We analyse a continuous-time quantum walk on a chimera graph, which is a graph of choice for designing quantum annealers, and we discover beautiful quantum walk features such as localization that starkly distinguishes classical from quantum behaviour. Motivated by technological thrusts, we study continuous-time quantum walk on enhanced variants of the chimera graph and on diminished chimera graph with a random removal of vertices. We explain the quantum walk by constructing a generating set for a suitable subgroup of graph isomorphisms and corresponding symmetry operators that commute with the quantum walk Hamiltonian; the Hamiltonian and these symmetry operators provide a complete set of labels for the spectrum and the stationary states. Our quantum walk characterization of the chimera graph and its variants yields valuable insights into graphs used for designing quantum-annealers.
In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N^6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this work.
Studies on graph isomorphism play an important role in graph research, and graph isomorphism algorithms have a wide range of applications in image matching, pattern recognition, computer vision, biochemistry and other fields. Previous research demonstrated that involving discrete-time quantum walk in the graph isomorphism algorithm could achieve complexity O ( N 7 ) for general graphs, since quantum walk could be utilized as a new toolbox for solving graph problems. We develop an enhanced classical approach to graph isomorphism using continuous-time quantum walk, which has lower complexity O ( N 5 ) and can effectively distinguish the graphs that are generally considered difficult. In addition, we define a graph similarity measure based on the proposed algorithm, which can be used for graph isomorphism and graph clustering. In the experiment, we test a wide variety of classes of graphs; the results show that the algorithm has a wide range of applications rather than being limited to a specific type of graph.
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.