Please wait a minute...
Chin. Phys. B, 2021, Vol. 30(4): 040305    DOI: 10.1088/1674-1056/abe29a
Special Issue: SPECIAL TOPIC — Quantum computation and quantum simulation
SPECIAL TOPIC—Quantum computation and quantum simulation Prev   Next  

Efficient self-testing system for quantum computations based on permutations

Shuquan Ma(马树泉)1, Changhua Zhu(朱畅华)1,2,†, Min Nie(聂敏)2,3, and Dongxiao Quan(权东晓)1
1 State Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China; 2 Shaanxi Key Laboratory of Information Communication Network and Security, Xi'an University of Posts & Telecommunications, Xi'an 710121, China; 3 School of Communications and Information Engineering, Xi'an University of Posts & Telecommunications, Xi'an 710121, China
Abstract  Verification in quantum computations is crucial since quantum systems are extremely vulnerable to the environment. However, verifying directly the output of a quantum computation is difficult since we know that efficiently simulating a large-scale quantum computation on a classical computer is usually thought to be impossible. To overcome this difficulty, we propose a self-testing system for quantum computations, which can be used to verify if a quantum computation is performed correctly by itself. Our basic idea is using some extra ancilla qubits to test the output of the computation. We design two kinds of permutation circuits into the original quantum circuit: one is applied on the ancilla qubits whose output indicates the testing information, the other is applied on all qubits (including ancilla qubits) which is aiming to uniformly permute the positions of all qubits. We show that both permutation circuits are easy to achieve. By this way, we prove that any quantum computation has an efficient self-testing system. In the end, we also discuss the relation between our self-testing system and interactive proof systems, and show that the two systems are equivalent if the verifier is allowed to have some quantum capacity.
Keywords:  quantum computation      verification      self-testing systems      complexity theory  
Received:  29 October 2020      Revised:  09 January 2021      Accepted manuscript online:  03 February 2021
PACS:  03.67.-a (Quantum information)  
  03.67.Ac (Quantum algorithms, protocols, and simulations)  
  03.67.Lx (Quantum computation architectures and implementations)  
Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 61372076, 61971348, and 62001351), Foundation of Shaanxi Key Laboratory of Information Communication Network and Security (Grant No. ICNS201802), Natural Science Basic Research Program of Shaanxi, China (Grant No. 2021JM-142), and Key Research and Development Program of Shaanxi Province, China (Grant No. 2019ZDLGY09-02).
Corresponding Authors:  Corresponding author. E-mail:   

Cite this article: 

Shuquan Ma(马树泉), Changhua Zhu(朱畅华), Min Nie(聂敏), and Dongxiao Quan(权东晓) Efficient self-testing system for quantum computations based on permutations 2021 Chin. Phys. B 30 040305

1 Deutsch D 1985 Proc. R. Soc. Lond. A 400 97
2 Feynman R P Int. J. Theor. Phys. 21 476
3 Yao X W, Xue F, Pang W M, et al. 2006 Chin. Phys. Lett. 23 1996
4 Feng Z B and Yan R Y 2010 Chin. Phys. Lett. 27 010301
5 Qü F M, Ji Z Q, Tian Y, et al. 2018 Chin. Phys. B 27 070301
6 Wu C, Fang M F, Xiao X, et al. 2011 Chin. Phys. B 20 020305
7 Xin T, Wang B X, Li K R, et al. 2018 Chin. Phys. B 27 020308
8 Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505
9 Gheorghiu A, Kapourniotis T and Kashefi E 2019 Theory of Computing Systems 63 715
10 Goldwasser S,Micali S and Rackoff C 1989 SIAM J. Comput. 18 186
11 Raussendorf R and Briegel H J 2001 Phys. Rev. Lett. 86 5188
12 Broadbent A, Fitzsimons J and Kashefi E 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, pp. 517-526
13 Kashefi E and Pappa A 2017 Cryptography 1 12
14 Cao X and Shang Y 2014 Chin. Phys. Lett. 31 110302
15 Diao D S 2013 Chin. Phys. Lett. 30 010303
16 Mayers D and Yao A arXiv:quant-ph/0307205
17 Magniez F, Mayers D, Mosca M and Ollivier H arXiv:quant-ph/0512111
19 Mckague M Theory of Computing 12 3
20 Fitzsimons J F and Kashefi E 2017 Phys. Rev. A 96 012303
22 Nielsen M and Chuang I2011 Quantum Computation and Quantum Information: 10th Anniversary Edition
23 Gottesman D arXiv:quant-ph/9807006
24 Broadbent A Theory of Computing 12 11
25 Goldreich O Electronic Colloquium on Computational Complexity
26 Rosgen B and Watrous J 20th Annual IEEE Conference on Computational Complexity, San Jose, CA, USA, pp. 344-354
27 Childs A M 2005 Quantum Info. Comput. 5 6
28 Mahadev U 59th Annual Symposium on Foundations of Computer Science, Paris, pp. 259-267
29 Cojocaru A, Colisson L, Kashefi E and Wallden, P 2019 Advances in Cryptology -ASIACRYPT 2019, pp. 615-645
30 Reichardt B W, Unger F and Vazirani U 2013 Nature 496 456
31 Gheorghiu A, Kashefi E and Wallden P 2015 New J. Phys. 17 083040
32 Morimae T and Koshiba T 2019 arXiv:1407.1636 [quant-ph]
[1] Quantum computation and simulation with superconducting qubits
Kaiyong He(何楷泳), Xiao Geng(耿霄), Rutian Huang(黄汝田), Jianshe Liu(刘建设), and Wei Chen(陈炜). Chin. Phys. B, 2021, 30(8): 080304.
[2] Quantum computation and simulation with vibrational modes of trapped ions
Wentao Chen(陈文涛), Jaren Gan, Jing-Ning Zhang(张静宁), Dzmitry Matuskevich, and Kihwan Kim(金奇奂). Chin. Phys. B, 2021, 30(6): 060311.
[3] Quantum computation and error correction based on continuous variable cluster states
Shuhong Hao(郝树宏), Xiaowei Deng(邓晓玮), Yang Liu(刘阳), Xiaolong Su(苏晓龙), Changde Xie(谢常德), and Kunchi Peng(彭堃墀). Chin. Phys. B, 2021, 30(6): 060312.
[4] Realization of arbitrary two-qubit quantum gates based on chiral Majorana fermions
Qing Yan(闫青) and Qing-Feng Sun(孙庆丰). Chin. Phys. B, 2021, 30(4): 040303.
[5] Quantum algorithm for a set of quantum 2SAT problems
Yanglin Hu(胡杨林), Zhelun Zhang(张哲伦), and Biao Wu(吴飙). Chin. Phys. B, 2021, 30(2): 020308.
[6] Low-temperature environments for quantum computation and quantum simulation
Hailong Fu(付海龙), Pengjie Wang(王鹏捷), Zhenhai Hu(胡禛海), Yifan Li(李亦璠), and Xi Lin(林熙). Chin. Phys. B, 2021, 30(2): 020702.
[7] A concise review of Rydberg atom based quantum computation and quantum simulation
Xiaoling Wu(吴晓凌), Xinhui Liang(梁昕晖), Yaoqi Tian(田曜齐), Fan Yang(杨帆), Cheng Chen(陈丞), Yong-Chun Liu(刘永椿), Meng Khoon Tey(郑盟锟), and Li You(尤力). Chin. Phys. B, 2021, 30(2): 020305.
[8] Quantum adiabatic algorithms using unitary interpolation
Shuo Zhang(张硕), Qian-Heng Duan(段乾恒), Tan Li(李坦), Xiang-Qun Fu(付向群), He-Liang Huang(黄合良), Xiang Wang(汪翔), Wan-Su Bao(鲍皖苏). Chin. Phys. B, 2020, 29(1): 010308.
[9] Novel quantum secret image sharing scheme
Gao-Feng Luo(罗高峰), Ri-Gui Zhou(周日贵), Wen-Wen Hu(胡文文). Chin. Phys. B, 2019, 28(4): 040302.
[10] Error-detected single-photon quantum routing using a quantum dot and a double-sided microcavity system
A-Peng Liu(刘阿鹏), Liu-Yong Cheng(程留永), Qi Guo(郭奇), Shi-Lei Su(苏石磊), Hong-Fu Wang(王洪福), Shou Zhang(张寿). Chin. Phys. B, 2019, 28(2): 020301.
[11] Experimental implementation of a continuous-time quantum random walk on a solid-state quantum information processor
Maimaitiyiming Tusun(麦麦提依明·吐孙), Yang Wu(伍旸), Wenquan Liu(刘文权), Xing Rong(荣星), Jiangfeng Du(杜江峰). Chin. Phys. B, 2019, 28(11): 110302.
[12] Direct measurement of the concurrence of hybrid entangled state based on parity check measurements
Man Zhang(张曼), Lan Zhou(周澜), Wei Zhong(钟伟), Yu-Bo Sheng(盛宇波). Chin. Phys. B, 2019, 28(1): 010301.
[13] Solid-state quantum computation station
Fanming Qu(屈凡明), Zhongqing Ji(姬忠庆), Ye Tian(田野), Shiping Zhao(赵士平). Chin. Phys. B, 2018, 27(7): 070301.
[14] Direct measurement of the concurrence for two-qubit electron spin entangled pure state based on charge detection
Liu Jiong, Zhou Lan, Sheng Yu-Bo. Chin. Phys. B, 2015, 24(7): 070309.
[15] Universal quantum computation using all-optical hybrid encoding
Guo Qi, Cheng Liu-Yong, Wang Hong-Fu, Zhang Shou. Chin. Phys. B, 2015, 24(4): 040303.
[2] TAO BI-XIU, TAO BI-YOU. DYNAMICS OF PLANAR RELATIVISTIC DOMAIN WALLS[J]. Acta Phys. Sin. (Overseas Edition), 1997, 6(5): 356 -360 .
[3] Gao Hong, Liu Sheng-gang. DISPERSION RELATION OF A MAGNETIZED PLASMA-FILLED BACKWARD WAVE OSCILLATOR[J]. Chin. Phys., 2000, 9(4): 274 -278 .
[4] Wang Cheng-Zhi, Fang Mao-Fa. Quantum entanglement in a two-dimensional ion trap[J]. Chin. Phys., 2003, 12(3): 287 -293 .
[5] Cao Quan-Jun, Zhang Yi-Men, Zhang Yu-Ming, Lü Hong-Liana, Wang Yue-Hu, Chang Yuan-Cheng, Tang Xiao-Yan. A CAD oriented quasi-analytical large-signal drain current model for 4H-SiC MESFETs[J]. Chin. Phys., 2007, 16(4): 1097 -1100 .
[6] W. B. Cardoso, A. T. Avelar, B.Baseia, N. G. de Almeida. Total teleportation of zero- and one-photon entangled states in running waves[J]. Chin. Phys. B, 2008, 17(1): 60 -63 .
[7] Gao Fei, Li Zhuo-Qiu, Tong Heng-Qing. Parameters estimation online for Lorenz system by a novel quantum-behaved particle swarm optimization[J]. Chin. Phys. B, 2008, 17(4): 1196 -1201 .
[8] Luan Su-Zhen, Liu Hong-Xia. Quantum compact model for thin-body double-gate Schottky barrier MOSFETs[J]. Chin. Phys. B, 2008, 17(8): 3077 -3082 .
[9] Cao Wen-Hui, Yu Hai-Feng, Tian Ye, Yu Hong-Wei, Ren Yu-Feng, Chen Geng-Hua, Zhao Shi-Ping. Nb/Al-AlOx/Nb junctions with controllable critical current density for qubit application[J]. Chin. Phys. B, 2009, 18(11): 5044 -5046 .
[10] Jin Zhang-Ying, Shen Bai-Fei, Zhang Xiao-Mei, Wang Feng-Chao, Ji Liang-Liang. Energetic-ion generation by the combination of laser pressure and Coulomb explosion[J]. Chin. Phys. B, 2009, 18(12): 5395 .