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 = [
    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 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.

  • $\begingroup$ What are $a_x$ and $a_q$? The x-th and q-th bit of the period string? $\endgroup$
    – Lorenzo B.
    Commented Jan 19, 2021 at 8:20
  • $\begingroup$ Yes, that's right. $\endgroup$
    – DaftWullie
    Commented Jan 19, 2021 at 12:09
  • $\begingroup$ i noticed that the Cirq code I posted above, after doing the same steps as you did, also swaps some qubits, is that necessary? $\endgroup$
    – Lorenzo B.
    Commented Feb 11, 2021 at 9:40
  • $\begingroup$ I'm not particularly familiar with cirq. But does it use a different convention for ordering of the tensor product? That might explain it? $\endgroup$
    – DaftWullie
    Commented Feb 11, 2021 at 9:56
  • 1
    $\begingroup$ 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 $\endgroup$
    – DaftWullie
    Commented Feb 11, 2021 at 10:34

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.