Robust Quantum Search with Uncertain Number of Target States
The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-12-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/23/12/1649 |
| _version_ | 1797504911769862144 |
|---|---|
| author | Yuanye Zhu Zeguo Wang Bao Yan Shijie Wei |
| author_facet | Yuanye Zhu Zeguo Wang Bao Yan Shijie Wei |
| author_sort | Yuanye Zhu |
| collection | DOAJ |
| description | The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mo>=</mo><msqrt><mrow><mi>M</mi><mo>/</mo><mi>N</mi></mrow></msqrt></mrow></semantics></math></inline-formula>, where <i>M</i> is the number of marked state and <i>N</i> is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced open="(" close=")"><msqrt><mi>N</mi></msqrt></mfenced></mrow></semantics></math></inline-formula> as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>M</mi><mo>/</mo><mi>N</mi></mrow></semantics></math></inline-formula>. In particular, for a database with an uncertainty in the ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mrow><mi>M</mi><mo>±</mo><msqrt><mi>M</mi></msqrt></mrow><mi>N</mi></mfrac></semantics></math></inline-formula>, our algorithm will find the target states with a success rate no less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>96</mn><mo>%</mo></mrow></semantics></math></inline-formula>. |
| first_indexed | 2024-03-10T04:11:09Z |
| format | Article |
| id | doaj.art-6b5d719d4f654389a42963fe9308c128 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T04:11:09Z |
| publishDate | 2021-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-6b5d719d4f654389a42963fe9308c1282023-11-23T08:11:08ZengMDPI AGEntropy1099-43002021-12-012312164910.3390/e23121649Robust Quantum Search with Uncertain Number of Target StatesYuanye Zhu0Zeguo Wang1Bao Yan2Shijie Wei3State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, ChinaState Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, ChinaState Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, ChinaState Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, ChinaThe quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mo>=</mo><msqrt><mrow><mi>M</mi><mo>/</mo><mi>N</mi></mrow></msqrt></mrow></semantics></math></inline-formula>, where <i>M</i> is the number of marked state and <i>N</i> is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced open="(" close=")"><msqrt><mi>N</mi></msqrt></mfenced></mrow></semantics></math></inline-formula> as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>M</mi><mo>/</mo><mi>N</mi></mrow></semantics></math></inline-formula>. In particular, for a database with an uncertainty in the ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mrow><mi>M</mi><mo>±</mo><msqrt><mi>M</mi></msqrt></mrow><mi>N</mi></mfrac></semantics></math></inline-formula>, our algorithm will find the target states with a success rate no less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>96</mn><mo>%</mo></mrow></semantics></math></inline-formula>.https://www.mdpi.com/1099-4300/23/12/1649quantum algorithmquantum computationquantum information |
| spellingShingle | Yuanye Zhu Zeguo Wang Bao Yan Shijie Wei Robust Quantum Search with Uncertain Number of Target States Entropy quantum algorithm quantum computation quantum information |
| title | Robust Quantum Search with Uncertain Number of Target States |
| title_full | Robust Quantum Search with Uncertain Number of Target States |
| title_fullStr | Robust Quantum Search with Uncertain Number of Target States |
| title_full_unstemmed | Robust Quantum Search with Uncertain Number of Target States |
| title_short | Robust Quantum Search with Uncertain Number of Target States |
| title_sort | robust quantum search with uncertain number of target states |
| topic | quantum algorithm quantum computation quantum information |
| url | https://www.mdpi.com/1099-4300/23/12/1649 |
| work_keys_str_mv | AT yuanyezhu robustquantumsearchwithuncertainnumberoftargetstates AT zeguowang robustquantumsearchwithuncertainnumberoftargetstates AT baoyan robustquantumsearchwithuncertainnumberoftargetstates AT shijiewei robustquantumsearchwithuncertainnumberoftargetstates |