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
- 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) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
We show that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of $> 5$ a maximum cut of at most $1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$.
We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$, where
arXiv Detail & Related papers (2021-06-10T16:28:23Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization [77.57736777744934]
This paper revisits and extends the widely used accelerated gradient tracking.
Our complexities improve significantly on the ones of $cal O(frac1epsilon5/7)$ and $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
arXiv Detail & Related papers (2021-04-06T15:34:14Z) - 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.