Max 2-SAT with up to 108 qubits
Max 2-SAT with up to 108 qubits
复制标题
最多 2-SAT，最多 108 个量子位
DOI：
10.1088/1367-2630/16/4/045006
复制
发表时间：
2013
影响因子：
3.3
通讯作者：
Daniel A. Lidar
中科院分区：
文献类型：
--
作者：
S. Santra;G. Quiroz;Greg Ver Steeg;Daniel A. Lidar
We experimentally study the performance of a programmable quantum annealing processor, the D-Wave One (DW1) with up to 108 qubits, on maximum SAT problem with 2 variables per clause (MAX 2-SAT) problems.我们考虑以固定子句密度为特征的随机问题集合，这是一个我们在实验中通过其临界值进行调整的外部参数。我们证明 DW1 对子句密度的临界值很敏感。 DW1 结果经过验证，并与 akmaxsat（一种精确的、最先进的算法）进行比较。我们研究了两个求解器的相对性能以及它们在问题难度方面的相关性。我们发现 DW1 性能与问题大小的关系更佳，并且问题硬度相关性基本上不存在。我们讨论这种比较的相关性和局限性。
We experimentally study the performance of a programmable quantum annealing processor, the D-Wave One (DW1) with up to 108 qubits, on maximum SAT problem with 2 variables per clause (MAX 2-SAT) problems. We consider ensembles of random problems characterized by a fixed clause density, an external parameter which we tune through its critical value in our experiments. We demonstrate that the DW1 is sensitive to the critical value of the clause density. The DW1 results are verified and compared with akmaxsat, an exact, state-of-the-art algorithm. We study the relative performance of the two solvers and how they correlate in terms of problem hardness. We find that the DW1 performance scales more favorably with problem size and that problem hardness correlation is essentially non-existent. We discuss the relevance and limitations of such a comparison.