User:CtFrck/Simon's problem

From Wikipedia, the free encyclopedia

Not to be confused with the Simon problems in mathematical physics.

In the computational complexity theory and quantum computing, Simon's problem is a computational problem that can be solved exponentially faster on a quantum computer than on a classical (or traditional) computer. Simon's problem incorporates the use of a black box. Black box problems give quantum algorithms advantage over classical algorithms.

The problem itself is of little practical value because there are little imaginable realistic settings that would require solving Simon's Problem. However, the problem is still important because it can be proved that a quantum algorithm can solve this problem exponentially faster than any known classical algorithm. This is the first example of a quantum computational problem that can be solved at a polynomial time on a quantum computer.

The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm, usually called Simon's algorithm, that solves the problem exponentially faster than any deterministic or probabilistic classical algorithm, requiring exponentially less computation time (or more precisely, queries) than the best classical probabilistic algorithm. In Simon's algorithm a linear number of queries are needed for the quantum algorithm rather than an exponential number of queries that are needed for the classical probabilistic algorithm. This problem yields an oracle separation between the complexity classes BPP and BQP, unlike the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. The separation is exponential (relative to an oracle) between quantum and bounded error classical query complexity. Simon's problem does not prove $BPP\neq BQP$, rather demonstrates that there exists an oracle relative to which ${\displaystyle BPP\neq BQP}$. The oracle used in Simon's Problem is the black box we consider when computing.

Simon's algorithm was also the inspiration for Shor's algorithm. Both problems are special cases of the Abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

Contents

• 1 Problem description
  • 1.1 Example
  • 1.2 Problem hardness
• 2 Overview of Simon's algorithm
  • 2.1 Idea
  • 2.2 Simon's quantum circuit
• 3 Simon's algorithm
  • 3.1Input
    • 3.1.1 Example
  • 3.2 First Hadamard transformation
    • 3.2.1 Example
  • 3.3 Oracle
  • 3.4 Second Hadamard transformation
  • 3.5 Measurement
    • 3.5.1First case
    • 3.5.2 Second case
      • 3.5.2.1Odd number
      • 3.5.2.2 Even number
  • 3.6 Classical post-processing
• 4 Complexity
• 5 See also
• 6 References

Problem Description

Given a function input (implemented by a black box or oracle) $f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}$ , from n bit strings to n bit strings, promised to satisfy the property that, for some nonzero $s\in \{0,1\}^{n}$  and all ${\displaystyle x,y\in \{0,1\}^{n}}$,

$f(x)=f(y)$ if and only if

$x=y\otimes s$ or

${\displaystyle x\oplus y\in \{0^{n},s\}}$

The goal is to identify s and identify whether $s=0^{n}$ or $s\neq 0^{n}$ by querying f(x).

Here, $s=0^{n}$ classifies a one-to-one function.

If $s\neq 0^{n}$ , the function is a two-to-one function such that

${\displaystyle x\oplus y\in \{0^{n},s\}}$

So, in other words, f is a function such that ${\displaystyle f(x)=f(x\oplus s)},$ for all  ${\displaystyle x\in \{0,1\}^{n}}$ where  $s\in \{0,1\}^{n}$ is unknown.

The problem is to find s that satisfies the equation.

Goal

It is important to remember that the goal of Simon's Problem is to reduce the number of queries to the black box so that we can determine s exponentially fast.

Example[edit]

For example, if $n=3$ , then the following function is an example of a function that satisfies the required and just mentioned property:

000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

In this case, $s=110$ (i.e. the solution). It can easily be verified that every output of  f occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to $s=110$.

For example, the input strings  010 and  100 are both mapped (by f) to the same output string 000. $f(010)=000$ and $f(100)=000$. If we apply XOR to 010 and 100 we obtain 110, that is ${\displaystyle 010\oplus 100=110=s}.$

$s=110$ can also be verified using input strings 001 and 111 that are both mapped (by f) to the same output string 010. If we apply XOR to 001 and 111, we obtain 110, that is $001\oplus 111=110=s$. This gives the same solution $s=110$ we solved for before.

In this example the function f is indeed a two-to-one function where ${\displaystyle s\neq 0^{n}}$.

For a one-to-one function, $f(x)=f(y)$ such that $f(1)=1,f(2)=2,f(3)=3,etc.$

Problem Hardness[edit]

Intuitively, this is a very hard problem to solve in a "classical" way, even if one uses randomness and accepts a small probability of error. The intuition behind the hardness is reasonably simple: if you want to solve the problem classically, you need to find two different inputs $x$ and $y$ for which $f(x)=f(y)$. There is not necessarily any structure in the function $f$ that would help us to find two such inputs: more specifically, we can discover something about $f$ (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess ${\displaystyle \Omega ({\sqrt {2^{n}}})}$ different inputs before being likely to find a pair on which $f$ takes the same output, as per the birthday problem. Since, classically to find s with a 100% certainty it would require checking up to $2^{n-1}+1$ inputs, Simon's problem seeks to find s using fewer queries than this classical method.

Overview of Simon's algorithm[edit]

Idea[edit]

The high-level idea behind Simon's algorithm is to "probe" (or "sample") a quantum circuit (see the picture below) "enough times" to find  (n-1) linearly independent) n-bit strings, that is

${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n},}$

such that the following equations are satisfied

${\displaystyle \left\{{\begin{aligned}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\,\,\,\vdots \\y_{n-1}\cdot s&=0\end{aligned}}\right.}$

where ${\displaystyle y_{i}\cdot s}$ is the modulo-2 dot product; that is,${\displaystyle y_{i}\cdot s=y_{i1}s_{1}\oplus y_{i2}s_{2}\oplus \dots \oplus y_{in}s_{n}}$ , and ${\displaystyle y_{ij},s_{j}\in \{0,1\}}$, for ${\displaystyle i=1,\dots ,n-1}$ and for ${\displaystyle j=1,\dots ,n}.$

So, this linear system contains $n-1$ linear equations in $n$ unknowns (i.e. the bits of ${\displaystyle s\in \{0,1\}^{n}}$), and the goal is to solve it to obtain $s$ , and $s$ is fixed for a given function $f$ . There is not always a (unique) solution.

Simon's quantum circuit[edit]

The quantum circuit (see the picture) is the implementation (and visualization) of the quantum part of Simon's algorithm.

A quantum state of all zeros is first prepared (this can easily be done).

The state $|0\rangle$ represents $|0^{n}\rangle$ where $n$ is the number of qubits.

Half of this state is then transformed using a Hadamard transform to create a superposition state.

The result is then fed into an oracle (or "black box"), which knows how to compute $f$. Where ${\displaystyle U_{f}}$ acts on the two registers as ${\displaystyle |x\rangle |0^{n}\rangle \rightarrow |x\rangle |f(x)\rangle }{\displaystyle |x\rangle |0^{n}\rangle \rightarrow |x\rangle |f(x)\rangle }$.

After that, part of the output produced by the oracle is transformed using another Hadamard transform to result in a state.

Finally, a measurement on the overall resulting quantum state is performed.

It is during this measurement that we retrieve the n-bit strings,${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$ , mentioned in the previous sub-section.

Simon's algorithm can be thought of as an iterative algorithm (which makes use of a quantum circuit) followed by a (possibly) classical algorithm to find the solution to a linear system of equations.

Simon's algorithm[edit]

In this section, each part of Simon's algorithm is explained (in detail). It may be useful to look at the picture of Simon's quantum circuit above while reading each of the following sub-sections.

Input[edit]

Simon's algorithm starts with the input ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle =|0^{n}\rangle |0^{n}\rangle }$, where ${\displaystyle |0^{n}\rangle }$ is the quantum state with $n$ zeros.

(The symbol $\otimes$ is the typical symbol used to represent the tensor product. To not clutter the notation, the symbol  is sometimes omitted: for example, in the previous sentence, ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle }$ is equivalent to ${\displaystyle |0^{n}\rangle |0^{n}\rangle }$. In this article, it is (often) used to remove ambiguity or to avoid confusion.)

Example[edit]

So, for example, if $n=2$, then the initial input is

${\displaystyle |0^{2}\rangle \otimes |0^{2}\rangle =|00\rangle \otimes |00\rangle =(|0\rangle \otimes |0\rangle )\otimes (|0\rangle \otimes |0\rangle )=|0\rangle \otimes |0\rangle \otimes |0\rangle \otimes |0\rangle =|0000\rangle =|0^{4}\rangle =|0^{2n}\rangle }$.

First Hadamard transformation[edit]

After that, the input (as described in the previous sub-section) is transformed using a Hadamard transform. Specifically, the Hadamard transform  (the tensor product can also be applied to matrices) is applied to the first  qubits, that is, to the "partial" state , so that the composite state after this operation is

where  denotes any n-bit string (i.e. the summation is over any n-bit string). The term  can be factored out of the summation because it does not depend on  (i.e. it is a constant with respect to ), and .

Example[edit]

Suppose (again) , then the input is  and the Hadamard transform  is

If we now apply  to the first , i.e. to the state

we obtain

To obtain the final composite quantum state, we can now tensor product  with , that is

Oracle[edit]

We then call the oracle or black-box ( in the picture above) to compute the function  on the transformed input , to obtain the state

Second Hadamard transformation[edit]

We then apply the Hadamard transform  to the states of the first  qubits of the state , to obtain

where  can either be  or , depending on , where , for . So, for example, if  and , then , which is an even number. Thus, in this case, , and  is always a non-negative number.

Intuition behind this inverse Hadamard transformation that is applied here can be found on CMUs lecture notes

Let's now rewrite

as follows

This manipulation will be convenient to understand the explanations in the next sections. The order of the summations has been reversed.

Measurement[edit]

After having performed all previously described operations, at the end of the circuit, a measurement is performed.

There are now two possible cases we need to consider separately

• or
• , where .

First case[edit]

Let's first analyze the (special) case , which means that  is (by requirement) a one-to-one function (as explained above in the "problem description").

Let's keep in mind that the quantum state before the measurement is

Now, the probability that the measurement results in each string  is

This follows from

because the two vectors only differ in the ordering of their entries, given that  is one-to-one.

The value of the right-hand side, that is

is more easily seen to be .

Thus, when , the outcome is simply a uniformly distributed -bit string.

Second case[edit]

Let's now analyze the case , where . In this case,  is a two-to-one function, that is, there are two inputs that map to the same output of .

The analysis performed in the first case is still valid for this second case, that is, the probability to measure any given string  can still be represented as

However, in this second case, we still need to figure out what this value of  is. Let's see why in the following explanations.

Let , the image of . Let  (i.e.  is some output of the function ), then for every , there is one (and only one) , such that ; moreover, we also have , which is equivalent to  (see "the problem description" section above for a review of this concept).

Hence, we have

Given that , then we can rewrite the coefficient  as follows

Given that , then we can further write the expression above as

So,  can further be written as

Odd number[edit]

Now, if  is an odd number, then . In that case,

Consequently, we have

Given that , then we never have this case, that is, no string  is seen (after the measurement) in this case.

(This is the case where we have destructive interference.)

Even number[edit]

If, instead,  is an even number (e.g. zero), then . In that case,

So, we have

Is the case of constructive interference,

. So, in summary, for this second case, we have the following probabilities

Classical post-processing[edit]

When we run the circuit (operations) above, there are two cases:

• in the (special) case where , the measurement results in each string  with probability

• in the case  (where ), the probability to obtain each string  is given by

Thus, in both cases, the measurement results in some string  that satisfies , and the distribution is uniform over all of the strings that satisfy this constraint.

Is this enough information to determine ? The answer is "yes", provided that the process (above) is repeated several times (and a small probability of failure is accepted). Specifically, if the above process is run  times, we get  strings , such that

This is a system of  linear equations in  unknowns (i.e. the bits of ), and the goal is to solve it to obtain . Note that each of the  that we obtain after each measurement (for each "round" of the process) is, of course, the result of a measurement, so it is known (at the end of each "round").

We only get a unique non-zero solution  if we are "lucky" and  are linearly independent. The probability that  are linearly independent is at least

If we have linear independence, we can solve the system to get a candidate solution  and test that . If , we know that , and the problem has been solved. If , it must be that  (because, if this were not so, the unique non-zero solution to the linear equations would have been ). Either way, once we have linear independence, we can solve the problem.

Complexity[edit]

Simon's algorithm requires  queries to the black box, whereas a classical algorithm would need at least  queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires  queries.

Classically, one would send a bit string input into the query to find the output, and repeat this process to solve Simon's problem. For a randomized classical algorithm, the optimal query to solve is a minimum of O(2^n/2) to have a good probability.

On the quantum end, we claim there exists a quantum algorithm that requires O(n) queries to solve Simon's problem, proved by Simon's algorithm. This provides an extensive improvement in efficiency as compared to the classical attempt.

Peer Review (Anthony Fleming)

You've done an excellent job explaining Simon's Problem in a way that is approachable. I like that you begin with a conceptual overview, then show the math and provide examples. However, the later sections are not well formatted and have little to no citations. The citations are also not formatted properly (you need more than just the link), and you don't need to include a table of contents because Wikipedia adds that automatically.

Peer Review (Alex King)

The best part of your edits seem to be the introduction, as it clearly explains the problem and it's implications. There are some problems with the edited project descriptions, as I feel like the problem is poorly defined. For instance, you introduce what the goal of the algorithm is, but then you go on to describe it in more detail before restating the problem. If there's one thing I would change it would be to state the goal of the algorithm once after setting the background for the problem. Another thing is that you've continued to use some of the article's awkward language when it comes to logic gates. For example, "we XOR 100 and 110" is much less understandable than, lets say, "we apply XOR to 100 and 110." Make sure that when you use a word from the article that it can be readily read off and understood from someone who might not understand the terminology and jargon. Otherwise, this is a good addition to the article.