Solving Set Cover with Pairs Problem using Quantum Annealing.
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.
Department of Computer Science, Purdue University, West Lafayette, IN 47906, USA.
Yudong
Y
Cao
Department of Computer Science, Purdue University, West Lafayette, IN 47906, USA.
Shuxian
S
Jiang
Department of Mathematics, Statistics and Computer Science, Marquette University, Milwaukee, WI 53233, USA.
Debbie
D
Perouli
Department of Chemistry, Physics and Birck Nanotechnology Center, Purdue University, West Lafayette, IN 47906, USA.|Qatar Energy and Environment Research Institute (QEERI), HBKU, Doha, Qatar.
Sabre
S
Kais
Nat Commun. 2013;4:1903
23695697
Nat Commun. 2013;4:2067
23811779
Nature. 2011 May 12;473(7346):194-8
21562559
Phys Rev Lett. 2012 Jan 6;108(1):010501
22304248
Science. 2002 Mar 29;295(5564):2427-30
11923532
Sci Rep. 2014 Jul 16;4:5703
25029660
Phys Rev Lett. 2012 Jun 8;108(23):230506
23003933
Science. 2001 Apr 20;292(5516):472-5
11313487
Phys Rev Lett. 2013 Sep 27;111(13):130505
24116761
Phys Rev Lett. 2015 Dec 4;115(23):230501
26684103
Sci Rep. 2012;2:571
22891157
Phys Rev Lett. 2008 Nov 28;101(22):220405
19113467
Science. 1983 May 13;220(4598):671-80
17813860
Sci Rep. 2016 Mar 03;6:22318
26936311
Science. 2015 Apr 10;348(6231):215-7
25765071
Science. 2014 Jul 25;345(6195):420-4
25061205
Sci Rep. 2016 Jan 19;6:18628
26783120
Phys Rev Lett. 2012 Aug 3;109(5):050501
23006152