A framework for optimal quantum spatial search using alternating phase-walks

• URL: http://arxiv.org/abs/2109.14351v1
• Date: Wed, 29 Sep 2021 11:16:52 GMT
• Title: A framework for optimal quantum spatial search using alternating phase-walks
• Authors: S. Marsh, J. B. Wang
• Abstract summary: We generalise the Childs & Goldstone ($mathcalCG$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We demonstrate the effectiveness of the algorithm by applying it to obtain $mathcalO(sqrtN)$ search on a variety of graphs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel methodological framework for quantum spatial search, generalising the Childs & Goldstone ($\mathcal{CG}$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We determine closed form expressions for the optimal walk time and phase shift parameters for periodic graphs. These parameters are chosen to rotate the system about subsets of the graph Laplacian eigenstates, amplifying the probability of measuring the marked vertex. The state evolution is asymptotically optimal for any class of periodic graphs having a fixed number of unique eigenvalues. We demonstrate the effectiveness of the algorithm by applying it to obtain $\mathcal{O}(\sqrt{N})$ search on a variety of graphs. One important class is the $n \times n^3$ rook graph, which has $N=n^4$ vertices. On this class of graphs the $\mathcal{CG}$ algorithm performs suboptimally, achieving only $\mathcal{O}(N^{-1/8})$ overlap after time $\mathcal{O}(N^{5/8})$. Using the new alternating phase-walk framework, we show that $\mathcal{O}(1)$ overlap is obtained in $\mathcal{O}(\sqrt{N})$ phase-walk iterations.

Related papers

• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing. How to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs.
  arXiv  Detail & Related papers  (2024-08-20T05:20:55Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  Current methods either invert a graph kernel runtime matrix with $mathcalO(n3)$ or $mathcalO(n2)$ space complexity or sample a large volume of random spanning trees. We propose an improvement based on the textitonline relaxation technique introduced by a series of works.
  arXiv  Detail & Related papers  (2023-05-25T17:13:08Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  We present a novel map-based algorithm ($mathsfnorMtext-mathsfSGD$) for $symbol$k$ convergence problems.
  arXiv  Detail & Related papers  (2023-05-10T01:12:11Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
  We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
  arXiv  Detail & Related papers  (2022-03-27T20:22:17Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

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.