The Simon Search Algorithm

As a second example of a classic quantum algorithm, we look at the Simon algorithm, first developed in the 1990s. While it has some general structural similarities to the Deutsch algorithm, it is also more complicated; so, hang on to your gates. We will follow the analysis given in Bernhardt’s Quantum Computing for Everyone, but with several additional explanations and examples to make the steps clearer. Once again, the strategy is to make use of superposition and entangled quantum states to create an algorithm that is more efficient than the corresponding classical algorithm.