Search Algorithm Based on Permutation Group by Quantum Walk on Hypergraphes

JIANG Yaoyao; CHU Pengcheng; MA Yulin; MA Hongyang

doi:10.1049/cje.2021.00.125

Volume 31 Issue 4

Jul. 2022

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2022 > 31(4): 626-634

JIANG Yaoyao, CHU Pengcheng, MA Yulin, et al., “Search Algorithm Based on Permutation Group by Quantum Walk on Hypergraphes,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 626-634, 2022, doi: 10.1049/cje.2021.00.125

Citation:

JIANG Yaoyao, CHU Pengcheng, MA Yulin, et al., “Search Algorithm Based on Permutation Group by Quantum Walk on Hypergraphes,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 626-634, 2022, doi: 10.1049/cje.2021.00.125

Citation:

PDF( 4065 KB)

Search Algorithm Based on Permutation Group by Quantum Walk on Hypergraphes

doi: 10.1049/cje.2021.00.125

1.
School of Science, Qingdao University of Technological, Qingdao 266033, China
2.
School of Information and Control Engineering, Qingdao University of Technology, Qingdao 266033, China

Funds: This work was supported by the National Natural Science Foundation of China (11975132, 61772295), the Natural Science Foundation of Shandong Province, China (ZR2019YQ01), and the Project of Shandong Province Higher Educational Science and Technology Program (J18KZ012)

More Information

Author Bio:
received the B.S. degree from Jinan University. She is currently studying for an M.S. degree in the Quantum Physics Laboratory of Qingdao University of Technology, and is mainly engaged in quantum search algorithms, quantum communication, and quantum machine learning.(Email: Jiangyaoyao_yy@163.com)

received the B.S. degree from East China University of Science and Technology, Shanghai, China, in 2005, and the Ph.D. degree in computer science and technology from Shanghai Jiao Tong University, Shanghai, China. He is currently a Professor at the School of Sciences, Qingdao University of Technology. His research interests mainly include quantum network, wireless network, and information security. (Email: kyois@126.com)

received the B.S. degree from Qingdao University of Technology and is currently pursuing the M.S. degree in Quantum Physics Laboratory of Qingdao University of Technology. He mainly engaged in quantum communication, quantum image processing, and quantum machine learning.(Email: mayulin6466@163.com)

(corresponding author) is currently a Professor at the School of Sciences, Qingdao University of Technology. He received the M.S. and Ph.D. degrees in computer science and technology from the Ocean University of China, Qingdao, China. His research interests mainly include quantum network, wireless network, and information security. (Email: hongyang_ma@aliyun.com)
Received Date: 2021-04-12
Accepted Date: 2021-10-23

Available Online: 2021-12-14

Publish Date: 2022-07-05

Abstract

Abstract

Because a significant number of algorithms in computational science include search challenges and a large number of algorithms that can be transformed into search problems have garnered significant attention, especially the time rate and accuracy of search, a quantum walk search algorithm on hypergraphs, whose aim is to reduce time consumption and increase the readiness and controllability of search, is proposed in this paper. First, the data points are divided into groups and then isomorphic to the permutation set. Second, the element coordinates in the permutation set are adopted to mark the position of the data points. Search the target data by the controllable quantum walk with multiparticle on the ring. By controlling the coin operator of quantum walk, it is determined that search algorithm can increase the accuracy and controllability of search. It is determined that search algorithm can reduce time consumption by increasing the number of search particles. It also provides a new direction for the design of quantum walk algorithms, which may eventually lead to entirely new algorithms.
- Search algorithm,
- Quantum walk,
- Permutation groups

FullText(HTML)

References(28)

References

[1]	Y. Q. Cai, X. W. Lu, and N. Jiang, “A survey on quantum image processing,” Chinese Journal of Electronics, vol.27, no.4, pp.718–727, 2018. doi: 10.1049/cje.2018.02.012
[2]	J. Li, N. Li, and Y. Zhang, et al., “A survey on quantum cryptography,” Chinese Journal of Electronics, vol.27, no.2, pp.223–228, 2018. doi: 10.1049/cje.2018.01.017
[3]	S. Wang, X. H. Song, and X. Niu, “Quantum computation and decision trees,” Chinese Journal of Electronics, vol.24, no.2, pp.321–325, 2015. doi: 10.1049/cje.2015.04.016
[4]	Y. Xiong, X. Liang, and F. Y. Miao, “A novel Pauli evolutionary quantum algorithm for combinatorial optimization,” Chinese Journal of Electronics, vol.19, no.3, pp.399–402, 2010.
[5]	J. Y. Peng and H. X. Lei, “Cyclic remote implementation of partially unknown quantum operations,” Chinese Journal of Electronics, vol.30, no.2, pp.378–383, 2021. doi: 10.1049/cje.2021.02.010
[6]	E. Farhi and S. Gutmann, “Quantum computation and decision trees,” Phys. Rev. A., vol.58, article no.915, 1998. doi: 10.1103/PhysRevA.58.915
[7]	Y. Aharonov, D. Luiz, and Z. Nicim, “Quantum random walks,” Phys. Rev. A., vol.48, no.2, pp.1687–1690, 1993. doi: 10.1103/PhysRevA.48.1687
[8]	C. Godsil, S. Kirkland, and S. Severini, et al., “Number-theoretic nature of communication in quantum spin systems,” Phys. Rev. L., vol.109, article no.050502, 2012. doi: 10.1103/PhysRevLett.109.050502
[9]	S. Bose, “Quantum communication through an unmodulated spin chain,” Phys. Rev. L., vol.91, no.20, article no.207901, 2003. doi: 10.1103/PhysRevLett.91.207901
[10]	A. M. Childs, “Universal computation by quantum walk,” Phys. Rev. L., vol.102, article no.180501, 2009. doi: 10.1103/PhysRevLett.102.180501
[11]	A. M. Childs, “On the relationship between continuous- and discrete-time quantum walk,” Commun. Math. Phys., vol.294, pp.581–603, 2010. doi: 10.1007/s00220-009-0930-1
[12]	D. Bacon and W. V. Dam, “Recent progress in quantum algorithms,” Communications of the ACM, vol.53, pp.84–93, 2010.
[13]	A. Patel and M. A. Rahaman, “Search on a hypercubic lattice using a quantum random walk,” Phys. Rev. A., vol.82, article no.032330, 2010. doi: 10.1103/PhysRevA.82.032330
[14]	S. D. Berry and J. B. Wang, “Two-particle quantum walks: Entanglement and graph isomorphism testing,” Phys. Rev. A., vol.83, article no.042317, 2011. doi: 10.1103/PhysRevA.83.042317
[15]	V. Potoček, A. Gábris, and T. Kiss, “Optimized quantum random-walk search algorithms on the hypercube,” Phys. Rev. A., vol.79, article no.012325, 2009. doi: 10.1103/PhysRevA.79.012325
[16]	A. Schreiber, K. N. Cassemiro, and V. Potoček, “Photons walking the line: A quantum walk with adjustable coin operations,” Phys. Rev. L., vol.104, article no.050502, 2010. doi: 10.1103/PhysRevLett.104.050502
[17]	F. Zaghringer, G. Kirchmair, and R. Gerritsma, “Realization of a quantum walk with one and two trapped ions,” Phys. Rev. L., vol.104, article no.100503, 2010. doi: 10.1103/PhysRevLett.104.100503
[18]	L. Sansoni, F. Sciarrino, and G. Vallone, “Two-particle bosonic-fermionic quantum walk via integrated photonics,” Phys. Rev. L., vol.108, article no.010502, 2012. doi: 10.1103/PhysRevLett.108.010502
[19]	B. Kollár, T. Kiss, J. Novotn’y, et al., “Asymptotic dynamics of coined quantum walks on percolation graphs,” Physical Review Letters, vol.108, no.23, article no.230505, 2012. doi: 10.1103/PhysRevLett.108.230505
[20]	O. Mülken and A. Blumen, “Continuous-time quantum walks: Models for coherent transport on complex networks,” Physics Reports, vol.502, pp.37–87, 2011. doi: 10.1016/j.physrep.2011.01.002
[21]	F. Caruso, “QSTAR. Universally optimal noisy quantum walks on complex networks,” New J. Phys., vol.16, article no.055015, 2014. doi: 10.1088/1367-2630/16/5/055015
[22]	N. Shenvi, J. Kempe, and W. K. Birgitta, “Quantum random-walk search algorithm,” Phys. Rev. A, vol.67, article no.052307, 2003. doi: 10.1103/PhysRevA.67.052307
[23]	H. Y. Ma, Z. Xin, P. G. Xu, et al., “Quantum secure primary communication based on quantum information compression,” Wireless Personal Communications, vol.113, pp.2203–2214, 2020. doi: 10.1007/s11277-020-07319-w
[24]	V. Dunjko and H. J. Briegel, “Quantum mixing of Markov chains for special distributions,” New Journal of Physics, vol.17, article no.073004, 2015. doi: 10.1088/1367-2630/17/7/073004
[25]	D. Orsucci, H. J. Briegel, and V. Dunjko, “Faster quantum mixing for slowly evolving sequences of Markov Chains,” Quantum, vol.2, article no.105, 2018. doi: 10.22331/q-2018-11-09-105
[26]	S. Chakraborty, L. Novo, A. Ambainis, et al., “Spatial search by quantum walk is optimal for almost all graphs,” Physical Review Letters, vol.116, no.10, article no.100501, 2016. doi: 10.1103/PhysRevLett.116.100501
[27]	S. Chakraborty, L. Novo, S. D. Giorgio, et al., “Optimal quantum spatial search on random temporal networks,” Physical Review Letters, vol.119, no.22, article no.220503, 2017. doi: 10.1103/PhysRevLett.119.220503
[28]	A. Glos, A. Krawiec, R. Kukulski, et al., “Vertices cannot be hidden from quantum spatial search for almost all random graphs,” Quantum Information Processing, vol.17, no.4, pp.1–15, 2018.