Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine

• URL: http://arxiv.org/abs/2401.01554v1
• Date: Wed, 3 Jan 2024 06:00:23 GMT
• Title: Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine
• Authors: Sergio A. Ortega, Miguel A. Martin-Delgado
• Abstract summary: The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the $N/M$ ratio between the network size $N$ and the number of marked nodes $M$ is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called Randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network, and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with $N/M$ for the quantum SearchRank, but remarkably it remains at a high value around $0.9$ for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutsch's algorithm is the first quantum algorithm to show the advantage over the classical algorithm. We propose a new quantum algorithm with indefinite causal order to solve this problem.
  arXiv  Detail & Related papers  (2023-05-09T13:04:28Z)
• 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)
• Generalized Quantum Google PageRank Algorithm with Arbitrary Phase Rotations [0.0]
  We present a modification of the quantum PageRank introducing arbitrary phase rotations (APR) in the underlying Szegedy's quantum walk. We have analyzed the behavior of the new algorithms in a small generic graph, observing that a decrease of the phase reduces the standard deviation of the instantaneous PageRank. We have found that one of our new algorithms whose PageRank distribution resembles the classical one, has a stability similar to the original quantum algorithm.
  arXiv  Detail & Related papers  (2022-09-27T15:15:54Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
  Existing quantum walk-based search algorithms suffer from the souffl'e problem. We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
  arXiv  Detail & Related papers  (2021-11-17T10:04:44Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• TensorFlow Solver for Quantum PageRank in Large-Scale Networks [12.937513443750804]
  We present an efficient solver for quantum PageRank using the Runge-Kutta method to reduce the matrix dimension to O(N2) and employing parallel computing. Compared with the previous quantum PageRank solver, our solver dramatically reduces the required memory and time to only 1% and 0.2%, respectively, making it practical to work in a normal computer with a memory of 4-8 GB in no more than 100 seconds.
  arXiv  Detail & Related papers  (2020-03-10T18:58:15Z)

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.