Bad Qubits — Learn Quantum by Doing

Multiple choice

In Simon's problem, the oracle

f : \{0,1\}^n \to \{0,1\}^n

satisfies the promise

f(x) = f(y)

if and only if

y = x \oplus s

for a secret string

s

. When

s

is NOT the all-zeros string, what is the structure of

f

$f$ maps exactly $2^{n-1}$ inputs to $0$ and the rest to $s$
$f$ is one-to-one (injective): every input gives a distinct output
$f$ is constant: every input maps to the same single output
$f$ is two-to-one: exactly the pair $\{x, x \oplus s\}$ maps to the same output for every $x$