Quantum Algorithm for MIMO ML detection

Question

I am reding the paper EXIT-Chart Aided Near-Capacity Quantum Turbo Code Design by Babar et al. and in the introduction, it is stated that due to the exponentially increasing complexity of the MIMO ML decoding, it is an idea to pass such problem to the quantum domain in order to make use of the inherent parallel nature of it, and so reduce the complexity of such problem.

I was wondering then if there has been any research on the topic of using quantum computing to solve such problem related with MIMO channels, and so if there has been, to reference some papers where such type of quantum algorithms are presented.

Answer 1

Yeah. See this one for a more-or-less analogous problem: https://ieeexplore.ieee.org/document/6515077?arnumber=6515077 . Look for some papers by Lajos Hanzo on IEEE Explore. One thing that's notable is that MIMO detection is NP hard.

Specifically, to solve the MIMO (or MU) ML detection problem exactly (currently) requires searching an exponential space. Applying quantum unstructured search gives a square root factor improvement via Grover's Algorithm, so the resulting problem is still exponential.

In more practical MIMO detection, people generally apply heuristics or solve relaxations of the actual problem. Typically, we can do a solid job in low polynomial complexity.