What is the general method for creating real gate sequences from mathematical algorithms?

Question

Background

I have been doing research on quantum computing on my own for over a year now and I feel like I may have missed a fundamental step. I have no idea how to take a mathematical algorithm and create an equivalent gate sequence for an actual Quantum Computer to follow. I would like to be able to read articles on quantum algorithms and be able to create circuits from them, but unless I can find an example of how the gates are set up I am stuck. Even more frustrating is when gates are shown but are just representations of subroutines instead of the basic gates (example on page 5).

Grover's Algorithm Example

For example, I am pretty familiar with Grovers algorithm. For Grover's algorithm you perform the following steps (I'm borrowing from Wikipedia a bit):

1. Initialize all qubits to a $\left| 0 \right>$ except for a specified qubit (the oracle qubit according to Wikipedia) you initialize to $\left| 1 \right>$; this will be the target of the Orcale.

2. Put all qubits, except for ancilla bits, into a superposition using Hadamard gates. The mathematical algorithm says that this is equivalent to the following:

   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$

I can kind of see how this would translate to Hadamard gates because we have the $\sqrt{N}$ on the denomonator.

3. Next comes the trickiest part in my opinion, the Orcale. The oracle, a black box function (in my experience) can be created by formulating the problem as a SAT problem and then creating an equivalent quantum circuit that ultimately flips the "target bit." The mathemitacal algorithm says this is equivelent to ${\displaystyle |x\rangle |q\rangle \,{\overset {U_{\omega }}{\longrightarrow }}\,|x\rangle |q\oplus f(x)\rangle ,}$ where $U_w$ is the oracle and $|q\rangle$ is that subroutine as an operatior.

Again, this seems a little intuitive to me because I know the $|q\rangle$ should XOR the oracle qubit.

4. Grover's diffusion operator is pretty darn confusing. Wikipedia defines this operator to be ${\displaystyle 2|s\rangle \langle s|-I}$.

From experience I know this can be achieved by sandwiching a large controlled Z, with target on last logical qubit that isn't the oracle qubit, by H and X gates like so:

I have no earthly idea how I would have figured that out from the instructions "${\displaystyle 2|s\rangle \langle s|-I}$"

5. Repeat steps 3 and 4 $O \sqrt{N}$ times and then measure.

Question

What are some general methods or practices for creating gate sequences from mathematical algorithms? Seeing as there are many ways to create equivalent gate sequences, I am assuming that performing this process is an art that takes practice and experience. That being said, where should I start? What advice can you give me?

Answer 1

This is a complicated question, which I am definitely not the most qualified to answer, but I encountered the same questioning during my learning path, and I had to find the answers by myself. Therefor, this is a partial answer, to contribute the the real answer which will be proposed (I hope) later.

I think the example you give is a very good one and I will list some elements which helped me with this example :

Trying to understand what everything means

As with every formula, understanding the variables which compose it is essential. This will give you insight of what the input is. For example, Grover's Diffusion operator is composed out of 3 elements : $2$, $I$ and $|s\rangle\langle s|$. $2$ and $I$ are easy to understand but $|s\rangle\langle s|$ is not. However, understanding this operator is key, as it is a matrix with the square of every amplitude in the diagonals starting from the top right.

Representing everything with a single matrix

This is something debatable, but it helped me a lot to visualize the entire thing in one image. This can make us able to see inversions using $X$ gates or simplifications with $H$ gates. For example, by calculating the $X$ gates of Grover's Diffusion operator (see example), we can change the $-1$ of sides, which transforms everything in a controlled-$Z$ gates.

Plugin in simple values

The representation of the state vector gets extremely complex after a couple of iterations in many algorithms and there is no way to visualize it simply. However, sometimes there are specific values that often simplify the problem. For example, when the first diffusion operator is applied : $|s\rangle \approx |+\rangle ^{\otimes n}$ (there is only a negative phase, which is removed in the outer product). This state can easily be simplified using $H^{\otimes n}$. Therefor, plugin in the simple values can easily help.

Conclusion

As you can see, this is not an "algorithmic" method to do what you want. It is similar to what you think like during a proof. But I hope these small tips can help you in your work. This is not meant to be a complete answer, so I hope someone can be more complete.