Quantum algorithm for Smallest Conjugate

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $c$ be an algebraic integer, specified by its monic irreducible polynomial in $\mathbb Z[X]$, and let $S\subset\mathbb Z[c]$ be a nonzero ideal specified by an integral basis in the coefficient basis $1,c,\ldots,c^{n-1}$, where $n=[\mathbb Q(c):\mathbb Q]$. For $v\in\mathbb Q(c)$ define \[ \|v\|_{\rm conj}=\max_{\sigma:\mathbb Q(c)\hookrightarrow\mathbb C}|\sigma(v)|. \] The Smallest Conjugate problem is minimization over nonzero ideal elements, rather than selection of a conjugate of one given element. The nonzero convention is the shortest-vector convention used throughout the source and in its immediate ideal-lattice equivalences.

Statement recorded in the supplied source.

Develop a quantum algorithm, polynomial in the bit length of the defining polynomial and ideal basis, which returns $0\ne v\in S$ minimizing $\|v\|_{\rm conj}$. [S2]

Short English statement

Find an efficient quantum algorithm for the ideal element whose largest conjugate magnitude is smallest.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800077 (AMR-087-0077). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Daniele Micciancio, Ideal Lattices: cryptographic applications and open problems, IPAM Number Theory and Cryptography: Open Problems workshop (9--13 October 2006), PDF pages 28--34, 41. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6240.pdf.