Quantum Speedup of the Dispersion and Codebook Design Problems
arXiv:2406.07187 · doi:10.1109/TQE.2024.3450852
Abstract
We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm, offering quadratic speedup. Dispersion problems are combinatorial optimization problems classified as NP-hard, which appear often in coding theory and wireless communications applications involving optimal codebook design. In turn, GAS is a quantum exhaustive search algorithm that can be used to implement full-fledged maximum-likelihood optimal solutions. In conventional naive formulations however, it is typical to rely on a binary vector spaces, resulting in search space sizes prohibitive even for GAS. To circumvent this challenge, we instead formulate the search of optimal dispersion problem over Dicke states, an equal superposition of binary vectors with equal Hamming weights, which significantly reduces the search space leading to a simplification of the quantum circuit via the elimination of penalty terms. Additionally, we propose a method to replace distance coefficients with their ranks, contributing to the reduction of the number of qubits. Our analysis demonstrates that as a result of the proposed techniques a reduction in query complexity compared to the conventional GAS using Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem.
13 pages, 7 figures
References in corpus (19)
- Quantum Amplitude Amplification and Estimation
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- SCMA Codebook Design
- Fixed-point quantum search with an optimal number of queries
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
- Deterministic Preparation of Dicke States
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Hybrid Beamforming for Intelligent Reflecting Surface Aided Millimeter Wave MIMO Systems
- The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
- Downlink SCMA Codebook Design with Low Error Rate by Maximizing Minimum Euclidean Distance of Superimposed Codewords
- A Divide-and-Conquer Approach to Dicke State Preparation
- Short-Depth Circuits for Dicke State Preparation
- Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
- Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
- Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
- Fermionic Quantum Approximate Optimization Algorithm
- Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
- Optimization of probabilistic quantum search algorithm with a priori information