6
$\begingroup$

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): enter image description here

  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.

  1. 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.

  1. 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:

enter image description here

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

  1. 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?

$\endgroup$
7
  • $\begingroup$ Also, any feedback or critique on my question formatting is more than welcome. $\endgroup$ Feb 25 at 16:29
  • 1
    $\begingroup$ What do you mean by "mathematical algorithms?" Are you wanting more information about implementing your favorite SAT problem as a quantum oracle? If so then this is often purely a classical problem of implementing a reversible set of gates - if you are familiar with ANDs and ORs and NANDs and NORs, then you should get familiar with CCNOTS and CCSWAPS while relying on the ancilla qubits as extra workspace. $\endgroup$
    – Mark S
    Feb 25 at 19:21
  • 1
    $\begingroup$ Maybe this can help a bit $\endgroup$ Feb 26 at 10:17
  • 1
    $\begingroup$ generally speaking, decomposing a complex gate using a given set of elementary gates is not a trivial matter. A quantum algorithm that claims efficiency would need to show how each complex operation decomposes into elementary gates, or at least argue that this is possible for some reason. In some sense, devising a (useful) quantum algorithm is essentially the task of finding a way to decompose a complex operation/gate into a (not too long) sequence of elementary gates. There is no general way to do it, this is essentially what a paper presenting an algorithm tells you how to do $\endgroup$
    – glS
    Feb 26 at 16:14
  • 1
    $\begingroup$ in the example of Grover you give, you essentially already have such decomposition: $U_\omega$ is a permutation matrix and thus can be implemented as the reversible circuit corresponding to the classical operation; $H$ is the elementary gate that is assumed to be implementable in this context, and $2|0\rangle\!\langle0|-I$ is again a permutation matrix. There is no easy way to find such a decomposition for a given algorithm; finding such decompositions is what devising a quantum algorithm is about $\endgroup$
    – glS
    Feb 26 at 16:19
4
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.