Solving Set Cover with Pairs Problem using Quantum Annealing
<p dir="ltr">Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology and biochemistry. We show an explicit construction of Ising Hamiltonians whose gr...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , |
| منشور في: |
2016
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513556444086272 |
|---|---|
| author | Yudong Cao (2407681) |
| author2 | Shuxian Jiang (32542) Debbie Perouli (7168103) Sabre Kais (1409968) |
| author2_role | author author author |
| author_facet | Yudong Cao (2407681) Shuxian Jiang (32542) Debbie Perouli (7168103) Sabre Kais (1409968) |
| author_role | author |
| dc.creator.none.fl_str_mv | Yudong Cao (2407681) Shuxian Jiang (32542) Debbie Perouli (7168103) Sabre Kais (1409968) |
| dc.date.none.fl_str_mv | 2016-09-27T03:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1038/srep33957 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/Solving_Set_Cover_with_Pairs_Problem_using_Quantum_Annealing/27101593 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Information and computing sciences Theory of computation Quantum annealing Set Cover with Pairs (SCP) NP-hard combinatorial optimization Ising Hamiltonians Schrödinger equation Chimera graphs |
| dc.title.none.fl_str_mv | Solving Set Cover with Pairs Problem using Quantum Annealing |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology and biochemistry. We show an explicit construction of Ising Hamiltonians whose ground states encode the solution of SCP instances. We numerically simulate the time-dependent Schrödinger equation in order to test the performance of quantum annealing for random instances and compare with that of simulated annealing. We also discuss explicit embedding strategies for realizing our Hamiltonian construction on the D-wave type restricted Ising Hamiltonian based on Chimera graphs. Our embedding on the Chimera graph preserves the structure of the original SCP instance and in particular, the embedding for general complete bipartite graphs and logical disjunctions may be of broader use than that the specific problem we deal with.</p><h2>Other Information</h2><p dir="ltr">Published in: Scientific Reports<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1038/srep33957" target="_blank">https://dx.doi.org/10.1038/srep33957</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_b9bd01d8e86d349810667d243cf05de3 |
| identifier_str_mv | 10.1038/srep33957 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/27101593 |
| publishDate | 2016 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | Solving Set Cover with Pairs Problem using Quantum AnnealingYudong Cao (2407681)Shuxian Jiang (32542)Debbie Perouli (7168103)Sabre Kais (1409968)Information and computing sciencesTheory of computationQuantum annealingSet Cover with Pairs (SCP)NP-hard combinatorial optimizationIsing HamiltoniansSchrödinger equationChimera graphs<p dir="ltr">Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology and biochemistry. We show an explicit construction of Ising Hamiltonians whose ground states encode the solution of SCP instances. We numerically simulate the time-dependent Schrödinger equation in order to test the performance of quantum annealing for random instances and compare with that of simulated annealing. We also discuss explicit embedding strategies for realizing our Hamiltonian construction on the D-wave type restricted Ising Hamiltonian based on Chimera graphs. Our embedding on the Chimera graph preserves the structure of the original SCP instance and in particular, the embedding for general complete bipartite graphs and logical disjunctions may be of broader use than that the specific problem we deal with.</p><h2>Other Information</h2><p dir="ltr">Published in: Scientific Reports<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1038/srep33957" target="_blank">https://dx.doi.org/10.1038/srep33957</a></p>2016-09-27T03:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1038/srep33957https://figshare.com/articles/journal_contribution/Solving_Set_Cover_with_Pairs_Problem_using_Quantum_Annealing/27101593CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/271015932016-09-27T03:00:00Z |
| spellingShingle | Solving Set Cover with Pairs Problem using Quantum Annealing Yudong Cao (2407681) Information and computing sciences Theory of computation Quantum annealing Set Cover with Pairs (SCP) NP-hard combinatorial optimization Ising Hamiltonians Schrödinger equation Chimera graphs |
| status_str | publishedVersion |
| title | Solving Set Cover with Pairs Problem using Quantum Annealing |
| title_full | Solving Set Cover with Pairs Problem using Quantum Annealing |
| title_fullStr | Solving Set Cover with Pairs Problem using Quantum Annealing |
| title_full_unstemmed | Solving Set Cover with Pairs Problem using Quantum Annealing |
| title_short | Solving Set Cover with Pairs Problem using Quantum Annealing |
| title_sort | Solving Set Cover with Pairs Problem using Quantum Annealing |
| topic | Information and computing sciences Theory of computation Quantum annealing Set Cover with Pairs (SCP) NP-hard combinatorial optimization Ising Hamiltonians Schrödinger equation Chimera graphs |