Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.22056 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917187583737856 |
|---|---|
| author | Lin, Yuefeng Wang, Kun Zheng, Qinyuan Zhang, Rui Fang, Jing-Kai Meng, Tiejun Xiang, Jingen Guo, Cong Huang, Jun-Han |
| author_facet | Lin, Yuefeng Wang, Kun Zheng, Qinyuan Zhang, Rui Fang, Jing-Kai Meng, Tiejun Xiang, Jingen Guo, Cong Huang, Jun-Han |
| contents | MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algorithms offer promising new approaches that may eventually outperform classical schemes, they suffer from resource constraints and trainability issues such as barren plateaus, making large-scale instances intractable on noisy intermediate-scale quantum devices. In this paper, we propose an enhanced distributed variational quantum eigensolver for large-scale MaxCut problems, which extends our prior distributed variational quantum eigensolver framework by integrating a novel hybrid classical-quantum perturbation strategy, enhances optimization scalability and efficiency. Our algorithm solves weighted MaxCut instances with up to 1000 vertices using only 10 qubits, and numerical results indicate that it consistently outperforms the Goemans-Williamson algorithm. We further employ a warm-start initialization strategy, seeding the algorithm with high-quality solutions from the Goemans-Williamson algorithm, with results confirming that the optimal classical solution can be effectively further improved. The practical utility of the proposed algorithm is further validated through its application to haplotype phasing on genome sequencing data of the human ABCA1 gene, producing high-quality haplotypes that rival those obtained by the Goemans-Williamson algorithm with $10^6$ projections. These results establish the proposed algorithm as a scalable, NISQ-compatible framework for near-term quantum-enhanced large-scale combinatorial optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_22056 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem Lin, Yuefeng Wang, Kun Zheng, Qinyuan Zhang, Rui Fang, Jing-Kai Meng, Tiejun Xiang, Jingen Guo, Cong Huang, Jun-Han Quantum Physics MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algorithms offer promising new approaches that may eventually outperform classical schemes, they suffer from resource constraints and trainability issues such as barren plateaus, making large-scale instances intractable on noisy intermediate-scale quantum devices. In this paper, we propose an enhanced distributed variational quantum eigensolver for large-scale MaxCut problems, which extends our prior distributed variational quantum eigensolver framework by integrating a novel hybrid classical-quantum perturbation strategy, enhances optimization scalability and efficiency. Our algorithm solves weighted MaxCut instances with up to 1000 vertices using only 10 qubits, and numerical results indicate that it consistently outperforms the Goemans-Williamson algorithm. We further employ a warm-start initialization strategy, seeding the algorithm with high-quality solutions from the Goemans-Williamson algorithm, with results confirming that the optimal classical solution can be effectively further improved. The practical utility of the proposed algorithm is further validated through its application to haplotype phasing on genome sequencing data of the human ABCA1 gene, producing high-quality haplotypes that rival those obtained by the Goemans-Williamson algorithm with $10^6$ projections. These results establish the proposed algorithm as a scalable, NISQ-compatible framework for near-term quantum-enhanced large-scale combinatorial optimization. |
| title | Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2512.22056 |