An adiabatic oracle for Grover's algorithm
- URL: http://arxiv.org/abs/2207.05665v2
- Date: Wed, 1 Feb 2023 15:24:10 GMT
- Title: An adiabatic oracle for Grover's algorithm
- Authors: Bin Yan and Nikolai A. Sinitsyn
- Abstract summary: Grover's search algorithm was originally proposed for circuit-based quantum computers.
We propose a realization of Grover's oracle for a large class of searching problems.
- Score: 3.800391908440439
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's search algorithm was originally proposed for circuit-based quantum
computers. A crucial part of it is to query an oracle -- a black-box unitary
operation. Generation of this oracle is formally beyond the original algorithm
design. Here, we propose a realization of Grover's oracle for a large class of
searching problems using a quantum annealing step. The time of this step grows
only logarithmically with the size of the database. This suggests an efficient
path to application of Grover's algorithm to practically important problems,
such as finding the ground state of a Hamiltonian with a spectral gap over its
ground state.
Related papers
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal.
Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
arXiv Detail & Related papers (2024-09-07T06:37:23Z) - Opening the Black Box Inside Grover's Algorithm [0.0]
Grover's algorithm is a primary algorithm offered as evidence that quantum computers can provide an advantage over classical computers.
We construct a quantum-inspired algorithm, executable on a classical computer, that performs Grover's task in a linear number of calls to (simulations of) the oracle.
arXiv Detail & Related papers (2023-03-20T17:56:20Z) - Automatic Generation of an Efficient Less-Than Oracle for Quantum
Amplitude Amplification [0.4374837991804085]
Grover's algorithm is a well-known contribution to quantum computing.
We present a classical algorithm that builds a phase-marking oracle for Amplitude Amplification.
arXiv Detail & Related papers (2023-03-13T13:52:19Z) - Description of the Grover algorithm based on geometric considerations [2.680349265843603]
Grover algorithm allows amplification of quantum states previously tagged by an Oracle.
This article provides a description of the amplitude amplification quantum algorithm mechanism in a very short computational way.
arXiv Detail & Related papers (2022-10-30T10:55:25Z) - 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) - Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles.
We use a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms.
Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases.
arXiv Detail & Related papers (2022-03-17T19:26:00Z) - Developing Mathematical Oracle Functions for Grover Quantum Search
Algorithm [0.0]
This article highlights some of the key operating principles of Grover algorithm.
It illustrates the possibility of using Grover algorithm for solving more realistic and specific search problems.
arXiv Detail & Related papers (2021-09-03T14:07:05Z) - 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) - 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-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z) - Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems.
Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
arXiv Detail & Related papers (2020-09-11T17:31:39Z)
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.