Talk:Simon's problem

Wiki Education Foundation-supported course assignment

This article was the subject of a Wiki Education Foundation-supported course assignment, between 20 August 2020 and 23 November 2020. Further details are available on the course page. Student editor(s): Calhin, CtFrck. Peer reviewers: Afk2231, Aflemingclt.

Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT (talk) 09:22, 17 January 2022 (UTC)

Not an encyclopic entry

This article requires a complete rewrite to make it accessible to a non specialist reader. As it stands it is totally opaque to anyone without mathematical training. Is there anyone who has a knowledge of the subject that they wish to share with a general readership who would be prepared to do such a rewrite? LuciusAeliusSejanus (talk) 16:04, 30 September 2017 (UTC)

Making it clear that measurement does not cause interference

I was new to quantum computing before reading this, and it took me some time to see that the interference happens before the measurement, and is not caused by it. I've edited the article to reflect that. The previous version has the advantage that it was shorter. I have nothing against reverting the edit.

Circuit diagram

I'm pretty new at this so I could be wrong, but for Simon's algorithm shouldn't the second register be initialized to 0? Emma Strubell (talk) 21:21, 10 January 2011 (UTC)

I'm also pretty sure that the hadamard on the lower register shouldn't be there. — Preceding unsigned comment added by 132.68.40.79 (talk) 10:50, 12 June 2011 (UTC)

Proposed move: Simon's algorithm -> Simon's problem

I think the article should be named after the problem instead of the algorithm. The problem was invented to show a separation and didn't exist before. (Unlike, say, Shor's algorithm for factorization or Grover's algorithm for the search problem.) --Robin (talk) 23:28, 16 October 2012 (UTC)

Makes sense to me. Would make it a better place to mention the deterministic solution as well. Skippydo (talk) 03:22, 17 October 2012 (UTC)

Measuring the registers

"We perform a simultaneous measurement of both registers". Why not only measure the first register? 132.65.249.52 (talk) 11:55, 20 July 2015 (UTC)

Sentence is wrong as is

"Although the problem itself is of little practical value, it can be proved that a quantum algorithm can solve this problem exponentially faster than any classical algorithm."

This is not true. Simon's algorithm is in fact exponentially faster than any KNOWN classical algorithm, but there is no proof that there isn't a classical algorithm that runs as fast as Simon's algorithm. I propose changing the above sentence to:

"Although the problem itself is of little practical value, it can be proved that a quantum algorithm can solve this problem exponentially faster than any known classical algorithm." — Preceding unsigned comment added by 2001:690:2100:1D:9D1A:499:D1C2:3FEE (talk) 13:12, 31 August 2018 (UTC)

Inspiration for Shor's algorithm

The claim that Simon's algorithm is the inspiration for Shor's algorithm is supported by this reliable source: "In 1994, inspired by Simon's algorithm, Peter Shor found a bounded probability polynomial-time quantum algorithm for factoring integers." Rieffel and Polak, Quantum Computing: A Gentle Introduction (2011) p. 163. Mgnbar (talk) 19:32, 8 May 2020 (UTC)

Intuition at the end of the overview

At the end of the overview section I'd like to consider adding some text to aid intuition of how the algorithm works. Using the example function described in the overview section, we might expect to see this possible outcome if we measure the output qubits:

Although it's not necessary to measure the output qubits, the correlations between the input qubits after the oracle has interacted with them contains everything required, it's helpful to focus on a single, narrow example where the output qubits have decohered or been measured.

In this example, inputs of either $|011\rangle$ or $|101\rangle$ can result in the output that occurred in this run of the algorithm, $|110\rangle$.

The input qubits that have a corresponding entry in $s$ of 0 will decohere to either $|0\rangle$ or $|1\rangle$ depending on the function. In the example, the third input qubit has decohered to $|1\rangle$ because both possible inputs have a $|1\rangle$ in the third qubit position. Conversely, input qubits that have a corresponding entry in $s$ of 1 will always decohere to $|0\rangle +|1\rangle$ because the two possible inputs have different values. In the example, this applies to the first and second input qubits.

The inputs are now passed through hadamard gates:

And then measured:

The input qubits that have a corresponding entry in $s$ of 1 will always result in a measurement of 0. The input qubits that have a corresponding entry in $s$ of 0 will measure 50/50 as 0 or 1. Notice that this is the only possibility of measuring 1. Repeating the algorithm many times for the same function provides an exponentially increasing chance of seeing a 1 measured for qubits that have a corresponding entry in $s$ of 0 and no chance of seeing a 1 for other qubits. Gathering evidence of the measured 1 values will allow deduction of $s$, which can be trivially verified as the correct solution.

DavidBoden (talk) 23:26, 7 November 2021 (UTC)

Plagiarism

A large portion of the algorithm section is a plagiarism of Watrous' lecture notes.

- Problem Hardness

From Watrous' notes: "Intuitively this is a very hard problem classically, even if one uses randomness and accepts a small probability of error. We will not go through the proof of this fact, because (like many lower-bound proofs) it is harder than one might expect and I prefer that our focus remain on the quantum algorithmic aspects of this problem. However, the intuition 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 you to find two such inputs—without any additional constraints on $f$ you are as likely to find two such inputs by randomly guessing them as you would using any other method. But you would need to guess $\Omega ({\sqrt {2^{n}}})$ different inputs before being likely to find a pair on which $f$ takes the same output."

From the page: "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 $\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."

- Classical Post Processing

From Watrous' notes: "You will only get a unique non-zero solution $s$ if you are lucky and $y_{1},...,y_{n-1}$ are linearly independent. The probability that $y_{1},...,y_{n-1}$ are linearly independent is at least

$\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788...>{\frac {1}{4}}$

If you have linear independence, solve the system to get a candidate solution $s'\neq 0^{n}$, and test that $f(0^{n})=f(s')$. If $f(0^{n})=f(s')$, you know that $s=s'$ and the problem has been solved. If $f(0^{n})\neq f(s')$, it must be the case that $s=0^{n}$ (because if this were not so, the unique nonzero solution to the linear equations would have been $s$). Either way, once you have linear independence, you can solve the problem."

From the page: "We only get a unique non-zero solution $s$ if we are "lucky" and $y_{1},y_{2},...,y_{n-1}\in \{0,1\}^{n}$ are linearly independent. The probability that are linearly independent is at least

$\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788...>{\frac {1}{4}}$

If we have linear independence, we can solve the system to get a candidate solution $s'\neq 0^{n}$ and test that $f(0^{n})=f(s')$. If $f(0^{n})=f(s')$, we know that $s=s'$, and the problem has been solved. If $f(0^{n})\neq f(s')$, it must be that $s=0^{n}$ (because, if this were not so, the unique non-zero solution to the linear equations would have been $s$). Either way, once we have linear independence, we can solve the problem."

The rest of the classical post processing section is plagiarized too.

- First Case

From Watrous' notes: "Let us first consider the special case where $s=0^{n}$, which means that $f$ is a one-to-one function."

From the page: "Let's first analyze the (special) case $x\oplus y=0^{n}$, which means that $f$ is (by requirement) a one-to-one function"

- Similar Equations. Lot's of similar stuff.

- In the measurement section, the range of $f$ is referred to as $A$, just as it is in the lecture notes.

- Similar variable characters are chosen (e.g. $x$, $y$, $y_{1},...,y_{n-1}$

This is kind of less of a problem, since it's the actual math, but it illustrates my point.

Tapeworms27 (talk) 14:56, 15 October 2022 (UTC)

Well, I've rewritten the algorithm section, so I guess this is less of a problem. Tapeworms27 (talk) 01:39, 16 October 2022 (UTC)

Isn't there a missing equation?

$y_{1},...,y_{n-1}$ yield only $n-1$ equations, how is it enough to solve for $s$, which is of length $n$? Doobiefletzet (talk) 14:49, 15 May 2023 (UTC)

And are you asking us to solve a homework problem for you? There cannot be n independent equations. If there were n independent equations, then that would be bad for s. I hope that this helps you. Mgnbar (talk) 15:02, 15 May 2023 (UTC)

Your condescending tone is unnecessary. I didn't ask you to solve anything for me, I pointed out an error.

1. The fact there cannot be n independent equations doesn't mean n-1 equations are enough to solve for s. Therefore, the sentence "Thus, we can efficiently solve this system of equations classically to find s" is still erroneous.
2. That said, it is not true that there cannot be n independent equations. If s=0 then every vector is possible (because every vector zeroes s under direct sum), and you may indeed obtain n independent vectors, which in turn yield n independent equations. However if s is not 0, the maximum rank you can get is n-1, which is the degree of the hyperplane perpendicular to s.
3. Thus a possible algorithm is to obtain n-1 vectors, then solve not for s, but for *the two possible solutions*. One will be the trivial solution (all zeroes). The other one, call it s*, will be s if s is not zero, or a random vector otherwise. Thus, a test whether f(0)=f(s*) will deterministically decide between the two cases.
4. Alternatively, you may sample more than n vectors (O(n) is enough), and then check their degree. if s is not 0 it will be less than n with probability 1, and if s is zero it will be n with high probability.
5. Read the original paper. Page 7.

Doobiefletzet (talk) 09:57, 16 May 2023 (UTC)

In the formulation, with which I'm most familiar, s cannot be 0...0. Therefore there cannot be n independent equations. That's why I responded, how I did. However, you are right that, in the article's formulation, it is possible that s is 0...0. Sorry. I should have re-read the article. Now your question makes sense. I agree with your most recent post.

However, as you have explained, you can stop once you have n - 1 independent equations, and then do a small check to finish the problem. Perhaps this is why people gloss over the s = 0...0 case. Certainly the algorithm can't have a step where it gathers n independent equations, because this step might not terminate. (Moreover, if we regard calls to the quantum subroutine as expensive, then you would never make more calls than you had to.)

In your view, does the article need to be edited, to clarify this point? Mgnbar (talk) 10:19, 16 May 2023 (UTC)

Thanks. I believe it should be edited. It certainly confused me... Something along the lines of item 3 in my reply above should suffice. Doobiefletzet (talk) 10:37, 16 May 2023 (UTC)