Suppose there are $n$ unknown unit vectors in $\mathbb{R}^d$, $V=\{v_1,\ldots,v_n\}$, no two identical. Your task is to determine the vectors in $V$. The only tool at your disposal is to query a particular vector $v_i$ and learn what is its dot product with your query vector $v$, which $v$ is your choice. So your query will return $v \cdot v_i$.

My question is:

. What is the best strategy to uniquely determine $V$, where "best" is the fewest number of queries, almost surely, as a function of $n$ and $d$?Q

"Almost surely" is to avoid choosing a query vector identical to one of the unknown vectors.

*Example*. $n=3$, $d=2$. Let the unknown vector be $V=\{v_1,v_2,v_3\}$ with \begin{eqnarray} v_1 & = & (1,0) \\ v_2 & = & (0,1) \\ v_3 & = & \left( \frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right) \end{eqnarray} $v_3$ is $(1,1)$ normalized to unit length. Let's say we choose just one $v=(-1/2,1)$ normalized as our query vector: $$ v=\left( -\frac{1}{\sqrt{5}},\frac{2}{\sqrt{5}} \right) $$

Then we could query with $v \cdot v_i$: \begin{eqnarray} v \cdot v_1 & = & -\frac{1}{\sqrt{5}} \\ v \cdot v_2 & = & \frac{2}{\sqrt{5}}\\ v \cdot v_3 & = & \sqrt{\frac{2}{5}}-\frac{1}{\sqrt{10}} \end{eqnarray} Knowing these dot products, and that $|v_1|=|v_2|=|v_3|=1$, we have $6$ unknowns and $6$ equations, and indeed the original $\{v_1,v_2,v_3\}$ constitute a solution. But only one of eight solutions, e.g.: \begin{eqnarray} v_1 & = & \left( -\frac{3}{5}, -\frac{4}{5} \right) \\ v_2 & = & \left( -\frac{4}{5}, \frac{3}{5} \right) \\ v_3 & = & \left( -\frac{7}{5 \sqrt{2}}, -\frac{1}{5 \sqrt{2}} \right) \end{eqnarray}

So which and how many additional queries are needed to pin down uniquely the unknown $V$? One may use many different query vectors, if that's advantageous; above I just used one, $v$.