将抽象论证中的难题转化为可被量子机求解的QUBO形式。
An encoding of argumentation problems using quadratic unconstrained binary optimization
- 把论证问题转为二元变量的二次优化问题，用矩阵表示系数。
- 在经典机、量子退火机上验证了方法正确性和有效性。
- 适合想用量子计算解决逻辑推理复杂问题的研究者。
本文提出一种将抽象论证中的多个NP完全问题编码为无约束二次二值优化（QUBO）问题的方法。该形式下，解是通过最小化关于二元变量（0/1）的二次函数得到，系数可用对称矩阵或其上三角版本表示。此编码使利用新型计算架构（如量子退火机与数字退火机）成为可能。相比传统近似求解器，本方法更适用于处理内在复杂性。我们通过实验验证了经典论证问题及论证集强制问题的正确性与适用性，并与文献中两种近似求解器进行对比。实验使用本地机器上的模拟退火算法，同时测试了来自D-Wave Ocean SDK和Leap量子云服务的量子退火机。
原文摘要 · Abstract (English)
In this paper, we develop a way to encode several NP-Complete problems in Abstract Argumentation to Quadratic Unconstrained Binary Optimization (QUBO) problems. In this form, a solution for a QUBO problem involves minimizing a quadratic function over binary variables (0/1), where the coefficients can be represented by a symmetric square matrix (or an equivalent upper triangular version). With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. A more conventional approach consists of developing approximate solvers, which, in this case, are used to tackle the intrinsic complexity. We performed tests to prove the correctness and applicability of classical problems in Argumentation and enforcement of argument sets. We compared our approach to two other approximate solvers in the literature during tests. In the final experimentation, we used a Simulated Annealing algorithm on a local machine. Also, we tested a Quantum Annealer from the D-Wave Ocean SDK and the Leap Quantum Cloud Service.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。