Can I in $\tilde{O}(r)$ number of gates (single and double qubit) create a uniform superposition of vertices of Johnson Graph $J(n,r)$? I would like to create a state $|\psi\rangle = \frac{1}{\sqrt{n \choose r}} \sum_{|S|=r, S \subset [n]}|S\rangle$ where $S$ denotes an $r$-sized tuple of indices in ascending order of their value.

  • $\begingroup$ What does this question have to do with the Johnson graph? Why isn't this simply "how do I create a an n qubit state that is an equally weighted superposition of all weight r basis vectors?" I'm not understanding how $J(n,r)$ influences the state $|\psi\rangle$. $\endgroup$
    – DaftWullie
    Aug 26, 2022 at 6:53
  • $\begingroup$ Each subset $S$ is a vertex in the Johnson graph, so the state $\vert\psi\rangle$ is really a uniform superposition of vertices in that Johnson graph. Arguably the question can be detached from the graph context (since it doesn't involve any edges) but this is the first step in so many quantum random walk algorithms that the context matters. $\endgroup$
    – Sam Jaques
    Aug 26, 2022 at 14:36

1 Answer 1


One can create this uniform superposition of vertices of Johnson graph $J(n,r)$ for any $r=n^b$ with $0<b<1$ in $\tilde{O}(r)$ gates using the gate construction mentioned in András Gilyén's Master's thesis https://web.cs.elte.hu/blobs/diplomamunkak/msc_mat/2014/gilyen_andras_pal.pdf


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.