2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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/…. $\endgroup$
    – Jack Ceroni
    Dec 4, 2018 at 22:39
  • $\begingroup$ 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. $\endgroup$
    – Jack Ceroni
    Dec 4, 2018 at 22:44
  • $\begingroup$ 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. $\endgroup$
    – Craig Gidney
    Dec 4, 2018 at 22:56
  • $\begingroup$ The outputs from my circuit seem to match the Quirk circuit, so the algorithm should be working now. On a side note, when you refer to the period finding algorithm, is that the same thing as the order finding algorithm? $\endgroup$
    – Jack Ceroni
    Dec 5, 2018 at 4:46
  • 1
    $\begingroup$ @JackCeroni yes $\endgroup$
    – Craig Gidney
    Dec 5, 2018 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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