Approximate Solutions of Combinatorial Problems via Quantum Relaxations
Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose...
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/10586788/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832586871885004800 |
|---|---|
| author | Bryce Fuller Charles Hadfield Jennifer R. Glick Takashi Imamichi Toshinari Itoko J. Richard Thompson Yang Jiao M. Marna Kagele W. Blom-Schieber Adriana Rudy Raymond Antonio Mezzacapo |
| author_facet | Bryce Fuller Charles Hadfield Jennifer R. Glick Takashi Imamichi Toshinari Itoko J. Richard Thompson Yang Jiao M. Marna Kagele W. Blom-Schieber Adriana Rudy Raymond Antonio Mezzacapo |
| author_sort | Bryce Fuller |
| collection | DOAJ |
| description | Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors. |
| format | Article |
| id | doaj-art-84de6beefa3540839cf9adfd65737435 |
| 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-84de6beefa3540839cf9adfd657374352025-01-25T00:03:35ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-01511510.1109/TQE.2024.342129410586788Approximate Solutions of Combinatorial Problems via Quantum RelaxationsBryce Fuller0https://orcid.org/0009-0009-3218-6501Charles Hadfield1Jennifer R. Glick2Takashi Imamichi3https://orcid.org/0000-0002-4423-6897Toshinari Itoko4J. Richard Thompson5https://orcid.org/0000-0003-0266-3249Yang Jiao6https://orcid.org/0000-0001-9583-0784M. Marna Kagele7W. Blom-Schieber Adriana8Rudy Raymond9Antonio Mezzacapo10IBM Quantum, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USAIBM Quantum, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USAIBM Quantum, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USAIBM Quantum, IBM Research—Tokyo, Tokyo, JapanIBM Quantum, IBM Research—Tokyo, Tokyo, JapanIntegrated Vehicle Systems, Boeing Research & Technology, Huntsville, AL, USAIntegrated Vehicle Systems, Boeing Research & Technology, Tukwila, WA, USATech Vis and Integration, Global Technology, Boeing Research & Technology, Tukwila, WA, USAProduct Development—Structures, Boeing Commercial Aircraft, Everett, WA, USAIBM Quantum, IBM Research—Tokyo, Tokyo, JapanIBM Quantum, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USACombinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.https://ieeexplore.ieee.org/document/10586788/Combinatorial optimizationquantum optimizationquantum random access codes (QRACs) |
| spellingShingle | Bryce Fuller Charles Hadfield Jennifer R. Glick Takashi Imamichi Toshinari Itoko J. Richard Thompson Yang Jiao M. Marna Kagele W. Blom-Schieber Adriana Rudy Raymond Antonio Mezzacapo Approximate Solutions of Combinatorial Problems via Quantum Relaxations IEEE Transactions on Quantum Engineering Combinatorial optimization quantum optimization quantum random access codes (QRACs) |
| title | Approximate Solutions of Combinatorial Problems via Quantum Relaxations |
| title_full | Approximate Solutions of Combinatorial Problems via Quantum Relaxations |
| title_fullStr | Approximate Solutions of Combinatorial Problems via Quantum Relaxations |
| title_full_unstemmed | Approximate Solutions of Combinatorial Problems via Quantum Relaxations |
| title_short | Approximate Solutions of Combinatorial Problems via Quantum Relaxations |
| title_sort | approximate solutions of combinatorial problems via quantum relaxations |
| topic | Combinatorial optimization quantum optimization quantum random access codes (QRACs) |
| url | https://ieeexplore.ieee.org/document/10586788/ |
| work_keys_str_mv | AT brycefuller approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT charleshadfield approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT jenniferrglick approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT takashiimamichi approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT toshinariitoko approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT jrichardthompson approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT yangjiao approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT mmarnakagele approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT wblomschieberadriana approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT rudyraymond approximatesolutionsofcombinatorialproblemsviaquantumrelaxations AT antoniomezzacapo approximatesolutionsofcombinatorialproblemsviaquantumrelaxations |