The algorithm is being implemented on Cirq, with the goal of finding the smallest $r$ for cooprime numbers $x$ and $N$ satisfying the equation $x^r \ = \ 1($mod $N)$. I have set $x \ = \ 2$ and $N \ = \ 3$, so the algorithm should output $r \ = \ 2$.

This is the circuit that Cirq outputs for my code. Are there any mistakes that I'm making in the algorithm implementation, as I am getting some strange results:

enter image description here

The Fourier transform part (everything from the swaps onward) looks correct. The initialization (column of Hadamards) looks correct. But the part where you do controlled modular multiplications doesn't, because there's no operations controlled on the 2nd through fifth qubits that you are QFT-ing.

You also seem to expect the output to be the period, when actually the output is a number of the form $2^n / (kp)$ where $p$ is the period and $k$ is an integer and $n$ is the number of qubits in your QFT. This blog post may be helpful..

Here is my recommendation on how to proceed.

  1. Start from Quirk's example period finding circuit:

    example period from quirk

  2. In Quirk, adjust the circuit to apply to your case, where $B=2$ and $R=3$.

  3. Replace the $\times B^A \pmod{R}$ operation with a series of controlled $\times A \pmod{R}$ operations, with a different $A=\text{constant}$ for each one.

  4. Replace each $\times A \pmod{R}$ operation, one by one, with simple gates such as CNOTs and Toffolis.

  5. Replace the inverse QFT with simple gates such as Hadamards and controlled phases.

  6. Compare with the circuit you're trying to make in Cirq.

As you are making the circuit transformations, keep an eye on the output display. If the spikes have moved around or changed, you made a mistake when doing a decomposition.

  • Thank you for your answer. However, wouldn't the operations from the second through fifth qubits be trivial? I outlined the mathematical reasoning in a question I posted yesterday: quantumcomputing.stackexchange.com/questions/4852/…. – Jack Ceroni Dec 4 at 22:39
  • Also, I'm passing the output through the continued fraction algorithm, I only provided the quantum part here because it is the part that seems not to be working. – Jack Ceroni Dec 4 at 22:44
  • I suppose that's true, since the operation has period 2 it's the identity for larger controls. Generally speaking you want to avoid taking advantage of information like that, since you're using the solution in order to formulate the computation to get the solution... oh well. If you're not getting the right answer, you might just have your endian-ness backwards. Try moving the control from the top qubit of the QFT to the bottom qubit of the QFT. – Craig Gidney Dec 4 at 22:56
  • Ok, I'll try that, thank you. – Jack Ceroni Dec 4 at 22:56
  • 1
    @JackCeroni yes – Craig Gidney Dec 5 at 17:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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