Talk:Simon's problem

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)Reply

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)Reply

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.

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)Reply

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)Reply

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)Reply

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)Reply

"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)Reply

"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)Reply

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)Reply

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 ${\displaystyle |011\rangle }$ or ${\displaystyle |101\rangle }$ can result in the output that occurred in this run of the algorithm, ${\displaystyle |110\rangle }$.

The input qubits that have a corresponding entry in ${\displaystyle s}$ of 0 will decohere to either ${\displaystyle |0\rangle }$ or ${\displaystyle |1\rangle }$ depending on the function. In the example, the third input qubit has decohered to ${\displaystyle |1\rangle }$ because both possible inputs have a ${\displaystyle |1\rangle }$ in the third qubit position. Conversely, input qubits that have a corresponding entry in ${\displaystyle s}$ of 1 will always decohere to ${\displaystyle |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 ${\displaystyle s}$ of 1 will always result in a measurement of 0. The input qubits that have a corresponding entry in ${\displaystyle 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 ${\displaystyle s}$ of 0 and no chance of seeing a 1 for other qubits. Gathering evidence of the measured 1 values will allow deduction of ${\displaystyle s}$, which can be trivially verified as the correct solution.

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

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 ${\displaystyle x}$ and ${\displaystyle y}$ for which ${\displaystyle f(x)=f(y)}$. There is not necessarily any structure in the function ${\displaystyle f}$ that would help you to find two such inputs—without any additional constraints on ${\displaystyle 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 ${\displaystyle \Omega ({\sqrt {2^{n}}})}$ different inputs before being likely to find a pair on which ${\displaystyle 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 ${\displaystyle x}$ and ${\displaystyle y}$ for which ${\displaystyle f(x)=f(y)}$. There is not necessarily any structure in the function ${\displaystyle f}$ that would help us to find two such inputs: more specifically, we can discover something about ${\displaystyle 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 ${\displaystyle f}$ takes the same output, as per the birthday problem. Since, classically to find ${\displaystyle s}$ with a 100% certainty it would require checking up to ${\displaystyle 2^{n-1}+1}$ inputs, Simon's problem seeks to find ${\displaystyle s}$ using fewer queries than this classical method."

- Classical Post Processing

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

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

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

${\displaystyle \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 ${\displaystyle s'\neq 0^{n}}$ and test that ${\displaystyle f(0^{n})=f(s')}$. If ${\displaystyle f(0^{n})=f(s')}$, we know that ${\displaystyle s=s'}$, and the problem has been solved. If ${\displaystyle f(0^{n})\neq f(s')}$, it must be that ${\displaystyle s=0^{n}}$ (because, if this were not so, the unique non-zero solution to the linear equations would have been ${\displaystyle 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 ${\displaystyle s=0^{n}}$, which means that ${\displaystyle f}$ is a one-to-one function."

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

- Similar Equations. Lot's of similar stuff.

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

- Similar variable characters are chosen (e.g. ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle 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)Reply

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

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

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)Reply

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)Reply

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)Reply

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)Reply

I had some trouble parsing the problem description as it is currently written. Simon's original description of the problem seems much clearer to me:

Suppose we are given a function ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m}}$, with ${\displaystyle m\geq n}$, and we are promised that either ${\displaystyle f}$ is 1-to-1, or there exists a non-trivial ${\displaystyle s}$ such that ${\displaystyle \forall x\neq x',\;f(x)=f(x')\iff x'=x\oplus s}$, where ${\displaystyle \oplus }$ denotes bitwise exclusive-or. We wish to determine which of these conditions holds for ${\displaystyle f}$, and, in the second case, to find ${\displaystyle s}$.

A possible rewriting of the section would be as follows:

Simon's problem considers access to a function ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m}}$, ${\displaystyle m\geq n}$, as implemented by a black box or an oracle. This function is promised to be either a one-to-one function, or a two-to-one function; if ${\displaystyle f}$ is two-to-one, it is furthermore promised that two inputs ${\displaystyle x}$ and ${\displaystyle x'}$ evaluate to the same value if and only if ${\displaystyle x}$ and ${\displaystyle x'}$ differ in a fixed set of bits. I.e., if ${\displaystyle f}$ is not one-to-one, it is promised that there exists a non-zero ${\displaystyle s}$ such that, for all ${\displaystyle x\neq x'}$, ${\displaystyle f(x)=f(x')}$ if and only if ${\displaystyle x'=x\oplus s}$, where ${\displaystyle \oplus }$ denotes bitwise exclusive-or. Simon's problem asks, in its decision version, whether ${\displaystyle f}$ is one-to-one or two-to-one. In its non-decision version, Simon's problem asks whether ${\displaystyle f}$ is one-to-one or what is the value of ${\displaystyle s}$ (as defined above). The goal is to solve this task with the least number of queries (evaluations) of ${\displaystyle f}$.

Note that the promise on ${\displaystyle f}$ if ${\displaystyle f}$ is two-to-one implies that it is, in this case, a periodic function:

$${\displaystyle f(x)=f(y)=f(x\oplus s).}$$

Miguelmurca (talk) 16:34, 15 January 2025 (UTC)Reply

With some modification, the rewriting above contains all of the information in the current version of the article. I'll update the article to use the rewrite. Feel free to revert the change if you feel appropriate. Miguelmurca (talk) 16:52, 15 January 2025 (UTC)Reply

I've reverted a modification of the 2nd formulation of Simon's problem, which now reads (again):

Given black-box or oracle access to ${\displaystyle f}$, promised to satisfy, for some ${\displaystyle s}$ and all ${\displaystyle x\neq x'}$, ${\displaystyle f(x)=f(x')}$ if and only if ${\displaystyle x'=x\oplus s}$, determine whether ${\displaystyle s\neq 0}$ (decision version), or output ${\displaystyle s}$ (non-decision version).

I think one needs to make that statement for all ${\displaystyle x\neq x'}$ (and not all ${\displaystyle x,x'}$) since it always holds that ${\displaystyle f(x)=f(x')}$ for ${\displaystyle x=x'}$ and so the if-and-only-if statement holds for two-to-one functions only if we talk about ${\displaystyle x\neq x'}$. --Qcomp (talk) 19:26, 15 January 2025 (UTC)Reply

Ah, that's right. But this is subtle, as the condition becomes trivially false when ${\displaystyle s=0}$, and it is from that (plus your observation) that you get that ${\displaystyle f}$ must be one-to-one. (Am I thinking correctly?)

Is it worth it to elaborate a little why the second formulation works for ${\displaystyle s=0}$ and ${\displaystyle s\neq 0}$? Miguelmurca (talk) 21:41, 15 January 2025 (UTC)Reply

I rephrased the 2nd phrasing (again). It should be clearer now that the question can be reduced to a question about ${\displaystyle s}$. Miguelmurca (talk) 14:52, 16 January 2025 (UTC)Reply

I was just writing a reply; I think your new formulation works and avoids both the problems with the reverted one and with the one I reverted t. Thanks. --Qcomp (talk) 14:56, 16 January 2025 (UTC)Reply

I'm reverting the addition of a Qiskit section, since it restates much of the discussion of the rest of the article, and there is almost no benefit to providing explicit code. (There is arguably little benefit in providing any code, since the point of Simon's problem is to establish a separation.) A quantum circuit is already provided in the Simon's algorithm section, with a detailed discussion on how the algorithm works, and there are also various explicit examples with a few qubits in the article.

Note that an extremely similar Qiskit section was added by the same user to the Deutsch-Jozsa page, and had also been added to Bernstein-Vazirani algorithm page, where there was prior discussion against having such a section. Miguel M. (talk) 15:42, 18 February 2025 (UTC)Reply

Thanks. I made modifications that I trust are acceptable. JavaFXpert (talk) 19:44, 20 February 2025 (UTC)Reply