# Tag Info

5

To determine the classical complexity of a problem you need two things, of course: an upper bound (generally an algorithm) and a lower bound. There is an easy randomized algorithm that works with high probability given $O(2^{n/2})$ queries to the function $f$: for a suitable constant $c>0$, generate $k = c 2^{n/2}$ strings $x_1,\ldots,x_k\in\{0,1\}^n$ ...

4

To see that Simon's program is an instance of an (abelian) hidden subgroup problem, we have to identify the group $G$, the subgroup $H$, the set $X$ and the function $f : G \rightarrow X$. Note first that the set $\{ 0,1 \}^n$ of all bit vectors of length $n$ naturally comes with a group structure given by the (component-wise) XOR between bit vectors: $(x_1, ... 3 You could do something like: assume the most significant bit of$s$is 1. write a function that says "if the most significant bit of$x$is 0, return$x$. if the most significant bit of$x$is 1, return$x\oplus s$. This is easily implemented because you start by doing a transversal set of cNOT gates to copy$x$from the input register to the output ... 3 This is basically the definition of the type of function that you apply Simon's algorithm to. You are required to have a function$f(x)$such that $$f(x)=f(y)$$ if and only if$x\oplus y=0$or$s$. Hence, if$s$is all zeros, the outcomes are all unique: if$f(x)=f(y)$then$x=y\oplus 000\ldots 0$, but bitwise addition modulo with 0 doesn't change the bit ... 2 Sources on quantum computing tend to give a classical complexity of$\sqrt{2^n}$but not the proof. I believe the sources on classical cryptography call this algorithm birthday attack and use it to find collisions of hash functions (which is effectively what the Simon's algorithm does). You should be able to find the math details looking for it in crypto ... 2 The first state in your question is not a valid quantum state as it is not normalized. The result comes directly from the axioms of quantum mechanics. You just have to apply the Born rule. For a state$\sum_y ~ a_y |y\rangle$the probability of measuring$|y\rangle$is$|a_y|^2.$Now suppose you are given a state$\sum_y ~ a_y |y\rangle|0\rangle + b_y |y\...

1

In the first state you write they omitted to write the normalization factor. This is not rare to see, as one can usually easily deduce what the normalization should be from the context (though it might not be a very pedagogical choice). To deduce the correct normalization in this case, you need only notice that, because $f$ is one-to-one, the sum over $x$ ...

1

Here's a partial explanation. Start by thinking about the 2 bit case. We first evaluate $f(00)$, and we learn nothing. Then, we evaluate (say) $f(01)$. Now we can compare the values, and see if $s=01$, or not. Next we calculate a new value, say $f(10)$. By comparing to $f(00)$, we can determine if $s=10$ but, also, by comparing to $f(01)$, we simultaneously ...

Only top voted, non community-wiki answers of a minimum length are eligible