Solving SAT and MaxSAT with a Quantum Annealer: Foundations and a Preliminary Report
作者： Zhengbing Bian , Fabian Chudak , William Macready , Aidan Roy , Roberto Sebastiani
DOI: 10.1007/978-3-319-66167-4_9
关键词: Mathematics 、 Binary number 、 Maximum satisfiability problem 、 Qubit 、 Exponential growth 、 Quantum computer 、 Mathematical optimization 、 Quadratic equation 、 Quadratic unconstrained binary optimization 、 Quantum
摘要: Quantum annealers (QA) are specialized quantum computers that minimize objective functions over discrete variables by physically exploiting effects. Current QA platforms allow for the optimization of quadratic objectives defined binary variables, is, they solve unconstrained (QUBO) problems. In last decade, systems as implemented D-Wave have scaled with Moore-like growth. architectures provide 2048 sparsely-connected qubits, and continued exponential growth is anticipated.
springer.com
sci-hub.se 参考文章(34)
Roberto Sebastiani, Patrick Trentin, OptiMathSAT: A Tool for Optimization Modulo Theories Computer Aided Verification. pp. 447- 454 ,(2015) , 10.1007/978-3-319-21690-4_27
Vicky Choi, Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design Quantum Information Processing. ,vol. 10, pp. 343- 353 ,(2011) , 10.1007/S11128-010-0200-3
Michael Sipser, Jeffrey Goldstone, Sam Gutmann, Edward Farhi, Quantum Computation by Adiabatic Evolution arXiv: Quantum Physics. ,(2000)
Dave A. D. Tompkins, Holger H. Hoos, UBCSAT: An Implementation and Experimentation Environment for SLS Algorithms for SAT and MAX-SAT Theory and Applications of Satisfiability Testing. pp. 306- 320 ,(2005) , 10.1007/11527695_24
Alan Mishchenko, Robert Brayton, Satrajit Chatterjee, Roland Jiang, FRAIGs: A Unifying Representation for Logic Synthesis and Verification ,(2005)
William G. Macready, Jun Cai, Aidan Roy, A practical heuristic for finding graph minors arXiv: Quantum Physics. ,(2014)
T Lanting, R Harris, J Johansson, MHS Amin, AJ Berkley, S Gildert, MW Johnson, P Bunyk, E Tolkacheva, E Ladizinsky, N Ladizinsky, T Oh, I Perminov, EM Chapple, C Enderud, C Rich, B Wilson, MC Thom, S Uchaikin, G Rose, None, Cotunneling in pairs of coupled flux qubits Physical Review B. ,vol. 82, pp. 060512- ,(2010) , 10.1103/PHYSREVB.82.060512
Michael Gester, Dirk Müller, Tim Nieberg, Christian Panten, Christian Schulte, Jens Vygen, BonnRoute ACM Transactions on Design Automation of Electronic Systems. ,vol. 18, pp. 1- 24 ,(2013) , 10.1145/2442087.2442103
Rina Dechter, Bucket elimination: A unifying framework for reasoning Artificial Intelligence. ,vol. 113, pp. 41- 85 ,(1999) , 10.1016/S0004-3702(99)00059-4
Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos, Faster parameterized algorithms for minor containment Theoretical Computer Science. ,vol. 412, pp. 7018- 7028 ,(2011) , 10.1016/J.TCS.2011.09.015