Quantum-Relaxation Based Optimization Algorithms: Experimental Analysis and Theoretical Extensions

• Item type: SIG Technical Reports(1)
• 公開日: 2023-03-06
• タイトル: Quantum-Relaxation Based Optimization Algorithms: Experimental Analysis and Theoretical Extensions
• タイトル / 言語: en
• タイトル: Quantum-Relaxation Based Optimization Algorithms: Experimental Analysis and Theoretical Extensions
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Dept. of Computer Science, The Univ. of Tokyo
• 著者所属: Dept. of Computer Science, The Univ. of Tokyo／IBM Quantum, IBM Japan／Quantum Computing Center, Keio University
• 著者所属: Dept. of Computer Science, The Univ. of Tokyo
• 著者所属: Dept. of Computer Science, The Univ. of Tokyo
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science, The Univ. of Tokyo
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science, The Univ. of Tokyo / IBM Quantum, IBM Japan / Quantum Computing Center, Keio University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science, The Univ. of Tokyo
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science, The Univ. of Tokyo
• 著者名: Kosei, Teramoto; Rudy, Raymond; Eyuri, Wakakuwa; Hiroshi, Imai
• 著者名(英): Kosei, Teramoto; Rudy, Raymond; Eyuri, Wakakuwa; Hiroshi, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. (2021) that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. Differing from standard quantum optimizers such as QAOA, it utilizes the eigenstates of local Hamiltonians that are not diagonal in the computational basis. There are indications that quantum entanglement may not be needed to solve binary optimization problems with standard quantum optimizers because the maximal eigenstates of diagonal Hamiltonians include classical states. QRAO with a bit-to-qubit compression ratio of 3x has an approximation ratio for the maximum cut problem as 0.555, and there is a trade-off between space efficiency and approximability. In this study, we (1) experimentally analyze QRAO (especially the role of entanglement) and (2) theoretically extend the quantum relaxation to obtain new approximation and compression tradeoffs.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. (2021) that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. Differing from standard quantum optimizers such as QAOA, it utilizes the eigenstates of local Hamiltonians that are not diagonal in the computational basis. There are indications that quantum entanglement may not be needed to solve binary optimization problems with standard quantum optimizers because the maximal eigenstates of diagonal Hamiltonians include classical states. QRAO with a bit-to-qubit compression ratio of 3x has an approximation ratio for the maximum cut problem as 0.555, and there is a trade-off between space efficiency and approximability. In this study, we (1) experimentally analyze QRAO (especially the role of entanglement) and (2) theoretically extend the quantum relaxation to obtain new approximation and compression tradeoffs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2023-QS-8, 号 15, p. 1-9, 発行日 2023-03-06
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会