I am wondering if I have the Output Histogram of a Simon Circuit where the Oracle is hidden, is there a way to reverse engineer or do anything that will make me figure out S "secret"?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Yes, that's the point of the algorithm to figure out using the measurements one got!
An important information though is the size of the registers you're dealing with, or whether you only measured the first register or both.
In your case, this information can be deduced. There are three possible cases:
- The first register has 4 qubits, which means you didn't measure the second register
- The first register has 2 qubits, which means you measured both registers
It is not possible to have a first register with 3 qubits and a second one with only 1 qubit, since this would not satisfy Simon's promise. It is also not possible that the first register only has a single qubit. Indeed, the second register contains the value of $f(x)$ for some $x$. As such, it can only contain two different values, which is not the case of the results you got. Even if you ran the circuit on a noised simulator, you would have got all 16 different states with different amplitudes.
Finally, let's tackle the case where the first register has 2 qubits. No matter whether you take the first two qubits or the last two ones, every possible two qubits state is obtained. Thus, either $s=0$, or this is not your case.
We're thus left with the only possible remaining possibility: you measured only he first register, which has $4$ qubits. Now, the principle of Simon's algorithm is that each of this value is orthogonal to $s$. You thus only have to perform a Gaussian elimination on this system to recover it, as you would normally do with Simon's algorithm.
It is a bit simpler in your case since we know that both $0010$ and $0100$ are orthogonal to $s$, which means that $s$ can be written as $X00Y$. Since $1001$ is also orthogonal to $s$, it means that $X=Y$. We can check using the remaining ones that $X=Y=1$ works. As such, the value you're looking for is $s=1001$.
answered Apr 2, 2022 at 11:34
-
$\begingroup$ if we say that 1001 means that X=Y, then why can't we say because of 0110 then the two middle qubits are equal to each other? $\endgroup$– n22Apr 5, 2022 at 16:32
-
$\begingroup$ @n22 $s$ can be written as $XABY$. We know that $XABY\cdot0100=0$, which means that $X\cdot0+A\cdot1+B\cdot0+Y\cdot0=0$, which means that $A=0$. We can do the same for $0010$ which gives us $B=0$. We thus only need to figure out $X$ and $Y$ to get $s$. We know that $1001$ is orthogonal to $s$, so it means that $X\cdot 1+0\cdot0+0\cdot0+Y\cdot1=0$, which means that $X+Y=0$. Note that addition is taken modulo 2, which means that $X=Y$. Note that if you can't take $s=0110$ because this value is not orthogonal to $0010$, which you measured. $\endgroup$ Apr 5, 2022 at 17:43
-
$\begingroup$ @n22 Your reasoning is correct though: the fact that $s$ is orthogonal to $0110$ means that the two bits in the middle are equal. It's just simpler to directly get their values from $0100$ and $0010$. $\endgroup$ Apr 6, 2022 at 8:08