Grover's Algorithm

Theory

Amplitude Amplification

The uniform superposition: $|u\rangle =H^{\otimes n}|0\rangle ^{n}$, where $H$ is the Hadamard gate.

Apply the oracle reflection $U_{w}|u\rangle =|u'\rangle$.

Apply an other reflection about the state $|u\rangle$, also $U_{u}=2|u\rangle \langle u|-1$. Thus we are at state $U_{u}U_{w}|u>$. This amplifies by two the amplitude of state $|w\rangle$.

Repeat $t$ times, where $t\approx {\sqrt {N}}$.

Application: Lights Out

We solve the $3\times 3$ tiling game using superposition (instead of Gaussian elimination). First, the numbering system is shown below:

0	1	2
3	4	5
6	7	8

Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus the toggle mapping is:

• 0 -> {0, 1, 3}
• 1 -> {0, 1, 2, 4}
• 2 -> {1, 2, 5}
• 3 -> {0, 3, 4, 6}
• 4 -> {1, 3, 4, 5, 7}
• 5 -> {2, 4, 5, 8}
• 6 -> {3, 6, 7}
• 7 -> {4, 6, 7, 8}
• 8 -> {5, 7, 8}

References

https://mathworld.wolfram.com/LightsOutPuzzle.html

http://perfectweb.org/ddo/solver/vale_puzzle.html

https://gaming.stackexchange.com/questions/11123/strategy-for-solving-lights-out-puzzle

References

https://medium.om/swlh/grovers-algorithm-quantum-computing-1171e826bcfb

https://quantumcomputinguk.org/tutorials/grovers-algorithm-with-code

https://jonathan-hui.medium.com/qc-grovers-algorithm-cd81e61cf248

https://arxiv.org/pdf/1804.03719.pdf

https://www.quantum-inspire.com/kbase/grover-algorithm/

http://davidbkemp.github.io/animated-qubits/grover.html

https://quantum-computing.ibm.com/docs/iqx/guide/grovers-algorithm

https://qudev.phys.ethz.ch/static/content/courses/QSIT12/presentations/Grover_superconducting.pdf

https://quantumcomputing.stackexchange.com/questions/2110/grovers-algorithm-where-is-the-list

https://qudev.phys.ethz.ch/static/content/QSIT16/talks/Grover_QSIT.pdf

https://grove-docs.readthedocs.io/en/latest/grover.html

https://thequantumdaily.com/2019/11/13/quantum-programming-101-grovers-algorithm/