The cube-term conjecture for the Hidden Kernel Problem

Let A\mathbb{A} be a finite algebra, and let a cube term be a term operation t(x1,,xn)t(x_1,\dots,x_n) such that, for every i[n]i\in[n], there is a choice of u1,,un{x,y}u_1,\dots,u_n\in\{x,y\} with ui=yu_i=y for which t(u1,,un)=xt(u_1,\dots,u_n)=x holds in A\mathbb{A}. Write HKP(An)\operatorname{HKP}(\mathbb{A}^n) for the Hidden Kernel Problem over the nn-th power of A\mathbb{A}. Cube-term conjecture. If A\mathbb{A} has a cube term, then HKP(An)\operatorname{HKP}(\mathbb{A}^n) has an efficient quantum solution. The conjecture proposes that the regularity supplied by a cube term is sufficient for efficient quantum algorithms, whereas counting arguments cannot rule out such algorithms because subalgebras, and hence congruences, of powers of A\mathbb{A} have polynomially bounded generating sets. An efficient quantum solution would in particular give an efficient quantum solution to the hidden normal subgroup problem.

Sources & referencesView supporting material

Primary source

Matthew Moore and Taylor Walenczyk, “The Hidden Subgroup Problem for Universal Algebras”, arXiv:2001.11298 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.