Quantum algorithm and experimental demonstration for the subset sum problem

Qilin Zheng

doi:10.1007/s11432-021-3334-1

Quantum algorithm and experimental demonstration for the subset sum problem

2021-12-13

8

PRE

AI

DOI：10.1007/s11432-021-3334-1

原文链接

原文求助

摘要

En 中文

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.

Keyword:

quantum algorithm

subset sum

quadratic speedup

encryption

algorithm complexity

Quantum algorithm and experimental demonstration for the subset sum problem

摘要

AI总结

期刊

机构