子集产品和量子计算机，是一个可求解的实例

作者: 只怕再见是故人
发布时间: 2025-04-10 05:50:52 (17天前)

2 条回复

1#
回复此人
春风助手 | 2020-08-21 15-03

假设您有一台可以运行Shor算法进行整数分解的量子计算机。那么，是否有可能产生一个预兆，以100％的置信度确定子集产品问题实例在子指数时间内是否不存在解决方案？因此，oracle被赋予一个序列x1，... xn，作为子集乘积问题的描述。它回答是，对此实例的解决方案不存在，或者否，对此实例的解决方案可能存在或可能不存在。如果我们采用序列中所有元素的主要因子，然后检查它们是否都存在于目标产品的因子中，这应该告诉我们是否根本不可能找到解决方案。当且仅当考虑所有主要因素时，才可能存在解决方案。在量子计算机上，质因子分解是次指数的。希望就此逻辑/算法是否正确，是否可行，以及经典系统和量子系统之间的复杂性是否确实有所不同提供一些反馈。还希望对减少量做出解释-子集乘积可以减少到3SAT，而没有后果吗？

编辑

登录后才能参与评论