Noise Robustness of Quantum Relaxation for Combinatorial Optimization
Relaxation is a common way for dealing with combinatorial optimization problems. Quantum random-access optimization (QRAO) is a quantum-relaxation-based optimizer that uses fewer qubits than the number of bits in the original problem by encoding multiple variables per qubit using quantum random-acce...
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/10623712/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832583973863161856 |
|---|---|
| author | Kentaro Tamura Yohichi Suzuki Rudy Raymond C. Hiroshi Watanabe Yuki Sato Ruho Kondo Michihiko Sugawara Naoki Yamamoto |
| author_facet | Kentaro Tamura Yohichi Suzuki Rudy Raymond C. Hiroshi Watanabe Yuki Sato Ruho Kondo Michihiko Sugawara Naoki Yamamoto |
| author_sort | Kentaro Tamura |
| collection | DOAJ |
| description | Relaxation is a common way for dealing with combinatorial optimization problems. Quantum random-access optimization (QRAO) is a quantum-relaxation-based optimizer that uses fewer qubits than the number of bits in the original problem by encoding multiple variables per qubit using quantum random-access code (QRAC). Reducing the number of qubits will alleviate physical noise (typically, decoherence), and as a result, the quality of the binary solution of QRAO may be robust against noise, which is, however, unknown. In this article, we numerically demonstrate that the mean approximation ratio of the (3, 1)-QRAC Hamiltonian, i.e., the Hamiltonian utilizing the encoding of three bits into one qubit by QRAC, is less affected by noise compared with the conventional Ising Hamiltonian used in the quantum annealer and the quantum approximate optimization algorithm. Based on this observation, we discuss a plausible mechanism behind the robustness of QRAO under depolarizing noise. Finally, we assess the number of shots required to estimate the values of binary variables correctly under depolarizing noise and show that the (3, 1)-QRAC Hamiltonian requires less shots to achieve the same accuracy compared with the Ising Hamiltonian. |
| format | Article |
| id | doaj-art-4e63221b41b5428298061138ca3f623e |
| 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-4e63221b41b5428298061138ca3f623e2025-01-28T00:02:21ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-0151910.1109/TQE.2024.343913510623712Noise Robustness of Quantum Relaxation for Combinatorial OptimizationKentaro Tamura0https://orcid.org/0009-0001-6971-6109Yohichi Suzuki1Rudy Raymond2https://orcid.org/0000-0003-1005-6705C. Hiroshi Watanabe3Yuki Sato4https://orcid.org/0000-0003-2069-0355Ruho Kondo5Michihiko Sugawara6https://orcid.org/0000-0003-0484-9899Naoki Yamamoto7https://orcid.org/0000-0002-8497-4608Department of Applied Physics and Physico-Informatics, Keio University, Yokohama, JapanQuantum Computing Center, Keio University, Yokohama, JapanQuantum Computing Center, Keio University, Yokohama, JapanQuantum Computing Center, Keio University, Yokohama, JapanQuantum Computing Center, Keio University, Yokohama, JapanQuantum Computing Center, Keio University, Yokohama, JapanQuantum Computing Center, Keio University, Yokohama, JapanDepartment of Applied Physics and Physico-Informatics, Keio University, Yokohama, JapanRelaxation is a common way for dealing with combinatorial optimization problems. Quantum random-access optimization (QRAO) is a quantum-relaxation-based optimizer that uses fewer qubits than the number of bits in the original problem by encoding multiple variables per qubit using quantum random-access code (QRAC). Reducing the number of qubits will alleviate physical noise (typically, decoherence), and as a result, the quality of the binary solution of QRAO may be robust against noise, which is, however, unknown. In this article, we numerically demonstrate that the mean approximation ratio of the (3, 1)-QRAC Hamiltonian, i.e., the Hamiltonian utilizing the encoding of three bits into one qubit by QRAC, is less affected by noise compared with the conventional Ising Hamiltonian used in the quantum annealer and the quantum approximate optimization algorithm. Based on this observation, we discuss a plausible mechanism behind the robustness of QRAO under depolarizing noise. Finally, we assess the number of shots required to estimate the values of binary variables correctly under depolarizing noise and show that the (3, 1)-QRAC Hamiltonian requires less shots to achieve the same accuracy compared with the Ising Hamiltonian.https://ieeexplore.ieee.org/document/10623712/Combinatorial optimizationdepolarizing noisequantum random-access code (QRAC)quantum relaxation |
| spellingShingle | Kentaro Tamura Yohichi Suzuki Rudy Raymond C. Hiroshi Watanabe Yuki Sato Ruho Kondo Michihiko Sugawara Naoki Yamamoto Noise Robustness of Quantum Relaxation for Combinatorial Optimization IEEE Transactions on Quantum Engineering Combinatorial optimization depolarizing noise quantum random-access code (QRAC) quantum relaxation |
| title | Noise Robustness of Quantum Relaxation for Combinatorial Optimization |
| title_full | Noise Robustness of Quantum Relaxation for Combinatorial Optimization |
| title_fullStr | Noise Robustness of Quantum Relaxation for Combinatorial Optimization |
| title_full_unstemmed | Noise Robustness of Quantum Relaxation for Combinatorial Optimization |
| title_short | Noise Robustness of Quantum Relaxation for Combinatorial Optimization |
| title_sort | noise robustness of quantum relaxation for combinatorial optimization |
| topic | Combinatorial optimization depolarizing noise quantum random-access code (QRAC) quantum relaxation |
| url | https://ieeexplore.ieee.org/document/10623712/ |
| work_keys_str_mv | AT kentarotamura noiserobustnessofquantumrelaxationforcombinatorialoptimization AT yohichisuzuki noiserobustnessofquantumrelaxationforcombinatorialoptimization AT rudyraymond noiserobustnessofquantumrelaxationforcombinatorialoptimization AT chiroshiwatanabe noiserobustnessofquantumrelaxationforcombinatorialoptimization AT yukisato noiserobustnessofquantumrelaxationforcombinatorialoptimization AT ruhokondo noiserobustnessofquantumrelaxationforcombinatorialoptimization AT michihikosugawara noiserobustnessofquantumrelaxationforcombinatorialoptimization AT naokiyamamoto noiserobustnessofquantumrelaxationforcombinatorialoptimization |