Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices of $J_F$ and $J_g$. Let $(F, G)$ be a vertex of the product of the Johnsons graphs. Two vertices in the graph product are conected if: $F$ is adjacent with $F'$ and if $G$ is adjacent with $G'$.

On page 5 the superposition created in order to apply Szegedy's framework is described as: $|\psi_0\rangle = \frac{1}{\sqrt{\binom{N}{l}\binom{M}{l}l (N-l) m(M-m)}} \otimes |F, G, L_{F, G} \rangle | F', G', L_{F', G'} \rangle$

Taken the nominator of the Amplitude: That would be all possibilities to connect any two vertices in the graph $J_f \times J_g$. The algorithm processes connected vertices in each ''step''.

Question: Is the above assumption of the nominator coorect? If so, why is it not sufficient to create a superposition over all connected vertices in the graph $J_f \times J_g$?

I do see that on a quantum level the ''few more connected vertices'' do not have much of an impact on the running time, but does it have some kind of impact on the algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.