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)