Motivated by the recent advancement of quantum processors, we investigate quantum approximate optimization algorithm (QAOA) to employ quasi-maximum-likelihood (ML) decoding of classical channel codes. QAOA is a hybrid quantum-classical variational algorithm, which is advantageous for the near-term noisy intermediate-scale quantum (NISQ) devices, where the fidelity of quantum gates is limited by noise and de-coherence. We first describe how to construct Ising Hamiltonian model to realize quasi-ML decoding with QAOA. For level-1 QAOA, we derive the systematic way to generate theoretical expressions of cost expectation for arbitrary binary linear codes. Focusing on [7], [4] Hamming code as an example, we analyze the impact of the degree distribution in associated generator matrix on the quantum decoding performance. The excellent performance of higher-level QAOA decoding is verified when Pauli rotation angles are optimized through meta-heuristic variational quantum eigensolver (VQE). Furthermore, we demonstrate the QAOA decoding performance in a real quantum device.
Motivated by the recent advancement of quantum processors, we investigate quantum approximate optimization algorithm (QAOA) to employ quasi-maximum-likelihood (ML) decoding of classical channel codes. QAOA is a hybrid quantum-classical variational algorithm, which is advantageous for the near-term noisy intermediate-scale quantum (NISQ) devices, where the fidelity of quantum gates is limited by noise and de-coherence. We first describe how to construct Ising Hamiltonian model to realize quasi-ML decoding with QAOA. For level-1 QAOA, we derive the systematic way to generate theoretical expressions of cost expectation for arbitrary binary linear codes. Focusing on [7], [4] Hamming code as an example, we analyze the impact of the degree distribution in associated generator matrix on the quantum decoding performance. The excellent performance of higher-level QAOA decoding is verified when Pauli rotation angles are optimized through meta-heuristic variational quantum eigensolver (VQE). Furthermore, we demonstrate the QAOA decoding performance in a real quantum device.
Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithm (QAOA) constitutes a promising candidate for demonstrating tangible quantum advantages based on NISQ devices. In this paper, we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel, where finding the optimal solution is exponentially hard using classical computers. Here, we apply the QAOA for the ML detection by encoding the problem of interest into a level-pQAOA circuit having2pvariational parameters, which can be optimized by classical optimizers. This level-pQAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately inpconsecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector.
Quantum approximate optimization algorithm (QAOA) is used for NP-hard problems on noisy intermediate-scale quantum (NISQ) devices. We demonstrate QAOA’s near-optimum maximum likelihood (ML) decoding for short block-lengths in Gaussian channels using random linear codes and channel coded modulation. Simulations with a p-layer QAOA decoder for  p ∈ [1, 4], coding rates R = k/n ∈ [0.3, 1], signal-to-noise ratio (SNR)  ∈  [0, 10] dB and k ∈ [10, 26] show near-optimum bit and block error rates. We conjecture near-optimum performance for p ∈ [1, 10], R = 0.5, SNR = 10 dB and k ≦ 250 indicating QAOA’s potential in short block-length decoding.
Quantum approximate optimization algorithm (QAOA) is used for NP-hard problems on noisy intermediate-scale quantum (NISQ) devices. We demonstrate QAOA's near-optimum maximum likelihood (ML) decoding for short block-lengths in Gaussian channels using random linear codes and channel coded modulation. Simulations with a p-layer QAOA decoder for p ∈ [1, 4], coding rates R = k/n ∈ [0.3, 1], signal-to-noise ratio (SNR) ∈ [0, 10] dB and k ∈ [10, 26] show near-optimum bit and block error rates. We conjecture near-optimum performance for p ∈ [1, 10], R = 0.5, SNR = 10 dB and k ≦ 250 indicating QAOA's potential in short block-length decoding.
In the massive multiple-input and multiple-output (Massive MIMO) systems, the maximum likelihood (ML) detection problem is NP-hard and becoming classically intricate with the number of transmitting antennas and symbols increasing. The quantum approximate optimization algorithm (QAOA), a leading candidate algorithm running in the noisy intermediate-scale quantum (NISQ) devices, can show quantum advantage for approximately solving combinatorial optimization problems. In this paper, we propose the QAOA based on the maximum likelihood detection solver of binary symbols. In the proposed scheme, we first conduct a universal and compact analytical expression for the expectation value of the 1-level QAOA. Second, a Bayesian optimization based parameters initialization is presented, which can speedup the convergence of the QAOA to a lower local minimum and improve the probability of measuring the exact solution. Compared to the state-of-the-art QAOA based ML detection algorithm, our scheme has the more universal and compact expectation value expression of the 1-level QAOA, and requires few quantum resources and has the higher probability to obtain the exact solution.
This paper presents a qualitative analysis of hybrid quantum-classical computing approaches aimed at solving complex optimization problems using near-term quantum processors. Hybrid algorithms leverage the strengths of quantum and classical computing to tackle computationally intensive tasks often constrained by current quantum hardware limitations. Through an extensive literature review and synthesis of recent empirical studies, we benchmark various hybrid algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE), focusing on their performance, scalability, and practical applicability on noisy intermediate-scale quantum (NISQ) devices. The study highlights the advantages, challenges, and future prospects of integrating hybrid quantum-classical computation in optimization domains, providing a comprehensive framework and qualitative insights into benchmarking methodologies and critical performance metrics.
Quantum optimization allows for up to exponential quantum speedups for specific, possibly industrially relevant problems. As the key algorithm in this field, we motivate and discuss the Quantum Approximate Optimization Algorithm (QAOA), which can be understood as a slightly generalized version of Quantum Annealing for gate-based quantum computers. We delve into the quantum circuit implementation of the QAOA, including Hamiltonian simulation techniques for higher-order Ising models, and discuss parameter training using the parameter shift rule. An example implementation with Pennylane source code demonstrates practical application for the Maximum Cut problem. Further, we show how constraints can be incorporated into the QAOA using Grover mixers, allowing to restrict the search space to strictly valid solutions for specific problems. Finally, we outline the Variational Quantum Eigensolver (VQE) as a generalization of the QAOA, highlighting its potential in the NISQ era and addressing challenges such as barren plateaus and ansatz design.