Analysis on Quantum-Inspired Computing and Algorithm for 8-puzzle

Abstract

Abstract:

Heuristic function in quantum-inspired computing for 8-puzzle was analyzed．The diversity of quantum coding was expounded．A quantum-inspired algorithm and computing strategies based on heuristic function was presented．Quantum counter and unitary transformation operation are used to complete quantum computing for 8-puzzle problem, and quantum counter is set to maximum extension depth value．It is discussed that quantum-inspired algorithm is compared with the classical algorithm．Finally, how to implement a quantum computer for the heuristic intelligent search is discussed further．

Key words: 8-puzzle, quantum-inspired algorithm, heuristic function, intelligent search

CLC Number:

O413.1

XU Jingming, RUAN Yue . Analysis on Quantum-Inspired Computing and Algorithm for 8-puzzle[J]. J4, 2015, 32(4): 459-465.

References

[1] Luis Domingues Tome Jardim Tarrataca.The quantum production system[D]. Universidade de Lisboa, Instituto Superior Tecnico,2013.http://web.ist.utl.pt/ luis.tarrataca/. [2] Mao Andrew, Ariel D. Procaccia, Chen Yiling. Better human computation through principled voting[C]. Proceedings of the 27th AAAI Conference on Artificial Intelligence,2013, Bellevue, Washington, USA. [3] Kevin Igwe, Nelishia Pillay, Christopher Rae.Solving the 8-Puzzle Problem Using Genetic Programming[C]. SAICSIT '13, October 07 - 09 2013, East London, South Africa. [4]Cai Zixing, Xu Guangyou. Artificial intelligence: principles & applications[M](the fourth edition)(人工智能及其应用(第四版)). Beijing: Tsinghua University Press, 2010,73-75(in Chinese). [5] Xu Jingming. Choice of heuristic function and analysis of heuristic power in intelligent search[J].Journal of Kunming University of Science and Technology(Science and Technology),2007,32(5):31-34(in Chinese). 许精明.智能搜索中启发函数的选择及启发能力分析[J].昆明理工大学学报(理工版),2007,32(5):31-34. [6] He Guangping. Quantum information made easy[M](通俗量子信息学).Beijing: Science Press,2012,15-18(in Chinese). [7] (Japanese)Zuo Chuan Hongxing,Ji Tian Xuanzhang.Song Heshan,Song Tian translated.Quantum information theory[M](量子信息论). Dalian: Dalian University of Technology Press, 2007(in Chinese). [8](America) A.Michael Nielsen, L.Isaac.Chuang.Zhao Qianchuan translated.Quantum computation and quantum information[M](量子计算和量子信息(一)、(二)). Beijing: Tsinghua University Press,2004(in Chinese). [9]Li Shiyong,Li Panchi.Quantum computation and quantum optimization algorithms[M](量子计算与量子优化算法).Harbin: Harbin Institute of Technology Press, 2009(in Chinese). [10]Liang Changyong,Bai Hua,Cai Meiju,et al.Advances in quantum genetic algorithm[J].Application Research of Computers,2012,29(7):2401-2405(in Chinese). 梁昌勇,柏桦,蔡美菊等.量子遗传算法研究进展[J].计算机应用研究,2012,29(7):2401-2405. [11]Meng Xiangping, Pi Yuzhen, Zhao Liang.A novel artifical neural network training method based on quantum computational multi-agent[J].Computer Simulation,2011,28(11):161-184(in Chinese). 孟祥萍,皮玉珍,赵亮.基于量子计算多Agent的人工神经网络训练方法[J].计算机仿真, 2011,28(11):161-184. [12] K. Aoki, Y. Yamanashi, and N. Yoshikawa. Multiplexing Techniques of Single Flux Quantum Circuit Based Readout Circuit for a Multi-Channel Sensing System. IEEE Transactions on Applied Superconductivity, 2013,23(3). [13] Yang Shuyuan, Liu Fang, Jiao Licheng. Quantum evolutionary strategies[J].Acta Electronica Sinica,2001, 29(12A):1873-1877(in Chinese). 杨淑媛,刘芳,焦李成.量子进化策略[J].电子学报,2001, 29(12A):1873-1877. [14] Jeremy Hsu. Scientists Confirm D-Wave's Computer Chips Compute Using Quantum Mechanics[OL]. http://spectrum.ieee.org/tech-talk/computing/hardware/scientists-confirm-dwave-computer-chips-compute-using- quantum-mechanics. [15] Sandip Dey, Indrajit Saha and Ujjwal Maulik, Siddhartha Bhattacharyya. New Quantum Inspired Meta-heuristic Methods for Multi-level Thresholding. International Conference on Advances in Computing, Communications and Informatics(ICACCI), Myore,India,2013. [16]Tie Han and Pieter Jonker. On Quantum Computing with Macroscopic Josephson Qubits.Proceedings of the 2002 2nd IEEE Conference on Nanotechnology (Cat. No.02TH8630),305-308.