Scoring Anomalous Vertices Through Quantum Walks
Authors:
- 16 February 2025
- journal article
- Published by Wiley in Annalen der Physik
- Vol. 537 (5)
Abstract
With the constant flow of data from vast sources over the past decades, a plethora of advanced analytical techniques have been developed to extract relevant information from different data types ranging from labeled data, quasi‐labeled data, and data with no labels known a priori. For data with at best quasi‐labels, graphs are a natural representation and have important applications in many industries and scientific disciplines. Specifically, for unlabeled data, anomaly detection on graphs is a method to determine which data points do not posses the latent characteristics that are present in most other data. There have been a variety of classical methods to compute an anomalous score for the individual vertices of a respective graph, such as checking the local topology of a node, random walks, and complex neural networks. Leveraging the structure of the graph, the first quantum algorithm is proposed to calculate the anomaly score of each node by continuously traversing the graph with a uniform starting position for all nodes. The proposed algorithm incorporates well‐known characteristics of quantum walks, and, taking into consideration the noisy intermediate‐scale quantum (NISQ) era and subsequent intermediate‐scale quantum (ISQ) era, an adjustment to the algorithm is provided to mitigate the increasing depth of the circuit. This algorithm is rigorously shown to converge to the expected probability with respect to the initial condition.Keywords
All Related Versions
This publication has 70 references indexed in Scilit:
- Quantum walks defined by digraphs and generalized Hermitian adjacency matricesQuantum Information Processing, 2021
- An ancilla-based quantum simulation framework for non-unitary matricesQuantum Information Processing, 2016
- Laplacian versus adjacency matrix in quantum walk searchQuantum Information Processing, 2016
- Hermitian Adjacency Matrix of Digraphs and Mixed GraphsJournal of Graph Theory, 2016
- Quantum Walks and Search Algorithms2013
- On the Hitting Times of Quantum Versus Random WalksAlgorithmica, 2011
- Random Walks and Diffusions on Graphs and Databases2011
- Graphs and Matrices2010
- On the Relationship Between Continuous- and Discrete-Time Quantum WalkCommunications in Mathematical Physics, 2009
- Identification of Outliers1980