The paper Quantum Complexity of Testing Group Commutativity considers the problem of identifying if a given group is commutative. The group is given via a certain oracle and the complexity of the problem is measured by the number of quantum queries to this oracle. The paper gives an algorithm for this problem as well as an analysis of this algorithm that yields an upper bound of $O(k^{2/3} \log k)$.

I think the analysis of their algorithm can be improved to give an upper bound of $O(k^{2/3} \log^{2/3} k)$.

Their quantum algorithm uses a quantum random walk on the following graph. The vertices are $\ell$-tuples containing distinct elements from a universe of size $k$. Two vertices are adjacent if

  1. the Hamming distance between them is 1 or
  2. the Hamming distance between them is 2 and, after swapping the elements (in one of the vertices) in the two locations in which they differ, the Hamming distance between them is 0 (i.e., they are the same vertex).

For an example of the second type of edge, consider $k = \ell = 3$. Then the vertices $(1, 2, 3)$ and $(1, 3, 2)$ would be connected by such an edge.

For given natural numbers $k$, and $\ell$, let $G(k, \ell)$ denote this graph with parameters $k$ and $\ell$. The analysis in the paper shows that the absolute spectral gap of $G(k, \ell)$ is $\Omega(\frac{1}{\ell \log \ell})$. I think the analysis of this absolute spectral gap can be improved to $\Omega(\frac{1}{\ell})$.

Conjecture The absolute spectral gap of $G(k, \ell)$ with $k \ge 3$, $\ell \ge 2$, and $k > \ell + 1$ is $\Omega(\frac{1}{\ell})$.

This conjecture implies that the complexity of their algorithm is $O(k^{2/3} \log^{2/3} k)$.

I addition to just "feeling" that this conjecture should be true, I have "checked it" for 19 (small) pairs of $k$ and $\ell$ with $k \le 8$ and $\ell \le 6$ in the sense that I computed the spectra for those small graphs, conjectured a pattern for the relevant eigenvalues based on those spectra, and then (easily) showed that the above conjecture is true.

Does anyone know how to prove this conjecture?

  • $\begingroup$ $G(k,\ell)$ is "almost" a Cartesian product of the Cayley graph of $S_\ell$ as generated by 2-cycles together with the Johnson graph $J(k,\ell)$. "Almost" is close enough that I think one should be able to relate the spectra of $G(k,\ell)$ to the spectra of these graphs, which I believe are well-known (though I don't have references). $\endgroup$ – Andrew Morgan Jan 13 '18 at 2:09

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.