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

Question

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]])

Answer 1

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.