|
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.
|
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: chhzhu@xidian.edu.cn
|
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] |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
