Optimizing Quantum Search

This is an informal presentation of the ideas behind our recently released paper about a modified version of the Grover's Search Algorithm that removes the NOT gates from the standard implementation of the inversion-by-the-mean (amplification) step.

Grover's Search Algorithm is one of the first concepts in Quantum Computing that people need to grasp. It was also one of the first reusable utilities we implemented in code. Its main ingredient is the Grover Iterate which is executed a number of times in order to amplify the amplitude of the outcomes of interest. The iterate is also used in the Amplitude Estimation procedure, making its efficient implementation quite important.

I will provide a couple of insights that can shed more light on the intuition behind the iterate and can lead to an implementation with a smaller number of gates. The main insight is that you don't have to undo the superposition to go back to the |0...0> state in the amplification step, but you can go to another state, e.g. |1...1> in order to implement the inversion about the mean. As an example, instead of using this circuit for the amplification step of the iterate:

 we can use one that eliminates the X gate, and uses a more atomic gate than H on each qubit:

All the implementations I have seen use the first circuit, starting with IBM's Qiskit, Google's Cirq, all tutorials like this one, or this Nature paper.

Background: Grover's Search Algorithm

The high level description of the algorithm is contained in this diagram from Wikipedia or one of IBM's tutorials:

Essentially there are 3 steps, with the last two repeated a number of times before measuring:

1. Create a superposition of the outcomes in the search space
2. Flag the outcomes of interest using an oracle that multiplies the amplitude of these outcomes by -1 (geometrically this is a reflection in the space of the "bad" states)
3. The amplification step, performing inversion around the mean (geometrically this is a reflection around the whole state), and it has 3 substeps":undo the superposition, multiply the amplitude of |0...0> by -1, and then redo the superposition.

The full circuit that performs the search for 5, represented as 101 in binary form, on 3 qubits is:

 The measurement histogram shows that 5 will be measured with a very high probability:

Modified Algorithm:

We will make 2 changes:

• Use Rx(pi/2) instead of H to create the initial superposition. In Qiskit Rx(pi/2) is a basic/atomic gate, from which H can be created with an additional phase gate applied in software.
• In the amplification step, instead of applying another H to remove the superposition, apply another Rx(pi/2) instead, which will lead to the |1...1> state, instead of |0...0>. To go back to the superposition after flipping the phase of |1...1>, apply Rx(-pi/2).

The identity Rx(pi) = -iX shows that applying Rx(pi/2) twice goes from |0...0> to |1...1> up to a rotation. The latter state is easier to match with controlled gates. The full circuit requires 12 fewer X gates and 15 U1 gates being not necessary:

On different quantum platforms Rx(pi/2) can be replaced with a different primitive. The histogram is identical. Replacing H with a gate that creates a different equal superposition can be done in many cases, but not all, of course.

Conclusion

The theoretical versions of quantum algorithms do not have to be implemented by the book. In the NISQ era versions that use a smaller number of gates may give an advantage. In our papers we have discussed modified versions of the oracle step as well, and may create an expanded writeup on the Grover Iterate.

Personally, I find the geometric angle to provide valuable insights for both understanding and improving quantum algorithms. The computational, combinatorial and probabilistic views have also helped me a lot, unlike the algebraic and physical views. I am biased of course, but the connection between multiple perspectives is one of the reasons Quantum Theory is so fascinating, and one of the reasons it is such an addictive hobby.