During the classical pre-processing stage of Simon's algorithm, we repeat the quantum operations $n-1$ times to get

$$ \begin{alignat}{7} y_{1} \cdot s & \phantom{\vdots} =~ && 0 \\ y_{2} \cdot s & \phantom{\vdots}=~ && 0 \\ & \phantom{=} \vdots \\ y_{n-1} \cdot s & \phantom{\vdots}=~ && 0 ~, \end{alignat} $$

where $s$ is the period while $y_{i}$ are the linearly independent measurement outcomes of the quantum process. But, shouldn't we be requiring $n$ equations to get the value of $s$ as it is an unknown with $n$ variables? I wonder if this is because a system of $n$ equations will admit only the trivial solution of all $0$s. Is there a mathematical reasoning to elucidate this? How exactly would we uniquely solve for $n$ variables with $n-1$ equations?

up vote 4 down vote accepted

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 algebra as in the real number case works in this case, and we again obtain a one-dimensional subspace of possible solutions $s$. This time, however, because there are only two elements of $\mathbb{F}_2$, this one-dimensional subspace includes only two elements: the all-zero vector and some nonzero vector $s$. Naturally we disregard the all-zero vector and take the nonzero vector $s$ as our solution.

Note also that if you did add another equation, $y_n\cdot s = 0$ for some $y_n$, then $y_n$ would have to be a linear combination of $y_1,\ldots,y_{n-1}$, for otherwise the only solution would be $s = (0,\ldots,0)$. So, you would not obtain any additional information about $s$ by adding an additional equation.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.