2
$\begingroup$

Can you explain the mathematical details of Grover's algorithm for children?

$\endgroup$
1
  • 2
    $\begingroup$ We're not ChatGPT. $\endgroup$
    – DannyNiu
    Apr 21, 2023 at 10:23

1 Answer 1

3
$\begingroup$

This is the crypto stack exchange. And if there is one thing I learned in crypto, you always have to specify everything, especially the power of the participants.

Therefore, because you did not specify the knowledge of the children, I assume all children have graduated in computer science and quantum mechanics. Thus, they will easily understand the following:

  1. Initialize the system to the uniform superposition over all states:

$$ |\psi_0\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} |i\rangle, $$

Obviously $N$ is the search space.

  1. Oracle for state $|\psi_0\rangle$ to invert $|w\rangle$:

\begin{equation} |\psi_1\rangle = U_w |\psi_0\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} (-1)^{f(i)} |i\rangle, \end{equation}

where $f(i) = 1$ if $i=w$ or $f(i) = 0$

  1. Amplify $|w\rangle$ with: \begin{equation} |\psi_2\rangle = S D |\psi_1\rangle = S \left(2 |\psi_1\rangle \langle \psi_1| - \mathbb{I} \right) |\psi_1\rangle, \end{equation} with: \begin{equation} S|i\rangle = (-1)^{i=w}|i\rangle. \end{equation} and: \begin{equation} D = 2|\psi_0\rangle\langle\psi_0| - I, \end{equation}

  2. Iterate over 2. and 3. $O(\sqrt{N})$ times to increase probability. Trivial.

  3. Measure quantum state. Everyone knows how that works.

"Yes, it really is that simple"

Edit: I forgot the relation to crypto. Just assume a cryptographic scheme as the black box function to which the Grovers algorithm is applied and brute force the key.

/s

Maybe this answers your question.

$\endgroup$
1
  • $\begingroup$ When explaining a cryptographic thing (e.g. signature) to children, I find it useful to first explain what the thing does (e.g. allow public verification of the authenticity of a message) and under what high level assumptions (e.g. authenticity of a public key, and secrecy of a matching private key known only to signer), without explaining the how (e.g. RSA or ECDSA) at first. The current answer does that only in the final Edit. IMHO that should be first, and more detailed. $\endgroup$
    – fgrieu
    Apr 21, 2023 at 11:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.