Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn information-theoretic analysis of Grovers algorithm
63
0
0.0
(
0
)
Authors
Erdal Arikan
Ask ChatGPT about the research
No Arabic abstract
Grover discovered a quantum algorithm for identifying a target element in an unstructured search universe of N items in approximately square-root of N queries to a quantum oracle, thus achieving a square-root speed-up over classical algorithms. We present an information-theoretic analysis of Grovers algorithm and show that the square-root speed-up is the best attainable result using Grovers oracle.
rate research
Read More
Grovers algorithm, a well-know quantum search algorithm, allows one to find the correct item in a database, with quadratic speedup. In this paper we adapt Grovers algorithm to the problem of finding a correct answer to a natural language question in English, thus contributing to the growing field of Quantum Natural Language Processing. Using a grammar that can be interpreted as tensor contractions, each word is represented as a quantum state that serves as input to the quantum circuit. We here introduce a quantum measurement to contract the representations of words, resulting in the representation of larger text fragments. Using this framework, a representation for the question is found that contains all the possible answers in equal quantum superposition, and allows for the building of an oracle that can detect a correct answer, being agnostic to the specific question. Furthermore, we show that our construction can deal with certain types of ambiguous phrases by keeping the various different meanings in quantum superposition.
Grovers algorithm for quantum searching is generalized to deal with arbitrary initial complex amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the marked and unmarked states. These equations are solved exactly. New expressions are derived for the optimal time of measurement and the maximal probability of success. They are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments. Our results imply that Grovers algorithm is robust against modest noise in the amplitude initialization procedure.
Grovers quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modelled easily because of the exact recursion formulas available for computing the quantum amplitude in Grovers algorithm. We study the algorithms intrinsic robustness when no quantum correction codes are used, and evaluate how much noise the algorithm can bear with, in terms of the size of the phone book and a desired probability of finding the correct result. The algorithm loses efficiency when noise is added, but does not slow down. We also study the maximal noise under which the iterated quantum algorithm is just as slow as the classical algorithm. In all cases, the width of the allowed noise scales with the size of the phone book as N^-2/3.
We present new results on an optical implementation of Grovers quantum search algorithm. This extends previous work in which the transverse spatial mode of a light beam oscillates between a broad initial input shape and a highly localized spike, which reveals the position of the tagged item. The spike reaches its maximum intensity after $simsqrt N$ round trips in a cavity equipped with two phase plates, where $N$ is the ratio of the surface area of the original beam and the area of the phase spot or tagged item. In our redesigned experiment the search space is now two-dimensional. In the time domain we demonstrate for the first time a multiple item search where the items appear directly as bright spots on the images of a gated camera. In a complementary experiment we investigate the searching cavity in the frequency domain. The oscillatory nature of the search algorithm can be seen as a splitting of cavity eigenmodes, each of which concentrates up to 50% of its power in the bright spot corresponding to the solution.
We study the entanglement content of the states employed in the Grover algorithm after the first oracle call when a few searched items are concerned. We then construct a link between these initial states and hypergraphs, which provides an illustration of their entanglement properties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
