I am looking at the Ambainis et al. method of verifying whether $AB = C$ in $O(n^{7/4})$ queries, as described in Buhrman and Špalek. They have the following sentence:

verify the matrix-vector product $Ay=z$ by a Grover search.

What, exactly, does this refer to?

Presumably, we would like to find--if they exist--any "marked elements", where an element in $z$ is marked if it does not equal the corresponding element in $Ay$. However, we do not a priori know the labels of the marked elements, which, as far as I know, Grover search requires (even as quantum walk algorithms do not). So, how does Grover's search help us in this case?


1 Answer 1


I'm mostly guessing, but I think it goes like this:

We do a Grover search over row indices $i$. For the Grover oracle, on input $i$, we compute $A_iy$ and $z_i$ (where $A_i$ is the $i$th row of $A$). This takes time $O(n)$. Then we compare $A_iy$ to $z_i$; if they are not equal, we treat that as a "success", and otherwise not.

If $Ay\neq z$, there will be some index $i$ such that $A_iy\neq z_i$, and this Grover search will find that index. Technically, since there may be many such indices, we will need to use one of several standard tricks to ensure that Grover's algorithm doesn't overshoot the result (one such trick: measure after 2 iterations, then measure after 4 iterations, then 8, etc., up to $O(\sqrt{n})$). The worst-case runtime is $O(\sqrt{n})$. If we never find such an index, we conclude that $Ay=z$.

I'm not sure what you mean by "labels" of the marked elements. It's true that, given $A$, $y$, and $z$, that we don't know a priori the value $A_iy$ (to compare to $z_i$), but we can compute that as part of the Grover search.

I think they then use a similar trick to find which block $i$ has $AB_i\neq C_i$ (if such a block exists). This only gives them time to try $O(1)$ random vectors $x$, but that should be fine: I think if $AB\neq C$, then (depending on how you sample random vectors) I think a random vector has probability at least $1/2$ that $ABx\neq Cx$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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