委托量子计算验证方法研究综述

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

数据与计算发展前沿 ›› 2025, Vol. 7 ›› Issue (6): 55-67.

CSTR: 32002.14.jfdc.CN10-1649/TP.2025.06.006

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

• 专刊：第40次全国计算机安全学术交流会征文 • 上一篇下一篇

委托量子计算验证方法研究综述

袁梓萌^1,²(),龙春^1,^2,^*(),李婧²,杨帆²,付豫豪²,魏金侠^1,²,万巍^1,²

1.中国科学院大学，北京 100190
2.中国科学院计算机网络信息中心，北京 100083

收稿日期:2025-08-01 出版日期:2025-12-20 发布日期:2025-12-17
通讯作者: 龙春
作者简介:袁梓萌，中国科学院计算机网络信息中心，博士研究生，主要研究方向为量子信息处理。
本文承担工作为：文献调研与分析，论文撰写。
YUAN Zimeng is a Ph.D. student at the Computer Network Information Center, Chinese Academy of Sciences. His main research interest is quantum information processing.
In this paper, he is mainly responsible for literature research, analysis, and manuscript writing.
E-mail: zmyuan@cnic.cn|龙春，中国科学院计算机网络信息中心，正高级工程师，博士生导师。中国计算机学会安全专委会委员，中国互联网协会青年专家。主要研究方向为智能网络安全保障、安全大数据挖掘与深度分析等。
本文承担工作为：课题背景支撑，论文框架指导。
LONG Chun is a professorate senior engineer and PhD supervisor at the Computer Network Information Center, Chinese Academy of Sciences. He is also a member of the Technical Committee on Security, China Computer Federation (CCF), and a young expert of the China Internet Association. His main research interests are intelligent cybersecurity assurance, security big data mining, and deep analytics.
In this paper, he is mainly responsible for providing background support and guidance on the overall framework.
E-mail: anquanip@cnic.cn
基金资助:
中国科学院网络安全和信息化专项(CAS-WX2022GC-04);中国科学院青年创新促进会项目(2022170)

Survey of Verification Methods for Delegated Quantum Computation

YUAN Zimeng^1,²(),LONG Chun^1,^2,^*(),LI Jing²,YANG Fan²,FU Yuhao²,WEI Jinxia^1,²,WAN Wei^1,²

1. University of Chinese Academy of Sciences, Beijing 100190, China
2. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100083, China

Received:2025-08-01 Online:2025-12-20 Published:2025-12-17
Contact: LONG Chun

摘要/Abstract

摘要：

【目的】系统梳理和分析委托量子计算验证方法的研究进展与现状。【文献范围】本文调研了1994年至2025年主流会议与期刊的74篇文献，涵盖量子计算验证领域的核心成果与最新进展。【方法】以客户端量子能力需求为主线，将验证方法分为三类（弱量子能力、纠缠、计算假设），构建分类框架；通过对比通信模式、资源开销、容错性等维度，提炼方法演进规律与优劣。【结果】发现三类方法形成互补格局：弱量子方案最成熟但需客户端具备量子能力；纠缠方案仅要求经典客户端但需多服务器协同；计算假设方案通信最简单但依赖后量子密码学。资源开销从指数级降至近线性，但理论优化渐近瓶颈。【结论】研究重心正从理论优化转向应用落地，亟需跨平台实验验证与多方委托计算场景标准化协议。

关键词: 量子计算, 委托计算, 可验证计算, 量子密码学

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

袁梓萌,龙春,李婧,杨帆,付豫豪,魏金侠,万巍. 委托量子计算验证方法研究综述[J]. 数据与计算发展前沿, 2025, 7(6): 55-67.

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.

图/表 10

图1

图2

图3

图4

表1

基于陷阱的委托量子计算验证方案对比"

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

表1

图5

表2

基于稳定子检测的委托量子计算验证方案对比"

验证方案	验证的资源态类型	资源开销
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$

表2

图6

图7

表3

三类委托量子计算验证方法对比"

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

表3

参考文献 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. doi: 10.1103/PhysRevLett.103.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. doi: 10.1007/s42484-024-00163-2
[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. doi: 10.1016/j.ins.2022.09.028
[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. doi: 10.26421/QIC
[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. doi: 10.1007/s00224-018-9872-3
[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. doi: 10.1103/PhysRevA.68.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. doi: 10.1103/PhysRevLett.134.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. doi: 10.1103/PhysRevA.96.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. doi: 10.1088/1751-8121/aa5dac
[26]	FERRACIN S, KAPOURNIOTIS T, DATTA A. Reducing resources for verification of quantum computations[J]. Physical Review A, 2018, 98(2): 022323. doi: 10.1103/PhysRevA.98.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. doi: 10.1103/PRXQuantum.2.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. doi: 10.1088/1367-2630/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. doi: 10.1103/PhysRevA.89.060302
[32]	HAYASHI M, MORIMAE T. Verifiable measurement-only blind quantum computing with stabilizer testing[J]. Physical Review Letters, 2015, 115(22): 220502. doi: 10.1103/PhysRevLett.115.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. doi: 10.1103/PhysRevA.96.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. doi: 10.1038/s41534-019-0142-2
[37]	ZHU H, HAYASHI M. Efficient verification of hypergraph states[J]. Physical Review Applied, 2019, 12(5): 054047. doi: 10.1103/PhysRevApplied.12.054047
[38]	ZHU H, HAYASHI M. Efficient verification of pure quantum states in the adversarial scenario[J]. Physical Review Letters, 2019, 123(26): 260504. doi: 10.1103/PhysRevLett.123.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. doi: 10.1038/s41534-023-00783-9
[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. doi: 10.1103/PhysRevLett.132.150604
[42]	BELL J S. On the einstein podolsky rosen paradox[J]. Physics Physique Fizika, 1964, 1(3): 195-200. doi: 10.1103/PhysicsPhysiqueFizika.1.195
[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. doi: 10.1103/PhysRevLett.23.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. doi: 10.1088/1751-8121/aa99c9
[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. doi: 10.1103/PhysRevA.104.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. doi: 10.1088/2058-9565/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. doi: 10.1038/nature12035
[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. doi: 10.1088/1367-2630/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. doi: 10.1038/nature23461
[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. doi: 10.1103/PhysRevA.107.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. doi: 10.1049/cje2.v30.4
[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. doi: 10.1109/TIFS.2023.3340859
[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.

委托量子计算验证方法研究综述

Survey of Verification Methods for Delegated Quantum Computation

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 74

相关文章 1

编辑推荐

Metrics

本文评价