Quantum Annealing (QA)-accelerated MIMO detection is an emerging research approach in the context of NextG wireless networks. The opportunity is to enable large MIMO systems and thus improve wireless performance. The approach aims to leverage QA to expedite the computation required for theoretically optimal but computationally-demanding Maximum Likelihood detection to overcome the limitations of the currently deployed linear detectors. This paper presents X-ResQ, a QA-based MIMO detector system featuring flexible parallelism that is uniquely enabled by quantum Reverse Annealing (RA). Unlike prior designs, X-ResQ has many desirable parallel QA system properties and has effectively improved detection performance as more qubits are assigned. In our evaluations on a state-of-the-art quantum annealer, fully parallel X-ResQ achieves near-optimal throughput for 4 × 6 MIMO with 16-QAM using approx. 240 qubits achieving 2.5–5× gains compared against other classical and quantum detectors. We also implement and evaluate X-ResQ in the non-quantum digital setting for more comprehensive evaluations. This classical X-ResQ showcases the potential to realize ultra-large 1024 × 1024 MIMO, significantly outperforming other MIMO detectors, including the state-of-the-art RA detector classically implemented in the same way.

Multiple-Input-Multiple-Output (MIMO) signal detection is central to nearly every state-of-the-art communication system, and enhancements in error performance and computational complexity of MIMO detection would significantly enhance data rate and latency experienced by the users. Theoretically, the optimal MIMO detector is the maximum-likelihood (ML) MIMO detector; however, due to its extremely high complexity, it is not feasible for large real-world communication systems. Over the past few years, algorithms based on physics-inspired Ising solvers, like Coherent Ising machines and Quantum Annealers, have shown significant performance improvements for the MIMO detection problem. However, the current state-of-the-art is limited to low-order modulations or systems with few users. In this paper, we propose an adaptive multi-stage Ising machine-based MIMO detector that extends the performance gains of physics-inspired computation to Large and Massive MIMO systems with a large number of users and very high modulation schemes (up to 256-QAM). We enhance our previously proposed delta Ising formulation and develop a heuristic that adaptively optimizes the performance and complexity of our proposed method. We perform extensive micro-benchmarking to optimize several free parameters of the system and evaluate our methods’ BER and spectral efficiency for Large and Massive MIMO systems (up to 32 users and 256-QAM modulation).

Optimal MIMO detection is one of the most computationally challenging tasks in wireless systems. We show that the quantum-inspired computing approach based on Coherent Ising Machines (CIMs) is a promising candidate for performing near-optimal MIMO detection. We propose a novel regularized Ising formulation for MIMO detection that mitigates a common error floor issue in the direct approach adopted in the existing literature on MIMO detection using Quantum Annealing. We evaluate our methods using a simplified, quantum-inspired model and show that our methods can achieve a near-optimal performance for several Large MIMO systems, like$16\times 16,20\times 20$, and$24\times 24$MIMO with BPSK modulation.

The last couple of years have seen an emergence of physics-inspired computing for maximum likelihood MIMO detection. These methods involve transforming the MIMO detection problem into an Ising minimization problem, which can then be solved on an Ising Machine. Recent works have shown promising projections for MIMO wireless detection using Quantum Annealing optimizers and Coherent Ising Machines. While these methods perform very well for BPSK and 4-QAM, they struggle to provide good BER for 16-QAM and higher modulations. In this paper, we explore an enhanced CIM model, and propose a novel Ising formulation, which together are shown to be the first Ising solver that provides significant gains in the BER performance of large and massive MIMO systems, like$16 \times 16$and$16 \times 32$, and sustain its performance gain even at 256-QAM modulation. We further perform a spectral efficiency analysis and show that, for a$16 \times 16$MIMO with Adaptive Modulation and Coding, our method can provide substantial throughput gains over MMSE, achieving$2\times$throughput for SNR$\leq 25$dB, and up to$1.5\times$throughput for SNR$\geq 30$dB.

With the continuous growth of the Internet of Things (IoT), the trend of increasing numbers of IoT devices will continue. To increase the network's capability to support a large number of active devices accessing a network concurrently, this work presents IoT-ResQ, a warm-started quantum annealing-based multi-device detector via quantum reverse annealing (RA). Unlike in typical quantum forward annealing (FA) protocol, IoT-ResQ's RA starts its search operation on a controllable candidate classical state, instead of a quantum superposition, and thus allows refined local quantum search around the initial state. This procedure can provide an opportunity of utilizing both conventional classical- and quantum-based detectors together in a hybrid synergy, to boost quantum optimization performance, mitigating the effect of quantum decoherence and noise on quantum hardware. In our evaluation, IoT-ResQ achieves nearly two to three orders of magnitude better BER and over 2X packet success rate with packet size of 32-byte compared to other quantum and conventional detectors at SNR 9 dB to support 48 active IoT devices with QPSK modulation (implying 48,000 deployed devices with 0.1% wake-up radio rate at a time), requiring ≈ 140 μs pure compute time for detection.

Optimal MIMO detection is one of the most computationally challenging tasks in wireless systems. We show that new analog computing approaches, such as Coherent Ising Machines (CIMs), are promising candidates for performing near-optimal MIMO detection. We propose a novel regularized Ising formulation for MIMO detection that mitigates a common error floor issue in the naive approach and evolve it into a regularized, Ising-based tree search algorithm that achieves near-optimal performance. By means of numerical simulation using the Rayleigh fading channel model, we show that in principle, a MIMO detector based on a high-speed Ising machine (such as a CIM implementation optimized for latency) would allow a higher transmitter antennas (users)-to-receiver antennas ratio and thus increase the overall throughput of the cell by a factor of two or more for massive MIMO systems. Our methods create an opportunity to operate wireless systems using more aggressive modulation and coding schemes and hence achieve high spectral efficiency: for a$16\times 16$MIMO system, we estimate around$2.5\times $more throughput in the mid-SNR regime (≈12 dB) and$2\times $more throughput in the high-SNR regime (>20 dB) as compared to the industry standard, a Minimum-Mean Square Error (MMSE) linear decoder.

In a multi-user system with multiple antennas at the base station, precoding techniques in the downlink broadcast channel allow users to detect their respective data in a non-cooperative manner. Vector Perturbation Precoding (VPP) is a non-linear variant of transmit-side channel inversion that perturbs user data to achieve full diversity order. While promising, finding an optimal perturbation in VPP is known to be an NP-hard problem, demanding heavy computational support at the base station and limiting the feasibility of the approach to small MIMO systems. This work proposes a radically different processing architecture for the downlink VPP problem, one based on Quantum Annealing (QA), to enable the applicability of VPP to large MIMO systems. Our design reduces VPP to a quadratic polynomial form amenable to QA, then refines the problem coefficients to mitigate the adverse effects of QA hardware noise. We evaluate our proposed QA based VPP (QAVP) technique on a real Quantum Annealing device over a variety of design and machine parameter settings. With existing hardware, QAVP can achieve a BER of 10−4with 100µs compute time, for a 6 × 6 MIMO system using 64 QAM modulation at 32 dB SNR.

Overcoming the conventional trade-off between throughput and bit error rate (BER) performance, versus computational complexity is a long-term challenge for uplink Multiple-Input Multiple-Output (MIMO) detection in base station design for the cellular 5G New Radio roadmap, as well as in next generation wireless local area networks. In this work, we present ParaMax, a MIMO detector architecture that for the first time brings to bear physics-inspired parallel tempering algorithmic techniques [28, 50, 67] on this class of problems. ParaMax can achieve near optimal maximum-likelihood (ML) throughput performance in the Large MIMO regime, Massive MIMO systems where the base station has additional RF chains, to approach the number of base station antennas, in order to support even more parallel spatial streams. ParaMax is able to achieve a near ML-BER performance up to 160 × 160 and 80 × 80 Large MIMO for low-order modulations such as BPSK and QPSK, respectively, only requiring less than tens of processing elements. With respect to Massive MIMO systems, in 12 × 24 MIMO with 16-QAM at SNR 16 dB, ParaMax achieves 330 Mbits/s near-optimal system throughput with 4--8 processing elements per subcarrier, which is approximately 1.4× throughput than linear detector-based Massive MIMO systems.

The problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilationtask, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOA for Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we apply a planning approach to qubit initialization. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds, and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring. These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.

With unprecedented increases in traffic load in today's wireless networks, design challenges shift from the wireless network itself to the computational support behind the wireless network. In this vein, there is new interest in quantum-compute approaches because of their potential to substantially speed up processing, and so improve network throughput. However, quantum hardware that actually exists today is much more susceptible to computational errors than silicon-based hardware, due to the physical phenomena of decoherence and noise. This paper explores the boundary between the two types of computation---classical-quantum hybrid processing for optimization problems in wireless systems---envisioning how wireless can simultaneously leverage the benefit of both approaches. We explore the feasibility of a hybrid system with a real hardware prototype using one of the most advanced experimentally available techniques today, reverse quantum annealing. Preliminary results on a low-latency, large MIMO system envisioned in the 5G New Radio roadmap are encouraging, showing approximately 2-10x better performance in terms of processing time than prior published results.

We present the mapping of a class of simplified air traffic management problems (strategic conflict resolution) to quadratic unconstrained Boolean optimization problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where the nodes of the graph represent flights and the edges represent a potential conflict between flights. The representation allows a natural decomposition of a real-world instance related to wind-optimal trajectories over the Atlantic Ocean into smaller subproblems that can be discretized and are amenable to be programmed in quantum annealers. In this paper, we tested the new programming techniques, and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices, the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time.

User demand for increasing amounts of wireless capacity continues to outpace supply, and so to meet this demand, significant progress has been made in new MIMO wireless physical layer techniques. Higher-performance systems now remain impractical largely only because their algorithms are extremely computationally demanding. For optimal performance, an amount of computation that increases at an exponential rate both with the number of users and with the data rate of each user is often required. The base station's computational capacity is thus becoming one of the key limiting factors on wireless capacity. QuAMax is the first large MIMO centralized radio access network design to address this issue by leveraging quantum annealing on the problem. We have implemented QuAMax on the 2,031 qubit D-Wave 2000Q quantum annealer, the state-of-the-art in the field. Our experimental results evaluate that implementation on real and synthetic MIMO channel traces, showing that 10 µs of compute time on the 2000Q can enable 48 user, 48 AP antenna BPSK communication at 20 dB SNR with a bit error rate of 10-6 and a 1,500 byte frame error rate of 10-4.

We investigate the application of temporal planners to the problem of compiling quantum circuits to emerging quantum hardware. While our approach is general, we focus our initial experiments on Quantum Approximate Optimization Algorithm (QAOA) circuits that have few ordering constraints and thus allow highly parallel plans. We report on experiments using several temporal planners to compile circuits of various sizes to a realistic hardware architecture. This early empirical evaluation suggests that temporal planning is a viable approach to quantum circuit compilation.

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

There are two complementary ways to evaluate planning algorithms: performance on benchmark problems derived from real applications and analysis of performance on parametrized families of problems with known properties. Prior to this work, few means of generating parametrized families of hard planning problems were known. We generate hard planning problems from the solvable/unsolvable phase transition region of well-studied NP-complete problems that map naturally to navigation and scheduling, aspects common to many planning domains. We observe significant differences between state-of-the-art planners on these problem families, enabling us to gain insight into the relative strengths and weaknesses of these planners. Our results confirm exponential scaling of hardness with problem size, even at very small problem sizes. These families provide complementary test sets exhibiting properties not found in existing benchmarks.