Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer
- URL: http://arxiv.org/abs/2210.04664v2
- Date: Wed, 12 Oct 2022 00:42:17 GMT
- Title: Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer
- Authors: Haoxiang Guo
- Abstract summary: 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.
- Score: 2.487445341407889
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We demonstrated the detailed construction of the hybrid quantum-classical
computer. Based on this architecture, the useful concept of amplitude
interception is illustrated. It is then embedded into a combination of
Depth-First Search and Grover's algorithm to generate a novel approach, the
Depth-First Grover Search(DFGS), to handle multi-solution searching problems on
unstructured databases with an unknown number of solutions. Our new algorithm
attains an average complexity of $\mathcal{O}(m\sqrt{N})$ which performs as
efficient as a normal Grover Search, and a $\mathcal{O}(\sqrt{p}N)$ complexity
with a manually determined constant $p$ for the case with all elements are
solutions, where a normal Grover Search will degenerate to
$\mathcal{O}(N\sqrt{N})$. The DFGS algorithm is more robust and stable in
comparison.
Related papers
- Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
Combination of Quantum Minimum Finding and dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems.
In this paper, we provide a bounded-error hybrid algorithm that achieves such an improvement for a broad class of NP-hard single-machine scheduling problems.
Our algorithm reduces the exponential-part complexity compared to the best-known classical algorithm, sometimes at the cost of an additional pseudo-polynomial factor.
arXiv Detail & Related papers (2024-08-11T10:28:49Z) - A Bi-directional Quantum Search Algorithm [30.62704006898929]
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.
arXiv Detail & Related papers (2024-04-24T03:11:10Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations.
We explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently.
The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.
arXiv Detail & Related papers (2024-03-19T11:32:02Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies.
We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - 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) - 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) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
General tools for designing efficient private estimation algorithms.
First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
arXiv Detail & Related papers (2023-01-11T09:12:28Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum.
Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges.
We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
arXiv Detail & Related papers (2022-03-28T21:34:16Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Quantum Search with Prior Knowledge [15.384459603233978]
We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting.
We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
arXiv Detail & Related papers (2020-09-18T09:50:33Z)
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.