Let $T = \{z_1, \ldots z_n\}$ be a finite set of complex numbers on the unit circle. I would like an algorithm which can quickly compute the nonempty subset $S \subset T$ which maximizes $$\left \operatorname{Re}\left(\prod_{z \in S} z\right) \right.$$ I suspect this problem may be NPHard, but I'm not sure. I'm fine with an algorithm which computes an approximately maximal product.

3$\begingroup$ I suppose the subset $S$ should be nonempty. $\endgroup$– LeechLatticeFeb 24, 2022 at 8:33

$\begingroup$ If you look for an approximation, do you need something that works well for small $n$ (say smaller than 10) or rather something that works well for larger n, say $n=100$, and in the latter case, are your $z_i$ approximately uniformly random or follow some other known distribution? $\endgroup$– quaragueFeb 24, 2022 at 17:44
2 Answers
This is NPhard, because the subset sum problem with target number zero is reducible to it.
Suppose we want to find a nonempty subset of an integer subset $\{x_1,\cdots,x_n\}$ that sums up to zero.
Then we can let $z_k=\exp(2\pi i (x_k/a))$ where $a=x_1+\cdots+x_n+1$. There is a choice of $z_k$s that achieves the maximum value $1$ iff the corresponding nonempty subset sums up to $0$.
If you write $z = \exp(2\pi i\theta_z)$ for arguments $\theta_z\in [0,1)$, then as $$\Re(\prod_{z\in S}z) = \Re(\exp(2\pi \sum_{z\in S}\theta_z)) = \cos(2\pi\sum_{z\in S}\theta_z).$$ the problem is equivalent to finding $S$ such that $\sum_{z\in S}\theta_z\bmod 1$ is closest to either of $0$ (when the absolute value is positive) or $1/2$ (when it is negative). If one assumes that all $\theta_z$ are rational, and moreover that for $N\in\mathbb{N}$ they are all of the form $\theta_z = a_z / n$ for $a_z\in[0,1,\dots,n1]$, one can rewrite this as finding $S$ such that $\sum_{z\in S}a_z \bmod n$ is closest to $0$ or $n/2$.
This seems to be a modular version of the 01 knapsack (optimization) problem. This is a simultaneous generalization of the standard 01 knapsack problem in 2 ways
 there is a modular constraint  the objective function is $\sum_{z\in S}a_z \bmod n$ rather than $\sum_{z\in S}a_z$, and
 it is an optimization problem rather than a decision problem.
If you only had one of these generalizations, casual searching would lead to known results. For example, if you knew that $\sum_{z\in S}a_z\bmod n = 0$ (or $n/2$) exactly, then there is a standard reduction to lattice problems, which is even efficient if the instance is "sparse" in a certain sense.
I expect one can similarly attack this problem by reducing it to SVP/CVP on a suitable lattice. As a brief sketch, if one defines the matrix
$$B =\begin{pmatrix} N &0&0 &\dots & 0\\ a_{z_1} & 1 & 0 & &0\\ a_{z_2} & 0 & 1 & \dots &0\\ \vdots &&&\ddots&\vdots\\ a_{z_k} & 0 & 0 & \dots & 1 \end{pmatrix},$$ Then one can check that any (integer) linear combination of the rows of the above takes the form
$$ \begin{pmatrix} Nx_0 + a_{z_1}x_1 + \dots + a_{z_k}x_k\\ x_1\\ \vdots\\ x_k \end{pmatrix} $$ where $\vec x = (x_0,\dots, x_k)\in\mathbb{Z}^{k+1}$. Clearly, the norm of this is minimized for $\vec x = 0$. One can argue that the shortest nonzero vector will lead to $Nx_0 + \sum_i a_{z_i}x_i$ being small. There is still of course work to do (for example, the shortest vector in the aforementioned lattice may lead to a "solution" to a knapsack problem without 0/1 weights. This could plausibly be fixed by using a lattice basis with $M$ on the diagonal instead of $1$, to penalize choosing $x_1,\dots, x_k > 1$). Still, I expect a solution to your problem will proceed in a route similar to this, as this is fairly typical for "modular knapsack" problems.