早期量子算法在量子通信、量子纠错等领域的应用

doi:10.11896/jsjkx.210400214

摘要/Abstract

摘要： 当今量子算法的一个发展方向是对早期量子算法的再思考。在量子计算领域,每一种早期量子算法都提出了突破性概念。一般认为它们在很大程度上仅属理论范畴,原因它们所求解的问题几乎都没有实用价值。但这些早期量子算法依然重要,因为它们在解决问题的速度上相比经典算法呈指数级别的增长。文中做了两件工作:一方面详细阐述对早期量子算法再思考的最新进展,另一方面则对早期量子算法进行所谓的重新目的化,即重新用于量子密钥分发、纠错等领域。Deutsch-Jozsa算法、Bernstein-Vazirani算法和Simon算法是关注的重点。Deutsch-Jozsa算法用于判定多引数函数(Multi-argument Function)是平衡的还是常数的。最近的研究表明,其应用可以扩展到量子通信和形式语言(Formal Languages)领域。Bernstein-Vazirani算法能够搜索出在函数中编码的字符串,其应用可以扩展至量子密钥分发领域和通信中对信息的纠错处理。Simon算法则用于求解具有特定属性字符串的识别问题,它的现代应用包括量子通信和纠错。

关键词: Bernstein-Vazirani 算法, Deutsch-Jozsa算法, Simon算法, 量子计算, 量子纠错, 量子密钥分发, 量子算法

Abstract: At present,a development direction of quantum algorithm is to rethink the early quantum algorithms.Each of them involves an important,groundbreaking concept in quantum computing.They are generally considered to only belong to the theoretical category due to the fact that the problems they solve are of little practical value.However,theyare still important as they can solve a problem exponentially faster than a classical algorithm.Here,this paper elaborates on some recent developments in repurposing the early quantum algorithms for quantum key distribution and other fields.It especially focuses on Deutsch-Jozsa algorithm,Bernstein-Vazirani algorithm and Simon's algorithm.The Deutsch-Jozsa algorithm is used to determine whether a multi-argument function is balanced or constant.As recent research shows,it can be extended to application in the field of quantum communication and formal languages.The Bernstein-Vazirani algorithm finds a string encoded in a function.Its application can be extended to quantum key distribution and error correction.Simon's algorithm tackles the problem of identifying a string with a particular property.Its modern applications include quantum communication and error correction.

Key words: Bernstein-Vazirani algorithm, Deutsch-Jozsa algorithm, Quantum algorithms, Quantum computing, Quantum error correction, Quantum key distribution, Simon's algorithm

中图分类号:

TP3-0

Renata WONG. 早期量子算法在量子通信、量子纠错等领域的应用[J]. 计算机科学, 2022, 49(6A): 645-648. https://doi.org/10.11896/jsjkx.210400214

Renata WONG. Application of Early Quantum Algorithms in Quantum Communication,Error Correction and Other Fields[J]. Computer Science, 2022, 49(6A): 645-648. https://doi.org/10.11896/jsjkx.210400214

参考文献

[1] DEUTSCH D,JOZSA R.Rapid solutions of problems by quantum computation[J].Proceedings of the Royal Society of London A,1992,439:553-558.
[2] BERNSTEIN E,VAZIRANI U.Quantum Complexity Theory[J].SIAM Journal on Computing,1992,26(5):1411-1473.
[3] SIMON D.On the Power of Quantum Computation[C]//Pro-ceedings of the 35^thAnnual IEEE Sympo-sium on Foundations of Computer Science.1994:116-123.
[4] GROVER L K.A fast quantum mechanical algorithm for database search[C]//Proceedings of the 28^thAnnual ACM Sympo-sium on the Theory of Computing.1996:212.
[5] SHOR P.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Journal on Computing,1997,26(5):1484-1509.
[6] BRASSARD G,HOYER P,TAPP A.Automata,Languages and Programming[C]//25th International Colloquium ICALP'98.Aalborg,Denmark.1998:820-831.
[7] CHANG W L,YU Q,LI Z,et al.Quantum Speedup in Solving the Maximal-Clique Problem[J].Physical Review A,2018,97:032344.
[8] CHANG W L,CHEN J C,CHUNG W Y,et al.QuantumSpeedup and Mathematical Solutions from Implementing Bio-molecular Solutions for the Independent Set Problem on IBM's Quantum Computers[J].IEEE Transactions on NanoBioscience,2021,20(3):354-376.
[9] WONG R,CHANG W L.Quantum Speedup for Protein Structure Prediction[J].IEEE Transactions on NanoBioscience,2021,20(3):323-330.
[10] WONG R.The Uncertainty Principle as related to QuantumComputing[J].Computer Science,2020,47(1):40-50.
[11] NAGATA K,NAKAMURA T,FAROUK A.Quantum Cryptography Based on the Deutsch-Jozsa Algorithm[J].International Journal of Theoretical Physics,2017,56:2887-2897.
[12] EKERT A K.Quantum Cryptography Based on BelĹs Theorem[J].PRL,1991,67(6):661-663.
[13] NGUYEN D M,KIM S.Quantum Key Distribution ProtocolBased on Modified Generalization of Deutsch-Jozsa Algorithm in d-Level Quantum Systems[J].International Journal of Theoretical Physics,2019,58:71-82.
[14] BATTY M,CASSACCINO A,DUNCAN A J,et al.An Application of the Deutsch-Jozsa Algorithm to Formal Languages and the Word Problem in Groups[C]//TQC:Theory of Quantum Computation,Communication and Cryptography.2008:57-69.
[15] NAGATA K,NAKAMURA T.Quantum Cryptography,Quantum Communication,and Quantum Computer in a Noisy Environment[J].International Journal of Theoretical Physics,2017,56:2086-2100.
[16] XIE H Q,YANG L.Using Bernstein-Vazirani Algorithm to Attack Block-ciphers[J].Designs,Codes and Cryptography,2019,87:1161-1182.
[17] NAGATA K,NAKAMURA T,GEURDES H,et al.Quantum Communication Based on Simon's Algorithm[J].International Journal of Emerging Engineering Research and Technology,2017,5(8):28-31.
[18] CUI J Y,GUO J S,DING S Z.Applications of Simon's Algorithm in Quantum Attacks on Feistel Variants[J].QIP,2021,20:117.
[19] KITAEV A Y.Quantum measurements and the Abelian stabilizer problem[J].arXiv:quant-ph/9511026.
[20] FEYNMAN R.Simulating physics with computers[J].International Journal of Theoretical Physics,1982,21(6/7):467-488.
[21] GILYEN A,SU Y,LOW G H,et al.Quantum singular valuetransformation and beyond:exponential improvements for quantum matrix arithmetic[C]//STOC 2019.2019:193-104.

相关文章 15

[1]	刘建美, 王洪, 马智. Shor整数分解算法的线路优化 Optimization for Shor's Integer Factorization Algorithm Circuit 计算机科学, 2022, 49(6A): 649-653. https://doi.org/10.11896/jsjkx.210600149
[2]	任畅, 赵洪, 蒋华. 一种量子安全拜占庭容错共识机制 Quantum Secured-Byzantine Fault Tolerance Blockchain Consensus Mechanism 计算机科学, 2022, 49(5): 333-340. https://doi.org/10.11896/jsjkx.210400154
[3]	刘晓楠, 宋慧超, 王洪, 江舵, 安家乐. Grover算法改进与应用综述 Survey on Improvement and Application of Grover Algorithm 计算机科学, 2021, 48(10): 315-323. https://doi.org/10.11896/jsjkx.201100141
[4]	罗文俊, 雷爽. 噪声信道下的盲量子计算 Blind Quantum Computation over Noise Channels 计算机科学, 2020, 47(7): 37-41. https://doi.org/10.11896/jsjkx.190600020
[5]	周恒, 王拥军, 王宝山, 燕健. 直觉主义视角下量子逻辑的进一步解释 Deeper Explanation of Quantum Logic in Intuitionistic Perspective 计算机科学, 2020, 47(5): 1-6. https://doi.org/10.11896/jsjkx.191200056
[6]	Renata WONG. 量子计算与不确定性原理 Uncertainty Principle as Related to Quantum Computation 计算机科学, 2020, 47(1): 40-50. https://doi.org/10.11896/jsjkx.190400432
[7]	郑祎能. QKD网络量子信道管理关键技术研究 Research on Key Technologies of Quantum Channel Management in QKD Network 计算机科学, 2018, 45(6A): 356-363.
[8]	戴文静, 袁家斌. 隐含子群问题的研究现状 Survey on Hidden Subgroup Problem 计算机科学, 2018, 45(6): 1-8. https://doi.org/10.11896/j.issn.1002-137X.2018.06.001
[9]	张亮亮,张翌维,梁洁,孙瑞一,王新安. 新量子技术时代下的信息安全 Information Security in New Quantum Technology Age 计算机科学, 2017, 44(7): 1-7. https://doi.org/10.11896/j.issn.1002-137X.2017.07.001
[10]	王亚辉,颜松远. 一种新的攻击RSA的量子算法 New Quantum Algorithm for Breaking RSA 计算机科学, 2016, 43(4): 24-27. https://doi.org/10.11896/j.issn.1002-137X.2016.04.004
[11]	徐永振,郭躬德,蔡彬彬,林崧. 基于一维三态量子游走的量子聚类算法 Quantum Clustering Algorithm Based on One-dimensional Three-state Quantum Walk 计算机科学, 2016, 43(3): 80-83. https://doi.org/10.11896/j.issn.1002-137X.2016.03.016
[12]	樊富有,杨国武,张艳,杨钢. 三值量子基本门及其对量子Fourier变换的电路实现 Three-valued Quantum Elementary and Implementation of Quantum Fourier Transform Circuit 计算机科学, 2015, 42(7): 57-61. https://doi.org/10.11896/j.issn.1002-137X.2015.07.013
[13]	王冬,刘强,李善治. 基于矩阵初等变换的量子可逆逻辑电路双向综合算法 Bidirectional Reversible Logic Circuit Synthesis Algorithm Based on Matrix Elementary Transformation 计算机科学, 2014, 41(9): 18-23. https://doi.org/10.11896/j.issn.1002-137X.2014.09.002
[14]	樊富有,杨国武,李晓瑜,罗庆斌. 混合多值可逆逻辑中广义Toffoli门仅用CNOT门的实现 Realization of Toffoli Gate Only Using CNOT Gate in Hybrid Multi-value Reversible Logic 计算机科学, 2014, 41(8): 115-117. https://doi.org/10.11896/j.issn.1002-137X.2014.08.025
[15]	王冬，刘志昊，朱皖宁，李善治. 基于多目标扩展通用Toffoli门的量子比较器设计 Design of Quantum Comparator Based on Extended General Toffoli Gates with Multiple Targets 计算机科学, 2012, 39(9): 302-306.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed