Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916103725252608 |
|---|---|
| author | Suppakitpaisarn, Vorapong Hao, Jin-Kao |
| author_facet | Suppakitpaisarn, Vorapong Hao, Jin-Kao |
| contents | We suggest employing graph sparsification as a pre-processing step for maxcut programs using the QUBO solver. Quantum(-inspired) algorithms are recognized for their potential efficiency in handling quadratic unconstrained binary optimization (QUBO). Given that maxcut is an NP-hard problem and can be readily expressed using QUBO, it stands out as an exemplary case to demonstrate the effectiveness of quantum(-inspired) QUBO approaches. Here, the non-zero count in the QUBO matrix corresponds to the graph's edge count. Given that many quantum(-inspired) solvers operate through cloud services, transmitting data for dense graphs can be costly. By introducing the graph sparsification method, we aim to mitigate these communication costs. Experimental results on classical, quantum-inspired, and quantum solvers indicate that this approach substantially reduces communication overheads and yields an objective value close to the optimal solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13004 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver Suppakitpaisarn, Vorapong Hao, Jin-Kao Optimization and Control Distributed, Parallel, and Cluster Computing Quantum Physics We suggest employing graph sparsification as a pre-processing step for maxcut programs using the QUBO solver. Quantum(-inspired) algorithms are recognized for their potential efficiency in handling quadratic unconstrained binary optimization (QUBO). Given that maxcut is an NP-hard problem and can be readily expressed using QUBO, it stands out as an exemplary case to demonstrate the effectiveness of quantum(-inspired) QUBO approaches. Here, the non-zero count in the QUBO matrix corresponds to the graph's edge count. Given that many quantum(-inspired) solvers operate through cloud services, transmitting data for dense graphs can be costly. By introducing the graph sparsification method, we aim to mitigate these communication costs. Experimental results on classical, quantum-inspired, and quantum solvers indicate that this approach substantially reduces communication overheads and yields an objective value close to the optimal solution. |
| title | Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Quantum Physics |
| url | https://arxiv.org/abs/2401.13004 |