Random Walks: A Review of Algorithms and Applications

• URL: http://arxiv.org/abs/2008.03639v1
• Date: Sun, 9 Aug 2020 03:41:56 GMT
• Title: Random Walks: A Review of Algorithms and Applications
• Authors: Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, Xiangjie Kong
• Abstract summary: In computer science, classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding.
• Score: 37.226218097358284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this paper, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.

Related papers

• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Estimating the randomness of quantum circuit ensembles up to 50 qubits [9.775777593425452]
  We show that the ability of random circuits to approximate any random unitaries has consequences on their complexity, expressibility, and trainability. Our work shows that large-scale tensor network simulations could provide important hints toward open problems in quantum information science.
  arXiv  Detail & Related papers  (2022-05-19T23:43:15Z)
• Designing exceptional-point-based graphs yielding topologically guaranteed quantum search [0.0]
  We show how to construct walks with the property that all the eigenvalues of the non-Hermitian survival operator, coalesce to zero. The resulting search is guaranteed to succeed in a bounded time for any initial condition.
  arXiv  Detail & Related papers  (2022-02-08T04:30:24Z)
• Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
  Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
  arXiv  Detail & Related papers  (2021-12-23T17:57:49Z)
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks [2.28438857884398]
  We introduce quantum algorithms to solve tasks such as matrix product or distance estimation. These results are then used to develop new quantum algorithms for unsupervised machine learning. We will also present new quantum algorithms for neural networks, or deep learning.
  arXiv  Detail & Related papers  (2021-11-05T16:36:09Z)
• Quantum Walk to Train a Classical Artificial Neural Network [0.0]
  This work proposes a procedure that uses a quantum walk in a complete graph to train classical artificial neural networks. The methodology employed to train the neural network will adjust the synaptic weights of the output layer, not altering the weights of the hidden layer. In addition to computational gain, another advantage of the proposed procedure is to be possible to know textita priori the number of iterations required to obtain the solutions.
  arXiv  Detail & Related papers  (2021-09-01T00:36:52Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.