Questions tagged [grovers-algorithm]

Grover's search algorithm is an algorithm that can perform a search in the order of square root of the input size. This is a provable speed up over the best classical algorithm, which requires a time of order N to perform a search.

65 questions
1k views

Is there a layman's explanation for why Grover's algorithm works?

This blogpost by Scott Aaronson is a very useful and simple explanation of Shor's algorithm. I'm wondering if there is such an explanation for the second most famous quantum algorithm: Grover's ...
770 views

Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?

(Sorry for a somewhat amateurish question) I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially ...
261 views

Can adiabatic quantum computing be faster than Grover's algorithm?

It has been proven that adiabatic quantum computing is equivalent to "standard", or gate-model quantum computing. Adiabatic computing, however, shows promises for optimisation problems, where the ...
832 views

Grover's algorithm: where is the list?

Grover's algorithm is used, among other things, to search an item $\mathbf{y}$ in an unordered list of items $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ of length $n$. Even though there are ...
832 views

What applications does Grover's Search Algorithm have?

Grover's Search algorithm is usually talked about in terms of finding a marked entry in an unsorted database. This is a natural formalism that lets it be applied directly to searching for solutions to ...
587 views

139 views

How many qubits does it take to break a 10 characters password?

Let's assume we developed a hashcat-like programs for quantum computer. How many qubits we need to find the correct hash (WPA, MD5,...) from a 10 characters password make from upper, lower & ...
52 views

Success probability in Grover's algorithm where there are multiple targets

The Grover algorithm allows you to search for multiple elements. Assuming my search space contains four elements, if I only search for one element, I get the one I'm looking for with a probability of ...
137 views

Grover operator as a rotation matrix

I have seen that it is possible to represent the Grover iterator as a rotation matrix $G$. My question is, how can you do that exactly? So we say that $|\psi\rangle$ is a superposition of the states ...
126 views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
111 views

Grover search with single query to $f(x)$ and multiple queries to $f(x) = a$

Assume $f(x)$ is an $n$ bits to $m$ bits function and we want to use Grover's search algorithm to find $x$ such that $f(x) = a$, where $a$ is some $m$-bit predetermined value. When using the ...
124 views

Finding the second smallest number. Is it achievable in QC?

I have a set of numbers in a superposition state (example: 3,8,1,5) in a quantum register (of 3 qubits). So I try to find the $n^{\text{th}}$ smallest number (...
197 views

Why does Grover's search invert about the mean?

Let $\vert s\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N\vert x_i\rangle$ be an equal superposition over states from which we need to find one solution state $\vert w\rangle$. The phase flip operator in ...
333 views

Grover's algorithm: number of searches

I would like to start my question with a quote: If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means ...
84 views

I'm studying the quantum search algorithm on this book: M.A. Nielsen, I.L. Chuang, "Quantum Computation and Quantum Information", Cambridge Univ. Press (2000) [~p. 252]. To sum up we have a state: $... 1answer 184 views Grover's algorithm – DES circuit as oracle? In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible$|x\rangle\rightarrow(-1)^{f(x)}|x\rangle$. I have read that it ... 1answer 76 views Counting in Q#: number of solutions I have this program derived from Microsoft Quantum Katas for counting (see here): ... 1answer 62 views Reversible crypto systems for use in the Grover's algorithm I'm working on some papers (here and here) that use the Grover algorithm to crack krypto systems like AES and SHA. I had already asked a first question here. Now, however, a new question has arisen ... 1answer 266 views Example of Grover's Algorithm applied to a decision problem? I recently asked this question on Grover's algorithm, and I am still fairly confused about the whole thing. Consider the following snippet from this post (written by DIDIx13) which for convenience I ... 1answer 88 views Proof that Grover's operator can be written as$D_N=-H_n R_N H_n$I am interested in showing the validity of the Grover operator. Now there are several ways to show it. One way is with complete induction. It has to be shown that the following relationship applies:$...
I am currently working on the Grover algorithm and have a few questions. In the third step of the algorithm, a phase shift is performed on all states, except $|0\rangle$. My question is, why is the ...