It remains an open problem to find the optimal configuration of phase shifts under the discrete constraint for intelligent reflecting surface (IRS) in polynomial time. The above problem is widely believed to be difficult because it is not linked to any known combinatorial problems that can be solved efficiently. The branch-and-bound algorithms and the approximation algorithms constitute the best results in this area. Nevertheless, this work shows that the global optimum can actually be reached in linear time in terms of the number of reflective elements (REs) of IRS. The main idea is to geometrically interpret the discrete beamforming problem as choosing the optimal point on the unit circle. Although the number of possible combinations of phase shifts grows exponentially with the number of REs, it turns out that there are merely a linear number of points on the unit circle to consider. Furthermore, the proposed algorithm can be viewed as a novel approach to a special case of the discrete quadratic program (QP).

翻译：在多元时间里,在智能反射表面(IRS)的离散限制下,找到在智能反射表面(IRS)反向表面(IRS)的离散限制下,阶段性转移的最佳配置仍是一个尚未解决的问题。人们普遍认为,上述问题很困难,因为它与已知的可有效解决的组合问题没有联系。分支和约束算法和近似算法是这一领域的最佳结果。然而,这项工作表明,从IRS的反射元素数量来看,全球最优化实际上可以在线性时间内达到。主要想法是从几何角度解释离散波束问题,将它解释为在单位圆上选择最佳点。尽管相位转移的可能组合数随着RE的数量急剧增长,但结果发现,在单位圆上只有线性数点可以考虑。此外,拟议的算法可以被视为对离散四边程序(QP)的特殊案例的一种新颖的方法。