子集產品和量子計算機，是一個可以解決的實例

Question

假設您有一臺可運行Shor算法的量子計算機，用於整數分解。

是否然後可能產生確定沒有辦法可以子集產品問題的一個實例，有100％的信心，在亞指數時間的預言？

因此，oracle給出了一個序列x1，... xn，作爲子集產品問題的描述。

它響應要麼是，這種情況下的解決方案並不存在，或沒有，這種情況下的解決方案可能會或可能不存在。

如果我們把序列中的所有元素，他首要因素，然後檢查是否所有的人都存在於目標產品的因素，這應該告訴我們，如果一個解決方案是不是在所有可能的。當且僅當所有素數因素都考慮在內時，才存在解決方案。在量子計算機上，素數因子分解是次指數的。

想上，如果這是正確的邏輯值，如果工程─如果複雜性是此Oracle /算法經典和量子系統之間確有不同的一些反饋。還會對減少量的解釋感到滿意 - 子集產品可以減少到3SAT而沒有後果嗎？

Answer 1

你的算法，如果我理解正確的話，將失敗的元素[6, 15]和目標10。這將決定6*15 = 2*3*3*5，裏面有所有的10=2*5使用的因素，並錯誤地斷言，這意味着你可以乘以6和15使10。

有兩個原因，它是不可能的，你就可以解決這個問題的算法：

1. Subset Product is NP-Complete。爲它找到一個多項式時間量子算法，或者表明不存在這樣的算法，可能與確定P = NP一樣困難。也就是說，非常非常難。

2. 你不想首要因素，你想要的「無必要對減少」的因素。例如，如果每次問題中的某個數字具有13的素數因子，則其伴隨有17的因子，則不需要將221分解爲13*17。您可以將Euclid的gcd算法應用於各種元素組合，以找到這些不需要減少的因素，而不需要量子性。