# Why is this implementation of the order finding algorithm not working?

I asked a question about this earlier, but I am still coming across problems in my algorithm implementation.

I am trying to implement the order finding algorithm on Cirq finding the minimal positive $$r$$ for coprime $$x$$ and $$N$$ satisfying the equation $$x^r \ = \ 1$$(mod$$\ N$$). In my case, I have set $$x \ = \ 2$$ and $$N \ = \ 3$$, so the algorithm should output $$r \ = \ 2$$.

Since the unitary is defined by $$U|y\rangle \ = \ |2^jy$$mod($$3)\rangle$$, and $$y \ = \ |1\rangle$$, then the value of $$U|1\rangle$$ should simply switch back and forth between $$|1\rangle$$ and $$|2\rangle$$. Since we are defining:

$$2^j$$mod($$3) \ = \ \big(2^{j_1 2^0}$$mod($$3)\big)\big(2^{j_2 2^1}$$mod($$3)\big) \ ... \ \big(2^{j_t 2^{t-1}}$$mod($$3)\big)$$

Each of the terms in the form $$\big(2^{j_k 2^k}$$mod($$3)\big)$$ becomes $$\big(1 \$$mod($$3)\big)$$, except for when $$k \ = \ 0$$, in which case we get $$\big(2 \$$mod($$3)\big)$$. Because of this, I implemented two $$CNOT$$ gates being controlled by the $$j_1$$ qubit acting on each of the two qubits acting as $$|y\rangle$$ ($$|1\rangle$$ is mapped to $$|2\rangle$$ if the control qubit is $$|1\rangle$$, and $$|1\rangle$$ is mapped to $$|1\rangle$$ if the control qubit is $$|0\rangle$$). It doesn't seem necessary to implement more gates on all the other $$j$$ qubits because mathematically, they turn out to act trivially in this context.

After this, I then pass all of the $$j$$ qubits through the inverse quantum Fourier transform. The outputs I'm getting seem kind of strange:

(This is all $$7$$ of the $$j$$ qubits measured for $$20$$ iterations of the circuit).

I was just wondering if anyone had any insight, since I feel as though I made some kind of mistake in creating the unitary.

I don't think this is necessarily a coding problem but just in case it is helpful, this is the code I have for the circuit so far:

# Quantum Order Finding Algorithm

import cirq
import numpy as np
import random
import tensorflow as tf
import time
import timeit
from cirq.google import ExpWGate, Exp11Gate, XmonMeasurementGate
from cirq.google import XmonSimulator
from matplotlib import pyplot as plt
from itertools import combinations
from cirq.circuits import InsertStrategy

# Gate schematic --> Hadamard (0) --> Controlled Phase gate (1, 0) --> Hadamard (1) --> Swap (0, 1) --> Measure (0, 1)

n = 5
a = 2

qubits = []
for i in range(0, n):
qubits.append(cirq.GridQubit(0, i))

other_qubits = []
for k in range(n, n+a):
other_qubits.append(cirq.GridQubit(0, k))

circuit = cirq.Circuit()

#Preparing the qubits

for j in qubits:
had_gate = cirq.H.on(j)
circuit.append([had_gate], strategy=InsertStrategy.EARLIEST)

'''
for l in other_qubits:
x_gate = cirq.X.on(l)
circuit.append([x_gate], strategy=InsertStrategy.EARLIEST)
'''

circuit.append(cirq.X.on(other_qubits[1]))

#Applying the unitary

circuit.append([cirq.CNOT.on(qubits[0], other_qubits[0]), cirq.CNOT.on(qubits[0], other_qubits[1])])
#circuit.append([cirq.CNOT.on(qubits[0], other_qubits[1]), cirq.CNOT.on(qubits[0], other_qubits[2]), cirq.CNOT.on(qubits[1], other_qubits[2]), cirq.CNOT.on(qubits[1], other_qubits[0]), cirq.CCX.on(qubits[0], qubits[1], other_qubits[0])])

#Applying the Inverse QFT

circuit.append(cirq.SWAP.on(qubits[0], qubits[4]))
circuit.append(cirq.SWAP.on(qubits[1], qubits[3]))

for b in range(0, n):
place = n-b-1
for h in range(n-1, place, -1):
holder = h
gate = cirq.CZ**(1/(2**(h-place)))
circuit.append(gate.on(qubits[holder], qubits[place]))
circuit.append(cirq.H.on(qubits[place]))

def circuit_init_again(meas=True):
if meas:
yield XmonMeasurementGate(key='qubit0')(qubits[0])
yield XmonMeasurementGate(key='qubit1')(qubits[1])
yield XmonMeasurementGate(key='qubit2')(qubits[2])
yield XmonMeasurementGate(key='qubit3')(qubits[3])
yield XmonMeasurementGate(key='qubit4')(qubits[4])

#circuit.append()
circuit.append(circuit_init_again())

print(" ")
print(" ")
print(circuit)
print(" ")
print(" ")

simulator = XmonSimulator()
result = simulator.run(circuit, repetitions=50)
print(result)


## 1 Answer

You can test stand alone the a modular multiplication circuit. In this case $$\text{base} = 2$$ and $$N = 3$$. However the smallest useful composite $$N = 15 = 3 \times 5$$.

Let's take a well known Multiplication by 7 modulo 15 circuit

We start with input $$\ |1\rangle \text{ gives } |7\rangle$$ $$\ |7\rangle \text{ gives } |4\rangle$$ $$\ |4\rangle \text{ gives } |13\rangle$$ $$\ |13\rangle \text{ gives } |1\rangle$$ This repeats after $$4$$ times and the period = $$4$$

In the not so useful case of $$N = 3$$ and $$a = 2$$

$$1 \times 2 \text{mod} (3) = 2$$

$$2 \times 2 \text{mod} (3) = 1$$

It repeats after $$2$$ times. Period is correct $$2$$ and can be tested in a quantum simulator.