Fetching the paper…
Reading the bibliography…
We experimentally study the performance of a programmable quantum annealing processor, the D-Wave One (DW1) with up to 108 qubits, on maximum satisfiability problem with 2 variables per clause (MAX 2-SAT) problems.
M. Davis and H. Putnam, J. ACM 7
1960
Earlier work this paper cites.
B. Aspvall, M. F. Plass, and R. E. Tarjan, Inf. Proc. Lett. 8
1979
Earlier work this paper cites.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220
1983
Earlier work this paper cites.
J. Feigenbaum and L. Fortnow, SIAM Journal on Computing 22
1993
Earlier work this paper cites.
A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Chem. Phys. Lett. 219
1994
Earlier work this paper cites.
C. Papadimitriou, Computational Complexity (Addison Wesley Longman, Reading, Massachusetts, 1995)
1995
Earlier work this paper cites.
M. Goemans and D. Williamson, J. Assoc. Comput. Mach. 42
1995
Earlier work this paper cites.
A. Goerdt, J. of Computer and System Sciences 53
1996
Earlier work this paper cites.
T. Kadowaki and H. Nishimori, Phys. Rev. E 58
1998
Earlier work this paper cites.
J. Brooke, D. Bitko, T. F., Rosenbaum, and G. Aeppli, Science 284
1999
Earlier work this paper cites.
Specifically, the biqmac algorithm Rendl et al. 2010 used in the spin glass server sgserver , exact belief propagation using bucket sort Dechter 1999 and a related divide-and-conquer algorithm
1999
Earlier work this paper cites.
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature 400
1999
Earlier work this paper cites.
M. Ajtai, in Proceedings of the 26th International Colloquium on Automata, Languages and Programming , ICAL ’99 (Springer-Verlag, London, UK, UK, 1999) pp. 1–9
1999
Earlier work this paper cites.
R. Dechter, Artificial Intelligence 113
1999
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, ArXiv (2000) , quant-ph/0001106 (2000)
2000
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292
2001
Earlier work this paper cites.
A. M. Childs, E. Farhi, and J. Preskill, Phys. Rev. A 65
2001
Earlier work this paper cites.
W. F. de la Vega, Theoretical Computer Science 265
2001
Earlier work this paper cites.
B. Bollobás, C. Borgs, J. T. Chayes, J. H. Kim, and D. B. Wilson, Random Struct. Algorithms 18
2001
Earlier work this paper cites.
J. Hàstad, Journal of the ACM (JACM) 48
2001
Earlier work this paper cites.
G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, Science 295
2002
Earlier work this paper cites.
R. Martoňák, G. E. Santoro, and E. Tosatti, Phys. Rev. B 66
2002
Earlier work this paper cites.
H. Shen and H. Zhag, Electronic Notes in Discrete Mathematics 16
2003
Earlier work this paper cites.
D. Coppersmith, D. Gamarnik, M. Hajiaghayi, and G. B. Sorkin, Random Structures and Algorithms 24
2004
Cited alongside, same era.
M. S. Siu, Phys. Rev. A 71
2005
Cited alongside, same era.
R. Oliveira and B. Terhal, Quantum Inf. Comput. 8
2005
Cited alongside, same era.
M. S. Sarandy and D. A. Lidar, Phys. Rev. Lett. 95
2005
Cited alongside, same era.
J. Roland and N. J. Cerf, Phys. Rev. A 71
2005
Cited alongside, same era.
D. A. Battaglia, G. E. Santoro, and E. Tosatti, Phys. Rev. E 71
2005
Cited alongside, same era.
J. Kempe, A. Kitaev, and O. Regev, SIAM Journal on Computing 35
A. J. Berkley, M. W. Johnson, P. Bunyk, R. Harris, J. Johansson, T. Lanting, E. Ladizinsky, E. Tolkacheva, M. H. S. Amin, and G. Rose, Superconductor Science and Technology 23
2010
Later among the works it cites.
M. W. Johnson, P. Bunyk, F. Maibaum, E. Tolkacheva, A. J. Berkley, E. M. Chapple, R. Harris, J. Johansson, T. Lanting, I. Perminov, E. Ladizinsky, T. Oh, and G. Rose, Superconductor Science and Technology 23
2010
Later among the works it cites.
F. Rendl, G. Rinaldi, and A. Wiegele, Mathematical Programming 121
2010
Later among the works it cites.
M.W. Johnson et al
2011
Later among the works it cites.
V. Choi, Quant. Inf. Proc. 10
2011
Later among the works it cites.
G. Quiroz and D. A. Lidar, Phys. Rev. A 86
2012
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2006
Cited alongside, same era.
S. P. Jordan, E. Farhi, and P. W. Shor, Phys. Rev. A 74
2006
Cited alongside, same era.
M. Lewin, D. Livnat, and U. Zwick, Integer Programming and Combinatorial Optimization , 67 (2006)
2006
Cited alongside, same era.
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, SIAM J. Comp. 37
2007
Cited alongside, same era.
A. Mizel, D. A. Lidar, and M. Mitchell, Phys. Rev. Lett. 99
2007
Cited alongside, same era.
M. Tiersch and R. Schützhold, Phys. Rev. A 75
2007
Cited alongside, same era.
Later among the works it cites.
G. A. Paz-Silva, A. T. Rezakhani, J. M. Dominy, and D. A. Lidar, Phys. Rev. Lett. 108
2012
Later among the works it cites.
K. C. Young and M. Sarovar, ArXiv e-prints (2012), arXiv:1208.6371 [quant-ph]
2012
Later among the works it cites.
A. Kuegel, in POS-10 , EPiC Series, Vol. 8, edited by D. L. Berre (EasyChair, 2012) pp. 15–27
2012
Later among the works it cites.
T. Albash, S. Boixo, D. A. Lidar, and P. Zanardi, New J. of Phys. 14
2012
Later among the works it cites.
Dickson, N. G. et al
2013
Closest in time.
S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor, and D. A. Lidar, Nature Comm. 4
2013
Closest in time.
2013
Closest in time.
2013
Closest in time.
C. C. McGeoch and C. Wang, in Proceedings of the 2013 ACM Conference on Computing Frontiers (2013)
2013
Closest in time.
In more detail, the McGeoch and Wang (MW) study McGeoch and Wang 2013 , working with the DW2, used a 439 439 qubit subgraph of Chimera and considered three problems: (1) Chimera-structured QUBO instances (this is actually an ensemble of uniform samples from the Ising model on Chimera with J i j , h j ∈ { − 1 , 1 } J_{ij},h_{j}\in\{-1,1\} Selby 2013 ), (2) Weighted Max 2-SAT, (3) the Quadratic Assignment Problem. Their main conclusion is that in their experiments the DW2 (together with a software layer called Blackbox) outperformed the software against which it was tested. In the case of problem (1), the DW2 is reported as outperforming its nearest rival (CPLEX), amongst those tried, by a factor of 3600 3600 . The times recorded by MW were for the first point that CPLEX found the optimal solution, and not the time at which it proved it optimality. However, several researchers have reported classical implementations for all three problems which outperform the DW2 and in particular the MW benchmarks Selby 2013 ; Puget 2013 . Our ensemble of MAX 2-SAT problems differs from the weighted MAX 2-SAT problems considered by MW, since we used uniform weights with the additional constraint of a fixed clause density. In addition, unlike MW’s case (2), our MAX 2-SAT problem ensemble inherits the native Chimera graph structure along with the connectivity contraints of the processor by design, which eliminates the need for using the Blackbox layer (that uses conventional heuristics along with hardware queries), resulting in a more transparent comparison. While we do not tune the implementation of akmaxsat
2013
Closest in time.
Annual Max-SAT Evaluations (2013)
2013
Closest in time.
M. H. Amin, N. G. Dickson, and P. Smith, Quantum Inf. Proc. 12
2013
Closest in time.
We note that Ref. S. Boixo et al. 2013 found that for an ensemble of Ising spin-glass problems the histogram of success probabilities solved using the DW1 was bimodal. This result agreed with predictions of a simulated quantum annealer, but differed from that of classical simulated annealing. The difference is most likely primarily due to the different annealing time, 5 μ 5\mu s in Ref. S. Boixo et al. 2013 compared to our 1 1 ms. While we did not vary the annealing time in the present study, Ref. S. Boixo et al. 2013 observed that a longer annealing time resulted in increasingly large fraction of problems being solved with high probability, thus shifting some of the weight of the distribution from the ‘hard’ (low success probability) problems to the ‘easy’ ones. Moreover, the ensemble of Ising spin glass problems considered in Ref. S. Boixo et al. 2013 differed from ours in several important ways. Their coupling strengths were randomly allowed to be only ± 1 \pm 1 with no fractional couplings. Another difference was that the couplings between two neighboring spins were completely independent of the local fields, unlike our Eq. ( 10
2013
Closest in time.
T. Lanting, D-Wave Inc., private communications (2013)
2013
Closest in time.
A. Selby, “D-Wave: comment on comparison with classical computers” (2013)
2013
Closest in time.
J.-F. Puget, “D-Wave vs CPLEX Comparison. Part 2: QUBO” (2013)
2013
Closest in time.