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$
$\endgroup$
2
-
$\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$– DaftWullieCommented 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 JaquesCommented Aug 26, 2022 at 14:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
