Quantum Speedup of the Dispersion and Codebook Design Problems
In this article, 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 c...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10654547/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832583990881550336 |
|---|---|
| author | Kein Yukiyoshi Taku Mikuriya Hyeon Seok Rou Giuseppe Thadeu Freitas de Abreu Naoki Ishikawa |
| author_facet | Kein Yukiyoshi Taku Mikuriya Hyeon Seok Rou Giuseppe Thadeu Freitas de Abreu Naoki Ishikawa |
| author_sort | Kein Yukiyoshi |
| collection | DOAJ |
| description | In this article, 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. In addition, 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 the Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem. |
| format | Article |
| id | doaj-art-9b89d38849fc49e9859023578e9edc6e |
| institution | Kabale University |
| issn | 2689-1808 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj-art-9b89d38849fc49e9859023578e9edc6e2025-01-28T00:02:30ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-01511610.1109/TQE.2024.345085210654547Quantum Speedup of the Dispersion and Codebook Design ProblemsKein Yukiyoshi0https://orcid.org/0009-0009-6243-7121Taku Mikuriya1https://orcid.org/0009-0005-9505-3205Hyeon Seok Rou2https://orcid.org/0000-0003-3483-7629Giuseppe Thadeu Freitas de Abreu3https://orcid.org/0000-0002-5018-8174Naoki Ishikawa4https://orcid.org/0000-0001-8978-4849Faculty of Engineering, Yokohama National University, Yokohama, JapanFaculty of Engineering, Yokohama National University, Yokohama, JapanSchool of Computer Science and Engineering, Constructor University, Bremen, GermanySchool of Computer Science and Engineering, Constructor University, Bremen, GermanyFaculty of Engineering, Yokohama National University, Yokohama, JapanIn this article, 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. In addition, 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 the Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem.https://ieeexplore.ieee.org/document/10654547/Codebook designDicke statedispersion problemGrover adaptive search (GAS)index modulation (IM)multiple-access systems |
| spellingShingle | Kein Yukiyoshi Taku Mikuriya Hyeon Seok Rou Giuseppe Thadeu Freitas de Abreu Naoki Ishikawa Quantum Speedup of the Dispersion and Codebook Design Problems IEEE Transactions on Quantum Engineering Codebook design Dicke state dispersion problem Grover adaptive search (GAS) index modulation (IM) multiple-access systems |
| title | Quantum Speedup of the Dispersion and Codebook Design Problems |
| title_full | Quantum Speedup of the Dispersion and Codebook Design Problems |
| title_fullStr | Quantum Speedup of the Dispersion and Codebook Design Problems |
| title_full_unstemmed | Quantum Speedup of the Dispersion and Codebook Design Problems |
| title_short | Quantum Speedup of the Dispersion and Codebook Design Problems |
| title_sort | quantum speedup of the dispersion and codebook design problems |
| topic | Codebook design Dicke state dispersion problem Grover adaptive search (GAS) index modulation (IM) multiple-access systems |
| url | https://ieeexplore.ieee.org/document/10654547/ |
| work_keys_str_mv | AT keinyukiyoshi quantumspeedupofthedispersionandcodebookdesignproblems AT takumikuriya quantumspeedupofthedispersionandcodebookdesignproblems AT hyeonseokrou quantumspeedupofthedispersionandcodebookdesignproblems AT giuseppethadeufreitasdeabreu quantumspeedupofthedispersionandcodebookdesignproblems AT naokiishikawa quantumspeedupofthedispersionandcodebookdesignproblems |