Finite Domain Constraint Satisfaction Using Quantum Computation
Finite Domain Constraint Satisfaction Using Quantum Computation
复制标题
使用量子计算满足有限域约束
DOI：
10.1007/3-540-45687-2_7
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
P. Jonsson
中科院分区：
文献类型：
--
作者：
Ola Angelsmark;Vilhelm Dahllöf;P. Jonsson
我们提出了一种用于有限域约束求解的量子算法，其中约束的数量为 2。它是完整的，运行时间为 O((d/2) n/2 )，其中 d 是变量域的大小，n 是变量的数量。对于 d = 3 的情况，我们提供了一种获得时间上限 O(8 n/8 ) ≃ O(1.2968 n ) 的方法。此外，对于 d = 5，上限也得到了改进。以稍微不同的方式使用此方法，我们可以在 O(1.2185 n ) 时间内确定 3-可色性。
We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in O((d/2) n/2 ) time, where d is size of the domain of the variables and n the number of variables. For the case of d = 3 we provide a method to obtain an upper time bound of O(8 n/8 ) ≃ O(1.2968 n ). Also for d = 5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185 n ) time.