8

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?

Nat
  • 1,507
  • 1
  • 14
  • 27
BlackHat18
  • 1,527
  • 9
  • 22

1 Answers1

5

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.

John Watrous
  • 6,342
  • 18
  • 28