A Bi-directional Quantum Search Algorithm

• URL: http://arxiv.org/abs/2404.15616v1
• Date: Wed, 24 Apr 2024 03:11:10 GMT
• Title: A Bi-directional Quantum Search Algorithm
• Authors: Debanjan Konar, Zain Hafeez, Vaneet Aggarwal,
• Abstract summary: This paper combines Partial Grover's search algorithm and Bi-directional Search to create a fast Grover's quantum search algorithm. We incorporated a bi-directional search tactic with a partial Grover search, starting from an initial state and a single marked state in parallel. The proposed BDGS algorithm is benchmarked against the state-of-the-art Depth-First Grover's Search (DFGS) and generic Grover's Search (GS) implementations for $2$ to $20$ qubits.
• Score: 30.62704006898929
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grover's search algorithms, including various partial Grover searches, experience scaling problems as the number of iterations rises with increased qubits, making implementation more computationally expensive. This paper combines Partial Grover's search algorithm and Bi-directional Search to create a fast Grover's quantum search algorithm, referred to as Bi-Directional Grover Search (BDGS). We incorporated a bi-directional search tactic with a partial Grover search, starting from an initial state and a single marked state in parallel. We have shown in this article that our novel approach requires $\frac{\pi}{4\sqrt{2}}\sqrt{N}(1-\sqrt{\frac{1}{b^{r/2k}}})$ iterations over regular Grover Search and Partial Grover Search (PGS), which takes $\frac{\pi}{4}\sqrt{N}\sqrt{1-\frac{1}{b}}$ (here, $N=2^r$ elements, $b$ is the branching factor of partial search, and $k= \lceil\log_2b \rceil$). The proposed BDGS algorithm is benchmarked against the state-of-the-art Depth-First Grover's Search (DFGS) and generic Grover's Search (GS) implementations for $2$ to $20$ qubits and provides promising results. The Qiskit Python implementation of the proposed BDGS algorithm is available on Github (https://github.com/hafeezzwiz21/DFGS-BDGS).

Related papers

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Implementing the Grover Algorithm in Homomorphic Encryption Schemes [0.25782420501870296]
  We apply quantum homomorphic encryption schemes suitable for circuits with a decryption number of $T/Tdagger$-gates to Grover's algorithm. The $T/Tdagger$ gate complexity of Grover's algorithm is also analysed in order to show that any Grover circuit can be evaluated homomorphically in an efficient manner.
  arXiv  Detail & Related papers  (2024-03-07T22:13:14Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
  Grover's algorithm is capable of finding $k$ elements in an unordered database with $N$ elements using $O(sqrtN/k)$ steps. This work tackles the problem of using the quantum counting algorithm for estimating the value $k$ of marked elements in other graphs.
  arXiv  Detail & Related papers  (2023-12-05T21:15:09Z)
• 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)
• Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
  We study decentralized learning in two-player zero-sum discounted Markov games. The goal is to design a policy optimization algorithm for either agent satisfying two properties.
  arXiv  Detail & Related papers  (2023-03-03T02:40:26Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
  Combination of Depth-First Search and Grover's algorithm to generate Depth-First Grover Search(DFGS) DFGS handles multi-solution searching problems on unstructured databases with an unknown number of solutions. New algorithm attains an average complexity of $mathcalO(msqrtN)$ which performs as efficient as a normal Grover Search.
  arXiv  Detail & Related papers  (2022-10-10T13:10:28Z)
• Grover's search algorithm for $n$ qubits with optimal number of iterations [0.0]
  Grover's search algorithm depends on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. General scheme for the construction of $n$-qubit Grover's search algorithm with $1 leq M leq N$ target states is presented.
  arXiv  Detail & Related papers  (2020-11-08T18:46:50Z)

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.