Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Say I have a secret of length $n$, $s = |x_{n-1}x_{n-2}...x_0 \rangle$. If I want to construct an oracle for this problem would I just insert a CNOT gate on every qubit where the secret's value is 1? And just do nothing to all of the 0 qubits?
How would I determine the asymptotic complexity of this circuit in its worst-case situation?
Yes, that is right. If you think about it, $CNOT|x\rangle |s\rangle = |x\rangle|x \oplus s \rangle \ $. Thus, giving a secret bitstring $s = s_1 s_2 \cdots s_n$ where $s_i \in \{0,1\}$, then whenever $s_i$ is non-zero ($s_i = 1$), performing a CNOT gate between the ancilla qubit and the $ith$ qubit in your input qubits (note that you have $n$ input qubits and one ancilla qubit in your circuit) is equivalent to performing $x_i \cdot s_i $.
Thus, everywhere there is a non-zero element in your secret bitstring $s = s_1 s_2 \cdots s_n $ you apply a CNOT gate between the ancilla qubit and the $ith$ input qubit. And anywhere the secret bitstring is zero, you don't do anything.
For example: Suppose your secret bitstring is $s = 0110$ then you would have the following circuit.
The worst case scenario is when your secret bitstring is non-zero every where. $s = 111\cdots 1$. In such case, you have to perform $n$ CNOT gates. But note that, on a quantum computer, not all the qubits are connected. So you can't just perform CNOT gate between any pair of qubit you pleased, you need to do some swapping.
For instance, look at the qubit layout in ibmq_16_melbourne
you can see that qubit 0 is not connected directly to qubit 13. Hence, to perform a CNOT between qubit 0 and 13, you would need to SWAP qubit 13 and 14 first, perform the CNOT, then SWAP it back... so the actual circuit running on current hardware will be longer than what you see on paper.
