Quantum Speedup for Polar Maximum Likelihood Decoding

• URL: http://arxiv.org/abs/2411.04727v1
• Date: Thu, 07 Nov 2024 14:05:57 GMT
• Title: Quantum Speedup for Polar Maximum Likelihood Decoding
• Authors: Shintaro Fujiwara, Naoki Ishikawa,
• Abstract summary: We propose a novel ML decoding architecture for polar codes based on the Grover adaptive search algorithm. We show that our proposed quantum decoding achieves ML performance while providing a pure quadratic speedup in query complexity.
• Score: 3.190355298836875
• License:
• Abstract: Conventional decoding algorithms for polar codes strive to balance achievable performance and computational complexity in classical computing. While maximum likelihood (ML) decoding guarantees optimal performance, its NP-hard nature makes it impractical for real-world systems. In this letter, we propose a novel ML decoding architecture for polar codes based on the Grover adaptive search, a quantum exhaustive search algorithm. Unlike conventional studies, our approach, enabled by a newly formulated objective function, uniquely supports Gray-coded multi-level modulation without expanding the search space size compared to the classical ML decoding. Simulation results demonstrate that our proposed quantum decoding achieves ML performance while providing a pure quadratic speedup in query complexity.

Related papers

• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  We introduce a quantum algorithm for reducing classical optimization problems to classical decoding problems. We show that DQI achieves a better approximation ratio than any quantum-time classical algorithm known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
  We show that some existing quantum optimization methods can be unified into a solver that finds the binary solution that is most likely measured from the optimal quantum state. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO outperforms the Goemans--Williamson method and is comparable to state-of-the-art classical solvers.
  arXiv  Detail & Related papers  (2024-03-04T13:48:21Z)
• Deep Learning Assisted Multiuser MIMO Load Modulated Systems for Enhanced Downlink mmWave Communications [68.96633803796003]
  This paper is focused on multiuser load modulation arrays (MU-LMAs) which are attractive due to their low system complexity and reduced cost for millimeter wave (mmWave) multi-input multi-output (MIMO) systems. The existing precoding algorithm for downlink MU-LMA relies on a sub-array structured (SAS) transmitter which may suffer from decreased degrees of freedom and complex system configuration. In this paper, we conceive an MU-LMA system employing a full-array structured (FAS) transmitter and propose two algorithms accordingly.
  arXiv  Detail & Related papers  (2023-11-08T08:54:56Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Quantum Error Correction via Noise Guessing Decoding [0.0]
  Quantum error correction codes (QECCs) play a central role in both quantum communications and quantum computation. This paper shows that it is possible to both construct and decode QECCs that can attain the maximum performance of the finite blocklength regime.
  arXiv  Detail & Related papers  (2022-08-04T16:18:20Z)
• On Quantum-Assisted LDPC Decoding Augmented with Classical Post-Processing [1.0498337709016812]
  This paper looks into the Quadratic Unconstrained Binary Optimization (QUBO) and utilized D-Wave 2000Q Quantum Annealer to solve it. We evaluated and compared this implementation against the decoding performance obtained using Simulated Annealing (SA) and belief propagation (BP) decoding with classical computers.
  arXiv  Detail & Related papers  (2022-04-21T08:01:39Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach [1.4873907857806357]
  We present a quantum circuit for estimating algorithmic complexity using the coding theorem method. As a use-case, an application framework for protein-protein interaction based on algorithmic complexity is proposed.
  arXiv  Detail & Related papers  (2020-09-18T14:41:41Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.