Distributed exact multi-objective quantum search algorithm

• URL: http://arxiv.org/abs/2409.04039v2
• Date: Mon, 9 Sep 2024 14:33:21 GMT
• Title: Distributed exact multi-objective quantum search algorithm
• Authors: Hao Li, Daowen Qiu, Le Luo,
• Abstract summary: Grover's algorithm has quadratic acceleration in multi-objection search. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification.
• Score: 9.09986332387569
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-objective search means searching for any one of several objectives in an unstructured database. Grover's algorithm has quadratic acceleration in multi-objection search than classical ones. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification. In this paper, we design two distributed iterated operators and therefore two new distributed Grover's algorithms are obtained with the following advantages: (1) Compared to Grover's algorithm and the modified Grover's algorithm by Long, our distributed algorithms require fewer qubits; (2) Compared to the distributed Grover's algorithm proposed by Qiu et al., one of our distributed algorithms is exact. Of course, both our distributed algorithms require quite quantum communication and involve a number of more complicated unitary operators as cost, but there still may have certain advantage of physical realizability in the Noisy Intermediate-Scale Quantum (NISQ) era.

Related papers

• Near-deterministic quantum search algorithm without phase control [10.754825115553086]
  Grover's algorithm can find the target item with certainty only if searching one out of four. We propose a near-deterministic quantum search algorithm without the phase control.
  arXiv  Detail & Related papers  (2024-07-15T14:20:47Z)
• Distributed exact quantum algorithms for Bernstein-Vazirani and search problems [9.146620606615889]
  We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
  arXiv  Detail & Related papers  (2023-03-19T14:18:49Z)
• Quantum multi-programming for Grover's search [6.359294579761927]
  We propose a quantum multi-programming (QMP) algorithm for Grover's search. Our algorithm decomposes Grover's algorithm by the partial diffusion operator and executes the decomposed circuits in parallel by QMP. We prove that this new algorithm increases the rotation angle of the Grover operator which, as a result, increases the success probability.
  arXiv  Detail & Related papers  (2022-07-29T04:05:46Z)
• Grover's Algorithm with Diffusion and Amplitude Steering [0.0]
  We present a generalization of Grover's algorithm that searches an arbitrary subspace of the multi-dimensional Hilbert space. We also outline a generalized Grover's algorithm that takes into account higher level correlations that could exist between database elements.
  arXiv  Detail & Related papers  (2021-10-21T14:15:32Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era [0.0]
  We undertake a series of simulations by inflicting various types of noise, modelled by the IBM QISKit. We find the upper bound of noise for these cases, establish its dependence on the quantum depth of the circuit. We predict what would be the typical gate error bounds when apply the Grover's algorithms for the search of a data in a data set as large as thirty two thousands.
  arXiv  Detail & Related papers  (2020-06-17T17:57:48Z)
• 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.