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] High-fidelity universal quantum gates for hybrid systems via the practical photon scattering
Jun-Wen Luo(罗竣文) and Guan-Yu Wang(王冠玉). Chin. Phys. B, 2023, 32(3): 030303.
[2] Analysis and improvement of verifiable blind quantum computation
Min Xiao(肖敏) and Yannan Zhang(张艳南). Chin. Phys. B, 2022, 31(5): 050305.
[3] Optimized quantum singular value thresholding algorithm based on a hybrid quantum computer
Yangyang Ge(葛阳阳), Zhimin Wang(王治旻), Wen Zheng(郑文), Yu Zhang(张钰), Xiangmin Yu(喻祥敏), Renjie Kang(康人杰), Wei Xin(辛蔚), Dong Lan(兰栋), Jie Zhao(赵杰), Xinsheng Tan(谭新生), Shaoxiong Li(李邵雄), and Yang Yu(于扬). Chin. Phys. B, 2022, 31(4): 048704.
[4] Molecular beam epitaxy growth of quantum devices
Ke He(何珂). Chin. Phys. B, 2022, 31(12): 126804.
[5] Quantum simulation and quantum computation of noisy-intermediate scale
Kai Xu(许凯), and Heng Fan(范桁). Chin. Phys. B, 2022, 31(10): 100304.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] Quantum algorithm for a set of quantum 2SAT problems
Yanglin Hu(胡杨林), Zhelun Zhang(张哲伦), and Biao Wu(吴飙). Chin. Phys. B, 2021, 30(2): 020308.
[11] 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.
[12] 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.
[13] 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.
[14] Novel quantum secret image sharing scheme
Gao-Feng Luo(罗高峰), Ri-Gui Zhou(周日贵), Wen-Wen Hu(胡文文). Chin. Phys. B, 2019, 28(4): 040302.
[15] 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.
No Suggested Reading articles found!