Name
Abstract | ||
|---|---|---|
To solve the subset sum problem, a well-known nondeterministic polynomial-time complete problem that is widely used in encryption and resource scheduling, we propose a feasible quantum algorithm that utilizes fewer qubits to encode and achieves quadratic speedup. Specifically, this algorithm combines an amplitude amplification algorithm with quantum phase estimation, and requires n + t + 1 qubits and O(2((0.5+o(1))n)) operations to obtain the solution, where n is the number of elements, and t is the number of qubits used to store the eigenvalues. To verify the performance of the algorithm, we simulate the algorithm with the online quantum simulator of IBM named ibmq_simulator using Qiskit and then run it on two IBM quantum computers called ibmq_santiago and ibmq_bogota. The experimental results indicate that compared with the brute force algorithm, the proposed algorithm results in quadratic acceleration for the problem of a set S with four elements and two subsets whose sum equals target w. Using the iterator twice, we obtain success probabilities of 0.940 +/- 0.004, 0.751 +/- 0.040, and 0.665 +/- 0.060 on the simulator, ibmq_santiago, and ibmq_bogota, respectively, and the fidelity between the theoretical and experimental quantum states is calculated to be 0.944 +/- 0.002, 0.753 +/- 0.017, and 0.657 +/- 0.028, respectively. If the error rates of the experimental quantum logic gates can be reduced, the success probabilities of the proposed algorithm on real quantum devices can be further improved. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s11432-021-3334-1 | SCIENCE CHINA-INFORMATION SCIENCES |
Keywords | DocType | Volume |
quantum algorithm, subset sum, quadratic speedup, encryption, algorithm complexity | Journal | 65 |
Issue | ISSN | Citations |
8 | 1674-733X | 0 |
PageRank | References | Authors |
0.34 | 0 | 11 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qilin Zheng | 1 | 0 | 0.34 |
| Pingyu Zhu | 2 | 0 | 0.34 |
| Shichuan Xue | 3 | 0 | 0.34 |
| Yang Wang | 4 | 394 | 61.44 |
| Chao Wu | 5 | 150 | 18.81 |
| Xinyao Yu | 6 | 13 | 1.45 |
| Miaomiao Yu | 7 | 0 | 0.68 |
| Yingwen Liu | 8 | 0 | 0.68 |
| Mingtang Deng | 9 | 0 | 0.34 |
| Junjie Wu | 10 | 551 | 47.60 |
| Ping Xu | 11 | 0 | 0.34 |