Presentation of the problem :
The majority problem is equivalent to the perceptron learning. For each $$a \in \mathbb{Z}_n$$ define a function $$m_a : \mathbb{Z}_2^N \rightarrow \mathbb{Z}_2$$ :
$$m_a(x)= \begin{cases} 1 & \text{ if } wt(a-x)\leq n/2 \\0 & \text{ otherwise } \end{cases}$$
Where wt is the weight of a bit-string (number of 1).
Alternatively we can write : $$ m_a(x) = \Theta (n/2 – wt(x-a) )$$.
The problem is : determine a given an access to answers from $$m_a$$.
We saw in the presentation (link available soon) that the classical complexity was $$ O(n)$$ while the quantum complexity was $$ O(\sqrt{n})$$. In the following we show the classical bound.
The classical algorithm
For the classical case we will use a dichotomic process as in the binary chop. Here is the algorithm :
- At the first step you look the result for 0…0. If it’s 1 you take all the possible weights that could have the same result ($$2^n / 2 = 2^{n-1}$$ weights possible). If it’s 0 you take the complementary set of bits (the same number of weights if n is even).
- After that, you choose a new vector in your possible set, with the biggest Hamming distance with the previous tested bit. Then you look the result. After that step you would be able to remove another time : $$ 2^{n-1} / 2$$ remaining weights .
- … you repeat these steps n-1 times at all, in the end you have $$2^n/2^{n-1} = 2$$ possible states.
- In the end, you may have two bits that you will separate by choosing a special bit b. This bit b will depend on the two possible states and differentiate them.
- And you are done in n steps.
Example for n=3
For n=3, let’s take the example of the following target bit : w = 001.
- I first try 000. I get 1. So the possible weights are : 000 / 001 / 010 / 100
- Then I test 001. I get 1. So the remaining states are 001 / 000 ( 011 / 101 are not possible because they are not in the previous set)
- Finally I test 101. I get 1. So the only possible result is 001.