2
$\begingroup$

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?

$\endgroup$

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.