Grover’s quantum

search algorithm
How can we use a quantum computer to find a needle in a haystack?

https://lonewolfonline.net/stars-point-delphis-oracle/

• Quantum oracle
• Useful quantum speedup
 Grover’s search algorithm - concept

creates
superposition quantum
parallelism

n qubits

n
2
possible states
= paths in the
interferometer
 Entanglement Grover’s search algorithm - concept
and algorithmic
1 2 ?
<latexit sha1_base64="r8rdnHZ88shrnBftAmhbMVZHbpE=">AAAB6HicbVDLSgNBEOyNrxhfUY9eBoPgKewGUW8GvXhMwDwgWcLspDcZMzu7zMwKIeQLvHhQxKuf5M2/cZLsQRMLGoqqbrq7gkRwbVz328mtrW9sbuW3Czu7e/sHxcOjpo5TxbDBYhGrdkA1Ci6xYbgR2E4U0igQ2ApGdzO/9YRK81g+mHGCfkQHkoecUWOl+k2vWHLL7hxklXgZKUGGWq/41e3HLI1QGiao1h3PTYw/ocpwJnBa6KYaE8pGdIAdSyWNUPuT+aFTcmaVPgljZUsaMld/T0xopPU4CmxnRM1QL3sz8T+vk5rw2p9wmaQGJVssClNBTExmX5M+V8iMGFtCmeL2VsKGVFFmbDYFG4K3/PIqaVbK3mW5Ur8oVW+zOPJwAqdwDh5cQRXuoQYNYIDwDK/w5jw6L86787FozTnZzDH8gfP5A5IfjMo=</latexit>

interference
…
1 x
2 x
3 x
… … x
N x …

Grover step

Grover step

Grover step
…

…
 Comparison classical vs quantum algorithm:
For searching 1 among N elements:

Quantum search:
1 x
2 x
3 x
Classical search:
… …
x
Quadratic quantum speedup

Classical Quantum
Discussion
Q: What if we don’t know the number of solutions M (and thus M/N)?
Running the algorithm for too long decreases the chance to find a solution!

A: The algorithm can be adapted (essentially making systematicp guesses for

<latexit sha1_base64="XpapfdzwtGOt85SMgSyiony4Va8=">AAACAHicbVDLSsNAFJ3UV62vqAsXbgaLUDc1kaIui27cqBXsA5pQJtNJO3QyiTMToYRs/BU3LhRx62e482+ctFlo64ELh3Pu5d57vIhRqSzr2ygsLC4trxRXS2vrG5tb5vZOS4axwKSJQxaKjockYZSTpqKKkU4kCAo8Rtre6DLz249ESBryezWOiBugAac+xUhpqWfuOQFSQ4xYcptWHPkgVHJzfJ0e9cyyVbUmgPPEzkkZ5Gj0zC+nH+I4IFxhhqTs2lak3AQJRTEjacmJJYkQHqEB6WrKUUCkm0weSOGhVvrQD4UuruBE/T2RoEDKceDpzuxcOetl4n9eN1b+uZtQHsWKcDxd5McMqhBmacA+FQQrNtYEYUH1rRAPkUBY6cxKOgR79uV50jqp2qfV2l2tXL/I4yiCfXAAKsAGZ6AOrkADNAEGKXgGr+DNeDJejHfjY9paMPKZXfAHxucPchaWUA==</latexit>

for M/N) and still finds a solution with an expected number O( N/M ) of runs.

The algorithm can also be adapted to estimate the number of solutions M:

Quantum Counting (see Nielsen & Chuang Sec. 6.3)
Discussion
The Grover algorithm can be used to speed up NP-complete problems.
(The Puzzle Museum)
(see Nielsen & Chuang Sec. 6.4)
Is there a path along the edges of a dodecahedron visiting each vertex once and only once?

Example: Hamiltonian-path problem

Hamiltonian cycle
<latexit sha1_base64="cxarwX0I3lAI+ZMYiZ24gxK2pW8=">AAACAHicbVDLSsNAFJ34rPUVdeHCzWAR6qYkpagboejGZQX7gCYtk8mkHTqZCTMToYRu/BU3LhRx62e482+ctllo64ELh3Pu5d57goRRpR3n21pZXVvf2CxsFbd3dvf27YPDlhKpxKSJBROyEyBFGOWkqalmpJNIguKAkXYwup367UciFRX8QY8T4sdowGlEMdJG6tvHvMfhNaz2Mu7hUGiPiUGZn0/6dsmpODPAZeLmpARyNPr2lxcKnMaEa8yQUl3XSbSfIakpZmRS9FJFEoRHaEC6hnIUE+Vnswcm8MwoIYyENMU1nKm/JzIUKzWOA9MZIz1Ui95U/M/rpjq68jPKk1QTjueLopRBLeA0DRhSSbBmY0MQltTcCvEQSYS1yaxoQnAXX14mrWrFvajU7mul+k0eRwGcgFNQBi64BHVwBxqgCTCYgGfwCt6sJ+vFerc+5q0rVj5zBP7A+vwBaFiVqg==</latexit>

n n·log(n) (wolfram)
Brute-force search through all n =2 paths
<latexit sha1_base64="VACX6S1zM0TEYMFKjZm+Pr9PbYY=">AAACAXicbVDLSsNAFJ3UV62vqBvBzWAR6qYmpajLohuXFewDmlgmk0k7dDITZiZCCXXjr7hxoYhb/8Kdf+O0zUKrBy4czrmXe+8JEkaVdpwvq7C0vLK6VlwvbWxube/Yu3ttJVKJSQsLJmQ3QIowyklLU81IN5EExQEjnWB0NfU790QqKvitHifEj9GA04hipI3Utw+SCj+BtbuMezgU2mNiYITT2qRvl52qMwP8S9yclEGOZt/+9EKB05hwjRlSquc6ifYzJDXFjExKXqpIgvAIDUjPUI5iovxs9sEEHhslhJGQpriGM/XnRIZipcZxYDpjpIdq0ZuK/3m9VEcXfkZ5kmrC8XxRlDKoBZzGAUMqCdZsbAjCkppbIR4iibA2oZVMCO7iy39Ju1Z1z6r1m3q5cZnHUQSH4AhUgAvOQQNcgyZoAQwewBN4Aa/Wo/VsvVnv89aClc/sg1+wPr4BiMGVrQ==</latexit>

n·log(n)/2
Quantum speed-up: reduction to p(n)2

polynomial quadratic
overhead speed-up

Important: Grover (and quantum computers in general) do NOT allow one to

solve NP-complete problems efficiently.
Discussion

Optimality (see Nielsen & Chuang Sec. 6.6)

One can prove that there exists no quantum algorithm that can perform
the task with less than
<latexit sha1_base64="aHnsY7oaHo07+NeDYLLcDHs6qQE=">AAACE3icbVDLSsNAFJ3UV62vqEs3wSJUFyWRoi6LbtyoFewDmlAm00k7dPJw5kYoIf/gxl9x40IRt27c+TdO2iy09cDA4Zx7uXOOG3EmwTS/tcLC4tLySnG1tLa+sbmlb++0ZBgLQpsk5KHouFhSzgLaBAacdiJBse9y2nZHF5nffqBCsjC4g3FEHR8PAuYxgkFJPf3I9jEMCebJTWpz6kHFlvcCEtsTmCTXaXKVprZggyEc9vSyWTUnMOaJlZMyytHo6V92PySxTwMgHEvZtcwInAQLYITTtGTHkkaYjPCAdhUNsE+lk0wypcaBUvqGFwr1AjAm6u+NBPtSjn1XTWYJ5KyXif953Ri8MydhQRQDDcj0kBdzA0IjK8joM0EJ8LEimAim/mqQIVZtgKqxpEqwZiPPk9Zx1Tqp1m5r5fp5XkcR7aF9VEEWOkV1dIkaqIkIekTP6BW9aU/ai/aufUxHC1q+s4v+QPv8AabWn0g=</latexit>

r !
N
O
M

oracle inquiries.

Thus, the Grover algorithm is optimal.