Survey of Verification Methods for Delegated Quantum Computation

doi:10.11871/jfdc.issn.2096-742X.2025.06.006

Abstract

Abstract:

[Objective] This paper systematically reviews and analyzes the research progress and current status of the verification methods for delegated quantum computation. [Coverage] This paper surveys 74 publications from mainstream conferences and journals spanning 1994 to 2025, covering core achievements and cutting-edge developments in quantum computing verification. [Methods] Classifying verification methods into three categories (weak quantum capability, entanglement, computational assumptions) based on client-side quantum capability requirements, we establish a taxonomy framework. By comparing communication patterns, overhead and fault tolerance, we distill evolutionary trends and comparative advantages of these approaches. [Results] Three complementary patterns emerge: weak-quantum-client schemes offer maturity but require client-side quantum capabilities; entanglement-based schemes need only classical clients but require multi-server collaboration; computational-assumption schemes feature minimal communication yet rely on post-quantum cryptography. Overhead decreases from exponential to near-linear complexity, though theoretical optimization is approaching asymptotic bottlenecks. [Conclusions] Research focus is shifting from theoretical optimization to practical deployment, urgently demanding cross-platform experimental validation and standardized protocols for multi-party delegated computation scenarios.

Key words: quantum computation, delegated computation, verification of computation, quantum cryptography

YUAN Zimeng,LONG Chun,LI Jing,YANG Fan,FU Yuhao,WEI Jinxia,WAN Wei. Survey of Verification Methods for Delegated Quantum Computation[J]. Frontiers of Data and Computing, 2025, 7(6): 55-67, https://cstr.cn/32002.14.jfdc.CN10-1649/TP.2025.06.006.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Comparison of verification protocols for delegated quantum computation based on traps"

验证方案	特点	容错性	资源开销
Fitzsimons与Kashefi^[23]	利用RHG方案^[24]插入陷阱	有	$O n 2$
Kashefi与Wallden^[25]	利用“三倍点缀”方法插入陷阱	无	线性级别
Ferracin等人^[26]	将资源态的某些量子比特替换为陷阱	无	线性级别
Leichtle等人^[27]	在Ferracin等人方案的基础上引入多数投票机制	有	线性级别

Table 1

Fig.5

Table 2

Comparison of verification protocols for delegated quantum computation based on stabilizer tests"

验证方案	验证的资源态类型	资源开销
Morimae^[31]	RHG态^[24]	指数级别
Hayashi与Morimae^[32]	一般图态	指数级别
Miller与Miyake^[33]	Union Jack态（超图态）	指数级别
Morimae等人^[34]	超边度数为2或3的超图态	$O n 21$
Takeuchi与Morimae^[35]	一般超图态	$O n 21$
Takeuchi等人^[36]	一般超图态	$O n 5 l o g n$
Zhu与Hayashi^[37]	一般超图态	$O n 2 l o g n$
Zhu与Hayashi^[38]	一般量子态	$O n 2 l o g n$
Tao等人^[39]	m-染色超图态	$O n 21$
Li等人^[40]	一般图态	$O n l o g n$

Table 2

Fig.6

Fig.7

Table 3

Comparison of three types of verification methods for delegated quantum computation"

验证方法	通信需求	客户端能力需求	服务器数目	计算假设需求	安全性	效率	实现难度
基于弱量子能力	受限量子通信、经典通信	弱量子客户端	$1$	无	强	高	适中
基于纠缠	经典通信	经典客户端	$≥ 2$	无	强	低	困难
基于计算假设	经典通信	经典客户端	$1$	量子计算难题	适中	中	简单

Table 3

References 74

[1]	SHOR P W. Algorithms for quantum computation: discrete logarithms and factoring[C]// Proceedings of the 35th annual symposium on foundations of computer science, 1994: 124-134.
[2]	GROVER L K. A fast quantum mechanical algorithm for database search[C]// Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996: 212-219.
[3]	HARROW A W, HASSIDIM A, LLOYD S. Quantum algorithm for linear systems of equations[J]. Physical Review Letters, 2009, 103(15): 150502.
[4]	AKTER M S, RODRIGUEZ-CARDENAS J, SHAHRIAR H, et al. Quantum cryptography for enhanced network security: A comprehensive survey of research, developments, and future directions[C]// 2023 IEEE International Conference on Big Data (BigData), 2023: 5408-5417.
[5]	HDAIB M, RAJASEGARAR S, PAN L. Quantum deep learning-based anomaly detection for enhanced network security[J]. Quantum Machine Intelligence, 2024, 6(1): 26.
[6]	SILVER D, PATEL T, RANJAN A, et al. SLIQ: quantum image similarity networks on noisy quantum computers[C]// Proceedings of the AAAI Conference on Artificial Intelligence, 2023: 9846-9854.
[7]	FAN Z, ZHANG J, ZHANG P, et al. Quantum-inspired neural network with runge-kutta method[C]// Proceedings of the AAAI Conference on Artificial Intelligence, 2024: 17977-17984.
[8]	QU Z, ZHANG Z, ZHENG M. A quantum blockchain-enabled framework for secure private electronic medical records in Internet of Medical Things[J]. Information Sciences, 2022, 612: 942-958.
[9]	SARAIVA A A, DA SILVA J P O, SOUSA J V M, et al. Incorporating an Intelligent System Based on a Quantum Algorithm into Predictive Analysis for Screening COVID-19 Patients[C]// Proceedings of the 17th International Joint Conference on Biomedical Engineering Systems and Technologies - BIODEVICES, 2024: 111-116.
[10]	BIESNER D, GERLACH T, BAUCKHAGE C, et al. Solving subset sum problems using quantum inspired optimization algorithms with applications in auditing and financial data analysis[C]// 2022 21st IEEE International Conference on Machine Learning and Applications (ICMLA), 2022: 903-908.
[11]	CHOU Y H, LAI Y T, TONG Y F, et al. A Quantum-Inspired Multi-objective Portfolio Strategy Based on Trend Ratio Model in Global Financial Network[C]// 2024 IEEE Congress on Evolutionary Computation (CEC), 2024: 1-8.
[12]	CHILDS A M. Secure assisted quantum computation[J]. Quantum Information and Computation, 2005, 5(6): 456-466.
[13]	GHEORGHIU A, KAPOURNIOTIS T, KASHEFI E. Verification of quantum computation: An overview of existing approaches[J]. Theory of computing systems, 2019, 63: 715-808.
[14]	NIELSEN M A, CHUANG I L. Quantum computation and quantum information[M]// Cambridge, UK: Cambridge university press, 2010: 80-96.
[15]	RAUSSENDORF R, BROWNE D E, BRIEGEL H J. Measurement-based quantum computation on cluster states[J]. Physical Review A, 2003, 68(2): 022312.
[16]	BRUZEWICZ C D, CHIAVERINI J, MCCONNELL R, et al. Trapped-ion quantum computing: Progress and challenges[J]. Applied physics reviews, 2019, 6(2), 021314.
[17]	GAO D, FAN D, ZHA C, et al. Establishing a new benchmark in quantum computational advantage with 105-qubit Zuchongzhi 3.0 processor[J]. Physical Review Letters, 2025, 134(9): 090601.
[18]	BRIEGEL H J, BROWNE D E, DÜR W, et al. Measurement-based quantum computation[J]. Nature Phy-sics, 2009, 5(1): 19-26.
[19]	AGHAEE Rad H, AINSWORTH T, ALEXANDER R N, et al. Scaling and networking a modular photonic quantum computer[J]. Nature, 2025, 638(8052): 1-8.
[20]	BARNUM H, CRÉPEAU C, GOTTESMAN D, et al. Authentication of quantum messages[C]// Proceedin-gs of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002: 449-458.
[21]	AHARONOV D, BEN-OR M, EBAN E. Interactive Proofs for Quantum Computations[J]. arXiv preprint arXiv:0810.5375, 2008.
[22]	AHARONOV D, BEN-OR M, EBAN E, et al. Interactive proofs for quantum computations[J]. arXiv preprint arXiv:1704.04487, 2017.
[23]	FITZSIMONS J F, KASHEFI E. Unconditionally verifiable blind quantum computation[J]. Physical Review A, 2017, 96(1): 012303.
[24]	RAUSSENDORF R, HARRINGTON J, GOYAL K. A fault-tolerant one-way quantum computer[J]. Ann-als of physics, 2006, 321(9): 2242-2270.
[25]	KASHEFI E, WALLDEN P. Optimised resource construction for verifiable quantum computation[J]. Journal of Physics A: Mathematical and Theoretical, 2017, 50(14): 145306.
[26]	FERRACIN S, KAPOURNIOTIS T, DATTA A. Reducing resources for verification of quantum computations[J]. Physical Review A, 2018, 98(2): 022323.
[27]	LEICHTLE D, MUSIC L, KASHEFI E, et al. Verifying BQP computations on noisy devices with minimal overhead[J]. PRX Quantum, 2021, 2(4): 040302.
[28]	BROADBENT A. How to Verify a Quantum Computation[J]. Theory of Computing, 2018, 14(1): 1-37.
[29]	ROSSI M, HUBER M, BRUΒ D, et al. Quantum hypergraph states[J]. New Journal of Physics, 2013, 15(11): 113022.
[30]	GACHECHILADZE M. Quantum hypergraph states and the theory of multiparticle entanglement[D]. Siegen, Germany: Siegen University, 2019.
[31]	MORIMAE T. Verification for measurement-only bli-nd quantum computing[J]. Physical Review A, 2014, 89(6): 060302.
[32]	HAYASHI M, MORIMAE T. Verifiable measurement-only blind quantum computing with stabilizer testing[J]. Physical Review Letters, 2015, 115(22): 220502.
[33]	MILLER J, MIYAKE A. Hierarchy of universal entanglement in 2D measurement-based quantum computation[J]. npj Quantum Information, 2016, 2(1): 1-6.
[34]	MORIMAE T, TAKEUCHI Y, HAYASHI M. Verification of hypergraph states[J]. Physical Review A, 2017, 96(6): 062321.
[35]	TAKEUCHI Y, MORIMAE T. Verification of many-qubit states[J]. Physical Review X, 2018, 8(2): 021-060.
[36]	TAKEUCHI Y, MANTRI A, MORIMAE T, et al. Resource-efficient verification of quantum computing using Serfling’s bound[J]. npj Quantum Information, 2019, 5(1): 27.
[37]	ZHU H, HAYASHI M. Efficient verification of hypergraph states[J]. Physical Review Applied, 2019, 12(5): 054047.
[38]	ZHU H, HAYASHI M. Efficient verification of pure quantum states in the adversarial scenario[J]. Physical Review Letters, 2019, 123(26): 260504.
[39]	TAO H, ZHANG X, SHAO L, et al. Verification of colorable hypergraph states with stabilizer test[J]. Quantum Science and Technology, 2022, 8(1): 015-012.
[40]	LI Z, ZHU H, HAYASHI M. Robust and efficient verification of graph states in blind measurement-based quantum computation[J]. npj Quantum Information, 2023, 9(1): 115.
[41]	DRMOTA P, NADLINGER D P, MAIN D, et al. Verifiable blind quantum computing with trapped ions and single photons[J]. Physical Review Letters, 2024, 132(15): 150604.
[42]	BELL J S. On the einstein podolsky rosen paradox[J]. Physics Physique Fizika, 1964, 1(3): 195-200.
[43]	CLAUSER J F, HORNE M A, Shimony A, et al. Proposed experiment to test local hidden-variable theories[J]. Physical Review Letters, 1969, 23(15): 880.
[44]	GHIO M, MALPETTI D, ROSSI M, et al. Multipartite entanglement detection for hypergraph states[J]. Journal of Physics A: Mathematical and Theoretical, 2017, 51(4): 045302.
[45]	LIU N, DEMARIE T F, TAN S H, et al. Client-friendly continuous-variable blind and verifiable quantum computing[J]. Physical Review A, 2019, 100(6): 062-309.
[46]	XU Q, TAN X, HUANG R, et al. Verification of blind quantum computation with entanglement witnesses[J]. Physical Review A, 2021, 104(4): 042412.
[47]	MORIMAE T, FITZSIMONS J F. Post hoc verification with a single prover[J]. arXiv preprint arXiv:1603.06046, 2016.
[48]	HANGLEITER D, KLIESCH M, SCHWARZ M, et al. Direct certification of a class of quantum simulations[J]. Quantum Science and Technology, 2017, 2(1): 015004.
[49]	FITZSIMONS J F, HAJDUŠEK M, MORIMAE T. Post hoc verification of quantum computation[J]. Ph-ysical Review Letters, 2018, 120(4): 040501.
[50]	MORIMAE T. Blind quantum computing can always be made verifiable[J]. arXiv preprint arXiv:1803.06624, 2018.
[51]	REICHARDT B W, UNGER F, VAZIRANI U. Classical command of quantum systems[J]. Nature, 2013, 496(7446): 456-460.
[52]	GHEORGHIU A, KASHEFI E, WALLDEN P. Robustness and device independence of verifiable blind quantum computing[J]. New Journal of Physics, 2015, 17(8): 083040.
[53]	HAJDUŠEK M, PÉREZ-DELGADO C A, FITZSIMONS J F. Device-independent verifiable blind qua-ntum computation[J]. arXiv preprint arXiv:1502.02563, 2015.
[54]	COLADANGELO A, GRILO A B, JEFFERY S, et al. Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2019: 247-277.
[55]	MCKAGUE M. Interactive proofs for BQP via self-tested graph states[J]. Theory of Computing, 2016, 12(3): 1-42.
[56]	FITZSIMONS J, VIDICK T. A multiprover interactive proof system for the local Hamiltonian problem[C]// Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015: 103-112.
[57]	NATARAJAN A, VIDICK T. Robust self-testing of many-qubit states[J]. arXiv preprint arXiv:1610.03574, 2016.
[58]	GRILO A B. A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round[C]// 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019: 28.
[59]	BERNSTEIN D J, LANGE T. Post-quantum cryptography[J]. Nature, 2017, 549(7671): 188-194.
[60]	BRAKERSKI Z, CHRISTIANO P, MAHADEV U, et al. A cryptographic test of quantumness and certifiable randomness from a single quantum device[J]. Journal of the ACM (JACM), 2021, 68(5): 1-47.
[61]	MAHADEV U. Classical verification of quantum computations[C]// 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018: 259-267.
[62]	CHIA N H, CHUNG K M, YAMAKAWA T. Classical verification of quantum computations with efficient verifier[C]// Theory of Cryptography Conference, 2020: 181-206.
[63]	ALAGIC G, CHILDS A M, GRILO A B, et al. Non-interactive classical verification of quantum computation[C]// Theory of Cryptography Conference, 2020: 153-180.
[64]	BARTUSEK J, KALAI Y T, LOMBARDI A, et al. Succinct classical verification of quantum computation[C]// Annual International Cryptology Conferen-ce, 2022: 195-211.
[65]	CHUNG K M, LEE Y, LIN H H, et al. Constant-round blind classical verification of quantum sampling[C]// Annual International Conference on the Theory and Applications of Cryptographic Techni-ques, 2022: 707-736.
[66]	XU Q, TAN X, BAO D, et al. Classical verification of quantum measurement for the computational basis and the XY-plane basis[J]. Physical Review A, 2023, 107(5): 052616.
[67]	STRICKER R, CARRASCO J, RINGBAUER M, et al. Towards experimental classical verification of qu-antum computation[J]. Quantum Science and Technology, 2024, 9(2): 02LT01.
[68]	GHEORGHIU A, VIDICK T. Computationally-sec-ure and composable remote state preparation[C]// 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019: 1024-1033.
[69]	ZHANG J. Classical verification of quantum computations in linear time[C]// 2022 IEEE 63rd Annual Sy-mposium on Foundations of Computer Science (FOCS), 2022: 46-57.
[70]	BARTUSEK J. Secure quantum computation with classical communication[C]// Theory of Cryptography Conference, 2021: 1-30.
[71]	SHAN R, CHEN X, XU G, et al. Verifiable Multi-Party Universal Blind Quantum Computing in Distributed Networks[J]. Chinese Journal of Electronics, 2021, 30(4): 712-718.
[72]	LI Q, WANG C, ZHU J, et al. Verifiable Multiparty Delegated Quantum Computation[J]. International Journal of Intelligent Systems, 2023, 2023(1): 2662685.
[73]	QUAN J, LI Q, LI L. Verifiable blind quantum computation with identity authentication for multi-type clients[J]. IEEE Transactions on Information Forensics and Security, 2023, 19: 1687-1698.
[74]	KAPOURNIOTIS T, KASHEFI E, LEICHTLE D, et al. Asymmetric quantum secure multi-party computation with weak clients against dishonest majority[J]. Quantum Science and Technology, 2025, 10(2): 025015.