Robustness of Quantum Random Walk Search Algorithm in Hypercube when only first or both first and second neighbors are measured

• URL: http://arxiv.org/abs/2305.15073v1
• Date: Wed, 24 May 2023 11:55:52 GMT
• Title: Robustness of Quantum Random Walk Search Algorithm in Hypercube when only first or both first and second neighbors are measured
• Authors: Hristo Tonchev, Petar Danev
• Abstract summary: We study the robustness of two modifications of quantum random walk search algorithm on hypercube. The most important one, in view of our study of the robustness, is an increase in the stability of the algorithm, especially for large coin dimensions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we study the robustness of two modifications of quantum random walk search algorithm on hypercube. In the first previously suggested modification, on each even iteration only quantum walk is applied. And in the second, the closest neighbors of the solution are measured classically. In our approach the traversing coin is constructed by both generalized Householder reflection and an additional phase multiplier and we investigate the stability of the algorithm to deviations in those phases. We have shown that the unmodified algorithm becomes more robust when a certain relation between those phases is preserved. The first modification we study here does not lead to any change in the robustness of quantum random walk search algorithm. However, when a measurement of the first and second neighbors is included, there are some differences. The most important one, in view of our study of the robustness, is an increase in the stability of the algorithm, especially for large coin dimensions.

Related papers

• Robustness of Quantum Random Walk Search with multi-phase matching [0.0]
  We show that usage of a particular sequence of phases can make the algorithm more robust even if there is no preserved connection between the phases in the traversing coin.
  arXiv  Detail & Related papers  (2024-04-07T21:52:35Z)
• Variational generation of spin squeezing on one-dimensional quantum devices with nearest-neighbor interactions [5.720828279632708]
  Current protocols for generating strong spin squeezing rely on either high dimensionality or long-range interactions. Here, we develop variational spin-squeezing algorithms to solve this problem. We consider both digital and analog quantum circuits for these variational algorithms.
  arXiv  Detail & Related papers  (2023-06-28T13:19:56Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• 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)
• Reducing number of gates in quantum random walk search algorithm via modification of coin operators [0.0]
  This paper examines a way to simplify the circuit of quantum random walk search algorithm. It is shown explicitly how to construct such walk coin in order to obtain more robust quantum algorithm.
  arXiv  Detail & Related papers  (2022-04-27T11:41:08Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• 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)
• Optimizing the walk coin in the quantum random walk search algorithm through machine learning [0.0]
  This paper examines the stability of the quantum random walk search algorithm, when the walk coin is constructed by generalized Householder reflection and additional phase shift. The optimization of the algorithm is done by numerical methods - Monte Carlo, neural networks, and supervised machine learning.
  arXiv  Detail & Related papers  (2021-05-17T17:13:49Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• 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)

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.