Deutsch-Jozsa algorithm realized on IBM Q

Abstract

Abstract: Deutsch-Jozsa algorithm realizes the exponential acceleration of classical algorithm for the first time, and solves the Deutsch problem of n qubits. The algorithm establishes the basic idea of quantum algorithms, and the implementation of which embodies the characteristics of quantum superposition and parallelism. A comprehensive algorithm is proposed for the first time, which can automatically generate all 8 truth tables and quantum circuits of 2-bit Deutsch-Jozsa algorithm. A synthesis method is given further to judge the properties of f(x) by constructing quantum circuit when the corresponding circuit is unknown. Generally, a typical classical algorithm solves this problem by doing 2n-1+1 times, and the Deutsch-Jozsa algorithm only needs one time. Although the new approach requires two steps to solve the problem, it provides another possible way to solve the problems with specific requirements in practical application. In addition, the correctness of the quantum circuits and Deutsch-Jozsa algorithm is verified by IBM Q Experience platform.

Key words: quantum information, Deutsch-Jozsa algorithm, quantum circuits, synthesis algorithm, IBM Q Experience

CLC Number:

O431.2

DAI Juan, LI Zhiqiang, PAN Suhan, ZHANG Wei, HU Jiajia. Deutsch-Jozsa algorithm realized on IBM Q[J]. Chinese Journal of Quantum Electronics, 2020, 37(2): 202-209.

References

[1] Zhang Hongtao, Xiong Hongmei, Tu Lingying, et al. Application of the quantum Fourier transform in Deutsch-Jozsa algorithm[J]. Journal of Huaqiao University(华侨大学学报) , 2016, 37(2): 155-159(in Chinese). [2] Sheng Mingyan, Cheng Xueyun, Guan Zhijin, et al. Realization method of two-dimensional nearest neighbor for quantum circuit[J]. Chinese Journal of Quantum Electronics(量子电子学报), 2019, 36(4): 477-482(in Chinese). [3] Reiche, Fritz. The Quantum Theory.[J]. The Journal of Physical Chemistry, 1932, 37(7):976-976. [4] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information [M]. 10th Anniversary Edition， Cambridge ： Cambridge University Press, 2011. [5] Nagata K . Implementation of the Deutsch-Jozsa algorithm violates nonlocal realism[J]. European Physical Journal D, 2010, 56(3):441-444. [6] Perez-Garcia B , Mclaren M , Goyal S K , et al. Quantum computation with classical light: Implementation of the Deutsch–Jozsa algorithm[J]. Physics Letters A,2016, 380(22-23):1925-1931. [7] Benenti G , Casati G , Strini G . Principles of Quantum Computation and Information: Basic Concepts v.1[M]. World Scientific, 2004. [8] Dieter H . Principles of quantum computation and information - volume i: basic concepts,[J]. Journal of Physics A Mathematical & Theoretical, 1926,(10): 256. [9] Zulehner A, Paler A, Wille R. An efficient methodology for mapping quantum circuits to the IBM QX architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018,38(7): 1226-1236. [10] Dong P, Song W, Cao Z L. Implementing Deutsch–Jozsa algorithm in cavity QED[J]. Communications in Theoretical Physics, 2006, 46(2): 241-243. [11] Dasgupta S, Biswas A, Agarwal G S. Implementing Deutsch-Jozsa algorithm using light shifts and atomic ensembles[J]. Physical Review A, 2005, 71(1): 012333. [12] Li Zhiqiang, Chen Hanwu, Xu Baowen, et al. Fast algorithms for synthesis of quantum reversible logic circuits based on Hash table[J]. Journal of Computer Research and Development(计算机研究与发展) , 2008, 45(12): 2162-2171 (in Chinese).

[1]	ZHU Mingqiang , SHEN Wenjie , NIU Yiren , ZHANG Chao , CHENG Xueyun , GUAN Zhijin , CHEN Liang. Reliability⁃oriented nearest neighbor synthesis of CNOT quantum circuits [J]. Chinese Journal of Quantum Electronics, 2023, 40(4): 560-569.
[2]	ZHANG Chao , GUAN Zhijin , FENG Shiguang , NIU Yiren , ZHU Mingqiang. A quantum circuit layout and optimization method in two⁃dimensional architecture [J]. Chinese Journal of Quantum Electronics, 2023, 40(4): 570-581.
[3]	JIA Wei , ZHANG Qiangqiang , BIAN Yuxiang , LI Wei . Research on the upper bound of collective attack in E91-QKD [J]. Chinese Journal of Quantum Electronics, 2023, 40(3): 407-414.
[4]	CAO Rui , YUAN Chengzhi , SHEN Si , ZHANG Zichang , FAN Yunru , LI Jiarui , LI Hao , YOU Lixing , ZHOU Qiang , WANG Zizhu ∗. Optimized detection of maximally entangled time-bin qutrits [J]. Chinese Journal of Quantum Electronics, 2023, 40(1): 85-94.
[5]	ZHAO Liangyuan , ∗ , CAO Lingyun , LIANG Hongyuan , WEI Zheng , WU Qianjun , QIAN Jianlin , HAN Zhengfu ∗. Research on wavelength-multiplexed quantum key distribution based on diﬀerent optical ﬁbers [J]. Chinese Journal of Quantum Electronics, 2022, 39(5): 776-785.
[6]	WU Xi, LI Zhiqiang∗. Circuit realization of Grover algorithm based on Cirq [J]. Chinese Journal of Quantum Electronics, 2022, 39(3): 431-438.
[7]	DAI Juan∗, LI Zhiqiang, YANG Donghan. Synthesis of Deutsch-Jozsa circuits based on Cirq [J]. Chinese Journal of Quantum Electronics, 2022, 39(3): 439-445.
[8]	WANG Fangxiang , , CHEN Wei , ∗. High-dimensional quantum key distribution based on orbital angular momentum photons: A review [J]. Chinese Journal of Quantum Electronics, 2022, 39(1): 64-80.
[9]	. Quantum secure multiparty summation based on Bell states [J]. Chinese Journal of Quantum Electronics, 2021, 38(6): 830-837.
[10]	TANG Shibiao∗, CHENG Jie, LI Shuai. Research on random number chip array scheme for quantum key distribution products [J]. Chinese Journal of Quantum Electronics, 2021, 38(4): 468-476.
[11]	FAN Yuteng, SUO Lei, ZHANG Chunhui, CHEN Jiaming, WANG Qin, ∗. Passive decoy-state quantum digital signature scheme based on linear optical components [J]. Chinese Journal of Quantum Electronics, 2021, 38(4): 485-495.
[12]	CHEN Menghan, GUO Gongde, LIN Song∗. Quantum recommendation algorithm based on Hamming distance [J]. Chinese Journal of Quantum Electronics, 2021, 38(3): 332-340.
[13]	YU Wei, ZHOU Yuanyuan, ZHOU Xuejun. Phase-matching decoy-state quantum key distribution scheme with weak coherent source [J]. Chinese Journal of Quantum Electronics, 2021, 38(1): 37-44.
[14]	GUO Mengqi, GONG Longyan∗. Quantum violation of I_{3322} inequality [J]. Chinese Journal of Quantum Electronics, 2021, 38(1): 50-56.
[15]	TANG Shibiao∗, CHENG Jie, LI Shuai. Research on random number source and real-time self-check scheme for high speed QKD system [J]. Chinese Journal of Quantum Electronics, 2021, 38(1): 86-93.