مقاله SAT ، Getgets ، Max2xor و Annealers Quantum

چکیده

Quantum Annealers are basically quantum computers that with high probability can optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state, with a high probability, after an annealing process. They have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e. as the problem of finding an assignment that maximizes the number of XOR clauses of at most 2 variables that are satisfied. In this paper, we present several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer.

چکیده به فارسی (ترجمه ماشینی)

آنیلرهای کوانتومی اساساً رایانه های کوانتومی هستند که با احتمال زیاد می توانند عملکردهای درجه دوم خاصی را در متغیرهای بولی در زمان ثابت بهینه کنند.این کارکردها اساساً پس از یک فرآیند بازپرداخت ، همیلتون مدل های ISING هستند که با احتمال زیاد به حالت انرژی زمین می رسند.آنها به عنوان راهی برای حل SAT پیشنهاد شده اند.این همیلتونیان را می توان به عنوان مشکلات Max2xor دانست ، یعنی به عنوان مشکل پیدا کردن تکلیف که تعداد بندهای XOR حداکثر 2 متغیر را برآورده می کند.در این مقاله ، ما چندین ابزار برای کاهش SAT به Max2xor ارائه می دهیم.ما نشان می دهیم که چگونه می توان از آنها برای ترجمه نمونه های SAT به تنظیمات اولیه آنیلر کوانتومی استفاده کرد.