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

$$ \newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\newcommand{\proj}[1]{\left|#1\right\rangle\left\langle#1\right|} $$ Much of the functionality here is the same as the Bernstien-Vazirani algorithm, if that helps....


4

It is always good to start from considering an example. Suppose you have CNOT gate; then \begin{align} \Ket{0}\Ket{0} \rightarrow \Ket{0}\Ket{0}\\ \Ket{1}\Ket{0} \rightarrow \Ket{1}\Ket{1} \end{align} By linearity \begin{align} \frac{1}{\sqrt{2}}(\Ket{0}\Ket{0} + \Ket{1}\Ket{0}) \rightarrow \frac{1}{\sqrt{2}}(\Ket{0}\Ket{0}+ \Ket{1}\Ket{1}) \end{align} or \...


4

Imagine for a moment that $y_1,\ldots,y_{n-1}$ are linearly independent vectors in $\mathbb{R}^n$. There would then be a one-dimension subspace of vectors $s$ satisfying the $n-1$ equations you listed. The situation is the same here, except that the field of real numbers is replaced by the finite field $\mathbb{F}_2$ with elements 0 and 1. The same linear ...


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


3

At first glance, the formula looks lightly wrong: the last term in the should only be $(1-2^{n-2}/N(s))$, giving $$ P_{ind}=\prod_{k=1}^{n-1}\left(1-\frac{2^{k-1}}{N(s)}\right) $$ overall. Thus every term is a half, or larger. My reasoning is as follows: you perform a measurement and get a random outcome. The first time you do this, it can be any outcome ...


2

In order to represent a '$\mathbf 0$' state as a vector in a Hilbert space, the '$\mathbf 0$' vector must in fact be non-zero. Thus, the label '$\mathbf 0$' is just a label for some designated vector (of norm 1) in our computational basis. This is obviously an abuse of notation, but it is a fairly common one. The more usual (and less confusing) notation ...


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

Yes. The tensor product of two linear maps $S: V \to X$ and $T: W \to Y$ is the linear map $$S \otimes T: V \otimes W \to X \otimes Y \ni (v \otimes w) \mapsto S(v) \otimes T(w).$$


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