The cube-term conjecture for the Hidden Kernel Problem

About 6 years old · traced to

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.

References

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.