An investigation of IBM quantum computing device performance on combinatorial optimisation problems.
Saved in:
| Title: | An investigation of IBM quantum computing device performance on combinatorial optimisation problems. |
|---|---|
| Authors: | Khumalo, Maxine T.1 (AUTHOR) 1604282@students.wits.ac.za, Chieza, Hazel A.1 (AUTHOR) 1609247@students.wits.ac.za, Prag, Krupa1 (AUTHOR) krupa.prag@wits.ac.za, Woolway, Matthew2 (AUTHOR) mjwoolway@uj.ac.za |
| Source: | Neural Computing & Applications. Jan2025, Vol. 37 Issue 2, p611-626. 16p. |
| Subjects: | Quadratic assignment problem, Optimization algorithms, Combinatorial optimization, Mathematical optimization, Traveling salesman problem |
| Abstract: | The intractability of deterministic solutions in solving NP -Hard Combinatorial Optimisation Problems (COP) is well reported in the literature. One mechanism for overcoming this difficulty has been the use of efficient COP non-deterministic approaches. However, with the advent of quantum technology, these modern devices' potential to overcome this tractability limitation requires exploration. This paper juxtaposes classical and quantum optimisation algorithms' performance to solve two common COP, namely the Travelling Salesman Problem and the Quadratic Assignment Problem. Two accepted classical optimisation methods, Branch and Bound and Simulated Annealing, are compared to two quantum optimisation methods, Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate Optimisation Algorithm (QAOA). These algorithms are, respectively, executed on both classical devices and IBM's suite of Noisy Intermediate-Scale Quantum (NISQ) devices. We have encoded the COP problems for the respective technologies and algorithms and provided the computational encodings for the NISQ devices. Our experimental results show that current classical devices significantly outperform the presently available NISQ devices, which both agree with and extend on those findings reported in the literature. Further, we introduce additional performance metrics to better compare the two approaches with respect to computational time, feasibility and solution quality. Our results show that the VQE performs better than QAOA with respect to these metrics, and we infer that this is due to the increased number of operations required. Additionally, we investigate the impact of a new set of basis gates on the quantum optimisation techniques and show they yield no notable improvement on obtained results. Finally, we highlight the present shortcomings of state-of-the-art NISQ IBM quantum devices and argue for continued future work on improving evolving devices. [ABSTRACT FROM AUTHOR] |
| Copyright of Neural Computing & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 182467431 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: An investigation of IBM quantum computing device performance on combinatorial optimisation problems. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Khumalo%2C+Maxine+T%2E%22">Khumalo, Maxine T.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> 1604282@students.wits.ac.za</i><br /><searchLink fieldCode="AR" term="%22Chieza%2C+Hazel+A%2E%22">Chieza, Hazel A.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> 1609247@students.wits.ac.za</i><br /><searchLink fieldCode="AR" term="%22Prag%2C+Krupa%22">Prag, Krupa</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> krupa.prag@wits.ac.za</i><br /><searchLink fieldCode="AR" term="%22Woolway%2C+Matthew%22">Woolway, Matthew</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> mjwoolway@uj.ac.za</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Neural+Computing+%26+Applications%22">Neural Computing & Applications</searchLink>. Jan2025, Vol. 37 Issue 2, p611-626. 16p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Quadratic+assignment+problem%22">Quadratic assignment problem</searchLink><br /><searchLink fieldCode="DE" term="%22Optimization+algorithms%22">Optimization algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+optimization%22">Combinatorial optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Traveling+salesman+problem%22">Traveling salesman problem</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: The intractability of deterministic solutions in solving NP -Hard Combinatorial Optimisation Problems (COP) is well reported in the literature. One mechanism for overcoming this difficulty has been the use of efficient COP non-deterministic approaches. However, with the advent of quantum technology, these modern devices' potential to overcome this tractability limitation requires exploration. This paper juxtaposes classical and quantum optimisation algorithms' performance to solve two common COP, namely the Travelling Salesman Problem and the Quadratic Assignment Problem. Two accepted classical optimisation methods, Branch and Bound and Simulated Annealing, are compared to two quantum optimisation methods, Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate Optimisation Algorithm (QAOA). These algorithms are, respectively, executed on both classical devices and IBM's suite of Noisy Intermediate-Scale Quantum (NISQ) devices. We have encoded the COP problems for the respective technologies and algorithms and provided the computational encodings for the NISQ devices. Our experimental results show that current classical devices significantly outperform the presently available NISQ devices, which both agree with and extend on those findings reported in the literature. Further, we introduce additional performance metrics to better compare the two approaches with respect to computational time, feasibility and solution quality. Our results show that the VQE performs better than QAOA with respect to these metrics, and we infer that this is due to the increased number of operations required. Additionally, we investigate the impact of a new set of basis gates on the quantum optimisation techniques and show they yield no notable improvement on obtained results. Finally, we highlight the present shortcomings of state-of-the-art NISQ IBM quantum devices and argue for continued future work on improving evolving devices. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Neural Computing & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=182467431 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00521-022-07438-4 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 16 StartPage: 611 Subjects: – SubjectFull: Quadratic assignment problem Type: general – SubjectFull: Optimization algorithms Type: general – SubjectFull: Combinatorial optimization Type: general – SubjectFull: Mathematical optimization Type: general – SubjectFull: Traveling salesman problem Type: general Titles: – TitleFull: An investigation of IBM quantum computing device performance on combinatorial optimisation problems. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Khumalo, Maxine T. – PersonEntity: Name: NameFull: Chieza, Hazel A. – PersonEntity: Name: NameFull: Prag, Krupa – PersonEntity: Name: NameFull: Woolway, Matthew IsPartOfRelationships: – BibEntity: Dates: – D: 11 M: 01 Text: Jan2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 09410643 Numbering: – Type: volume Value: 37 – Type: issue Value: 2 Titles: – TitleFull: Neural Computing & Applications Type: main |
| ResultId | 1 |
