# In Simon's algorithm, is there a general method to define an oracle given a certain periodicity?

I have to implement Simon's algorithm in Cirq. I have problems determining the oracle $$f(x)$$ defined such that $$f(x)=f(x\oplus a)$$ from a certain value of $$a$$.

Given a random $$a$$, is there a general way to define the oracle $$f$$? Or at least, how can I determine the oracle from a certain $$a$$?

I think the following code (from Cirq Github repo) answers my question but I cannot understand it.

def make_oracle(input_qubits, output_qubits, secret_string):
"""Gates implementing the function f(a) = f(b) iff a ⨁ b = s"""
# Copy contents to output qubits:
for control_qubit, target_qubit in zip(input_qubits, output_qubits):
yield cirq.CNOT(control_qubit, target_qubit)

# Create mapping:
if sum(secret_string):  # check if the secret string is non-zero
# Find significant bit of secret string (first non-zero bit)
significant = list(secret_string).index(1)

# Add secret string to input according to the significant bit:
for j in range(len(secret_string)):
if secret_string[j] > 0:
yield cirq.CNOT(input_qubits[significant], output_qubits[j])
# Apply a random permutation:
pos = [
0,
len(secret_string) - 1,
]  # Swap some qubits to define oracle. We choose first and last:
yield cirq.SWAP(output_qubits[pos[0]], output_qubits[pos[1]])


## 1 Answer

Assuming $$x$$ is $$n$$ bits, here's a simple procedure: take $$n$$ ancilla qubits, all prepared in $$|0\rangle$$. Do a transversal controlled-not (i.e. bit by bit controlled-not) from the register with $$|x\rangle$$ to the ancilla register. THis means that if you started wuth $$\sum_xa_x|x\rangle,$$ you now have $$\sum_xa_x|x\rangle|x\rangle.$$

Next, find a bit of $$a$$ which is 1. Let's say this is bit $$b$$. Do a controlled-not from qubit b of the original register, targeting all the qubits $$q$$ of the second register for which $$a_q=1$$. This means that for all $$x$$ such that $$x_b=0$$, the second register is still $$x$$, while if $$x_b=1$$, the second register has become $$x\oplus a$$. In particular, the $$b^{th}$$ qubit of the ancilla register must be 0, and that qubit can be dropped.

• What are $a_x$ and $a_q$? The x-th and q-th bit of the period string? Jan 19 '21 at 8:20
• Yes, that's right. Jan 19 '21 at 12:09
• i noticed that the Cirq code I posted above, after doing the same steps as you did, also swaps some qubits, is that necessary? Feb 11 '21 at 9:40
• I'm not particularly familiar with cirq. But does it use a different convention for ordering of the tensor product? That might explain it? Feb 11 '21 at 9:56
• Ah, no, sorry. That's just for the purpose of implementing a different f. I've implemented a specific one, but it's also kind of trivial (and possibly if you already knew the specific form or f, there's a faster classical algorithm to solve it). So adding the permutation from a random set 'hides' that structure a bit more Feb 11 '21 at 10:34