Efficient self-testing system for quantum computations based on permutations  

作　　者：Shuquan Ma Changhua Zhu Min Nie Dongxiao Quan 马树泉;朱畅华;聂敏;权东晓(State Key Laboratory of Integrated Services Networks,Xidian University,Xi'an 710071,China;Shaanxi Key Laboratory of Information Communication Network and Security,Xi'an University of Posts&Telecommunications,Xi'an 710121,China;School of Communications and Information Engineering,Xi'an University of Posts&Telecommunications,Xi'an 710121,China)

机构地区：[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

出　　处：《Chinese Physics B》2021年第4期61-73,共13页中国物理B（英文版）

基　　金：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);Key Research and Development Program of Shaanxi Province,China(Grant No.2019ZDLGY09-02)。

摘　　要：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.

关 键 词：quantum computation VERIFICATION self-testing systems complexity theory 

分 类 号：TP38[自动化与计算机技术—计算机系统结构]