量子计算复杂性理论综述
|
摘要
量子计算复杂性理论是量子计算机科学的基础理论之一,对量子环境下的算法设计和问题求解具有指导意义.因此,该文对量子计算复杂性理论进行了综述.首先,介绍了各种量子图灵机模型及它们之间的关系.其次,量子计算复杂性是指在量子环境下对于某个问题求解的困难程度,包含问题复杂性、算法复杂性等.于是,该文介绍了量子问题复杂性、量子线路复杂性、量子算法复杂性,并且介绍了量子基本运算和Shor算法的优化实现.第三,格被看做是一种具有周期性结构的n维点空间集合.格密码有很多优势,包括具有抗量子计算的潜力,格算法具有简单易实现、高效性、可并行性特点,格密码已经被证明在最坏条件下和平均条件下具有同等的安全性.因此该文介绍了格的困难问题,以及主要的格密码方案现状.最后,对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望.
The quantum computation complexity theory is one of the basic theories of quantum computer science,and it has guiding significance for the designing and solving some problems under the environment of quantum algorithms.Therefore,in this paper,the quantum computation complexity theory is reviewed.Firstly,this paper introduce the relationships between quantum Turing machine model and classical Turing model.Secondly,due to the quantum computational complexity is the degree of difficulty under the quantum environment for problem solving,including the complexity of the problem,the complexity of the algorithm and so on,this paper describes the quantum complexity of the problem,quantum circuit complexity,the complexity of quantum algorithms,and introduces the basic optimization for quantum computation and Shor algorithm.Thirdly,the lattice has n-dimensional periodic structure in space.Lattice based cryptography has many advantages,including post-quantum computation potential,lattice algorithm is simple,efficient,parallel and easy to implement,lattice cryptography has been shown to haveequal safety under the worst conditions and average conditions.This paper describes some difficult problems about lattice,and the status of the main lattice cryptography scheme.Finally,the prospect about the cipher design and analysis of some important issues worthy of study and quantum computing environments is given.
The quantum computation complexity theory is one of the basic theories of quantum computer science,and it has guiding significance for the designing and solving some problems under the environment of quantum algorithms.Therefore,in this paper,the quantum computation complexity theory is reviewed.Firstly,this paper introduce the relationships between quantum Turing machine model and classical Turing model.Secondly,due to the quantum computational complexity is the degree of difficulty under the quantum environment for problem solving,including the complexity of the problem,the complexity of the algorithm and so on,this paper describes the quantum complexity of the problem,quantum circuit complexity,the complexity of quantum algorithms,and introduces the basic optimization for quantum computation and Shor algorithm.Thirdly,the lattice has n-dimensional periodic structure in space.Lattice based cryptography has many advantages,including post-quantum computation potential,lattice algorithm is simple,efficient,parallel and easy to implement,lattice cryptography has been shown to haveequal safety under the worst conditions and average conditions.This paper describes some difficult problems about lattice,and the status of the main lattice cryptography scheme.Finally,the prospect about the cipher design and analysis of some important issues worthy of study and quantum computing environments is given.
引文
[1]Deutsch D,Jozsa R.Rapid solution of problems by quantum computation.Proceedings of the Royal Society of London.Series A:Mathematical and Physical Sciences,1992,439(1907):553-558
[2]Simon D.On the power of quantum computation//Proceedings of the 35th Annual Symposium on Foundations of Computer Science.Santa Fe,NM,1994:116-123
[3]Grover L K.Quantum mechanics helps in searching for a needle in a haystack.Physical Review Letters,1997,79(2):325-328
[4]Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM Journal on Computing,1997,26(5):1484-1509
[5]Mosca M,Ekert A.The hidden subgroup problem and eigenvalue estimation on a quantum computer//Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communication.California,USA,1999:174-188
[6]Hallgren S,Russell A,Ta-Shma A.The hidden subgroup problem and quantum computation using group representations.SIAM Journal on Computing,2003,32(4):916-934
[7]Schack R.Using aquantum computer to investigate quantum chaos.Physical Review A,1998,57(3):1634-1635
[8]Terraneo M,Georgeot B,Shepelyansky D L.Strange attractor simulated on a quantum computer.The European Physical Journal D-Atomic,Molecular,Optical and Plasma Physics,2003,22(1):127-130
[9]Schindler P,Müller M,Nigg D,et al.Quantum simulation of dynamical maps with trapped ions.Nature Physics,2013,9(6):361-367
[10]Munhoz P P,Semiao F L.Multipartite entangled states with two bosonic modes and qubits.The European Physical Journal D,2010,59(3):509-519
[11]Proos J,Zalka C.Shor’s discrete logarithm quantum algorithm for elliptic curves.Quantum Information and Computation,2003,3(4):317-344
[12]Zhang Huan-Guo,Guan Hai-Ming,Wang Hou-Zhen.Research on the quantum cryptography system.China’s Cryptography Development Report 2010.Changsha:Electronic Industry Press,2011:1-31(in Chinese)(张焕国,管海明,王后珍.抗量子密码体制的研究现状.中国密码学发展报告2010.长沙:电子工业出版社,2011:1-31)
[13]Hankerson D,Menezes A,Vanstone S.Guide to Elliptic Curve Cryptography.New York,USA:Springer-Verlag,2004
[14]Bennett C H,Brassard G.Quantum cryptography:Public key distribution and coin tossing//Proceedings of the IEEEInternational Conference on Computers,Systems and Signal Processing.Bangalor,India,1984:10-12
[15]Bennett C H,Brassard G,Crépeau C,et al.Teleporting an unknown quantum state via dual classical and Einstein-PodolskyRosen channels.Physical Review Letters,1993,70(13):1895
[16]Bennett C H,DiVincenzo D P,Smolin J A,et al.Mixedstate entanglement and quantum error correction.Physical Review A,1996,54(5):3824
[17]Leung D W.Quantum vernam cipher.Physics,2000,2(1):14-34
[18]Shi J J,Shi R H,Guo Y,et al.Batch proxy quantum blind signature scheme.Science China Information Sciences,2013,56(5):1-9
[19]Xiao F Y,Chen H W.Construction of minimal trellises for quantum stabilizer codes.Science China Information Sciences,2013,56(1):1-11
[20]Gehani A,LaBean T H,Reif J H.DNA-Based Cryptography.DNA Based Computers V.Providence,USA:American Mathematical Society,2000
[21]Lu Mingxin,Lai Xuejia,Xiao Guozhen,et al.A symmetric key cryptography with DNA technology.Science in China Series F:Information Sciences,2007,50(3):324-333
[22]Lai Xuejia,Lu Mingxin,Qin Lei,et al.Asymmetric encryption and signature method with DNA technology.Science China:Information Sciences,2010,53(3):506-514
[23]Okamoto T,Tanaka K,Uchiyama S.Quantum public-key cryptosystems//Bellare M ed.Advances in CryptologyCRYPTO 2000.Berlin:Springer,2000:147-165
[24]Bernstein D J,Buchmann J,Dahmen E.Post-Quantum Cryptography.New York:Springer-Verlag,2000
[25]Wang H Z,Zhang H G,Wang Z Y,et al.Extended multivariate public key cryptosystems with secure encryption function.Science China Information Sciences,2011,54(6):1161-1171
[26]Mu L W,Liu X C,Liang C L.Improved construction of LDPC convolutional codes with semi-random parity-check matrices.Science China Information Sciences,2014,57(2):1-10
[27]Heckey J,Patil S,Javadiabhari A,et al.Compiler management of communication and parallelism for quantum computation.ACM Sigplan Notices,2015,50:445-456
[28]Perez-Garcia B,Francis J,Mclaren M,et al.Quantum computation with classical light:The Deutsch Algorithm.Physics Letters A,2015,379(s28-29):1675-1680
[29]Cheung D,Maslov D,Mathew J,et al.On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography//Kawano Y,Mosca M eds.Theory of Quantum Computation,Communication,and Cryptography.Berlin:Springer,2008:96-104
[30]Peev M,Nlle M,Maurhardt O,et al.A novel protocolauthentication algorithm ruling out a man-in-the middle attack in quantum cryptography.International Journal of Quantum Information,2005,3(1):225-231
[31]Krovi H,Russell A.Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups.Communications in Mathematical Physics,2015,334(2):743-777
[32]Jozsa R.Classical simulation and complexity of quantum computations//Ablayev F,Mayr E W eds.Computer Science Theory and Applications.Berlin Heidelberg:Springer-Verlag,2010:252-258
[33]Diao Z,Zubairy M S,Chen G.A quantum circuit design for Grover’s algorithm.Zeitschrift Für Naturforschung A,2014,57(8):701-708
[34]Zheng S,Qiu D.From quantum query complexity to state complexity//Calude C S,Freivalds R,Kazuo I eds.Computing with New Resources.Switzerland:Springer International Publishing,2014:231-245
[35]Yan C,Xu C X,Zhang S B,et al.Quantum secure direct communication and authentication protocol with single photons.Chinese Science Bulletin,2013,58(36):4571-4576
[36]Feynman R P.Simulating physics with computers.International Journal of Theoretical Physics,1982,21(6-7):467-488
[37]Deutsch D.Quantum theory,the church-turing principle and the universal quantum computer.Royal Society,1985,400(1818):97-117
[38]Bernstein E,Vazirani U.Quantum complexity theory//Proceedings of the 25th Annual ACM Symposium on Theory of Computing.New York,USA,1993:11-20
[39]Yimsiriwattana A,Lomonaco Jr S J.Distributed quantum computing:A distributed Shor algorithm//Defense and Security.International Society for Optics and Photonics,2004:360-372
[40]Dash T,Nayak T.Comparative analysis on turing machine and quantum turing machine.Journal of Global Research in Computer Science,2012,3(5):51-56
[41]Bennett C H,Bernstein E,Brassard G,et al.Strengths and weaknesses of quantum computing.SIAM Journal on Computing,1997,26(5):1510-1523
[42]Ohya M,Volovich I V.New quantum algorithm for studying NP-complete problems.Reports on Mathematical Physics,2003,52(1):25-33
[43]Iriyama S,Ohya M.On generalized quantum turing machine and its applications.Open Systems&Information Dynamics,2004,16(2-3):195-204
[44]Ohya M,Volovich I V.Quantum computing and the chaotic amplifier.Journal of Optics B Quantum and Semiclassical Optics,2003,5(6):639-642
[45]Yamakami T.A foundation of programming a multi-tape quantum turing machine//Kutylowski M,Pacholski L,Wierzbicki T eds.Mathematical Foundations of Computer Science 1999.Berlin Heidelberg:Springer-Verlag,1999
[46]Ozawa M,Nishimura H.Local transition functions of quantum Turing machines.RAIRO-Theoretical Informatics and Applications,2000,34(05):379-402
[47]Carpentieri M.On the simulation of quantum turing machines.Theoretical Computer Science,2003,304(1):103-128
[48]Shor P W.Algorithms for quantum computation:Discrete logarithms and factoring//Proceedings of the 35th Annual Symposium on Foundations of Computer Science.Washington,USA,1994:124-134
[49]Spakowski H,Thakur M,Tripathi R.Quantum and classical complexity classes:Separations,collapses,and closure properties.Lecture Notes in Computer Science,2003,200(1):1-34
[50]Fortnow L,Rogers J.Complexity limitations on quantum computation.Journal of Computer and System Sciences,1999,59(2):240-252
[51]Lm A,Huang M,Demarrais J.Quantum computability.SIAM Journal on Computing,1997,26(5):1524-1540
[52]Janzing D,Wocjan P,Zeier R,et al.Thermodynamic cost of reliability and low temperatures:Tightening landauer’s principle and the second law.International Journal of Theoretical Physics,2000,39(12):2717-2753
[53]Tanaka Y.Exact non-identity check is NQP-complete.International Journal of Quantum Information,2010,8(5):807-819
[54]Fenner S,Green F,Homer S,et al.Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy.Proceedings of the Royal Society A,1999,455(1991):3953-3966
[55]Kitaev A Y,Shen A H,Vyalyi M N.Classical and quantum computation.American Mathematical Monthly,Boston,MA,USA,2003:110-257
[56]Beigi S,Shor P W.On the complexity of computing zeroerror and Holevo capacity of quantum channels.Quantum Physics,2007
[57]Kobayashi H,Matsumoto K,Yamakami T.Quantum merlinarthur proof systems:Are multiple merlins more helpful to arthur//Proceedings of the 14th International Symposium.Kyoto,Japan,2003:189-198
[58]Moore C,Nilsson M.Parallel quantum computation and quantum codes.SIAM Journal on Computing,2002,31(3):799-815
[59]Fenner S,Fortnow L,Kurtz S.Gap-definable counting classes.Journal of Computer and System Sciences,1994,48(1):116-148
[60]Fenner S A.PP-lowness and a simple definition of AWPP.Theory of Computing Systems,2003,36(2):199-212
[61]Kobler J,Schoning U,Torn J.Graph isomorphism is low for PP.Computational Complexity,1992,2(4):301-330
[62]Spakowski H,Tripathi R.Degree bounds on polynomials and relativization theory//Levy J-J,Mayr E W,Mitchell J Ceds.Exploring New Frontiers of Theoretical Informatics.Springer US,2004:97-110
[63]Aaronson S.Quantum computing,postselection,and probabilistic polynomial-time.Proceedings of the Royal Society of London A Mathematical Physical and Engineering Sciences,2005,461(2063):3473-3482
[64]Aharonov D,Naveh T.Quantum NP-A survey.Physics,2002
[65]Morimae T,Nishimura H.Quantum interpretations of AWPPand APP.Computer Science,2015
[66]Aharonov D,Ta-Shma A.Adiabatic quantum state generation and statistical zero knowledge//Proceedings of the 35th Annual ACM Symposium on Theory of Computing.New York,USA,2003:20-29
[67]Aaronson S,Bouland A,Fitzsimons J,et al.The space“just above”BQP//Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science.Cambridge,USA,2016:271-280
[68]Watrous J.Quantum computational complexity//Meyers RA ed.Encyclopedia of Complexity and Systems Science.New York:Springer-Verlag,2008:7174-7201
[69]Jain R,Ji Z,Upadhyay S,et al.QIP=PSPACE.Journal of the ACM,2011,58(6):30-58
[70]Jain R,Watrous J.Parallel approximation of non-interactive zero-sum quantum games//Proceedings of the Annual IEEEConference on Computational Complexity.Paris,France,2008:243-253
[71]Beigi S,Shor P,Watrous J.Quantum interactive proofs with short messages.Theory of Computing,2010:101-117
[72]Deutsch D.Quantum computational networks.Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences,1989,425(1868):73-90
[73]Yao C C.Quantum circuit complexity//Proceedings of the34th Symposium on Foundations of Computer Science.Palo Alto,USA,1993:352-361
[74]Juliá-Díaz B,Burdis J M,Tabakin F.QDENSITY-Amathematica quantum computer simulation.Computer Physics Communications,2006,174(11):914-934
[75]Kempe J,Vidick T.Quantum algorithms//Benatti F,Fannes M,Floreanini R,Petritis D eds.Quantum Information,Computation and Cryptography.Berlin Heidelberg:SpringerVerlag,2010:309-342
[76]Gerdt V P,Prokopenya A N.The circuit model of quantum computation and its simulation with mathematica//Adam G,Bua J,Hnatiˇc M eds.Mathematical Modeling and Computational Science.Berlin Heidelberg:Springer-Verlag,2012:43-55
[77]Childs A M,Leung D W,Nielsen M A.Unified derivations of measurement-based schemes for quantum computation.Physical Review A,2005,71(3):032318
[78]Daskin A,Grama A,Kais S.A universal quantum circuit scheme for finding complex eigenvalues.Quantum Information Processing,2014,13(2):333-353
[79]Pan J,Cao Y,Yao X,et al.Experimental realization of quantum algorithm for solving linear systems of equations.Physical Review A,2013,89(2):1150-1154
[80]Alfailakawi M,Ahmad I,Alterkawi L,et al.Depth optimization for topological quantum circuits.Quantum Information Processing,2014,14(2):447-463
[81]Wu Wan-Qing,Zhang Huan-Guo,Mao Shao-Wu,Wang Hou-Zhen.Quantum algorithm to find invariant linear structure of MD hash functions.Quantum Information Processing,2015,14(3):813-829
[82]Wang Dong,Chen Han-Wu,Zhu Wan-Ning,et al.Unitary matrix of multiple-valued quantum purmutation gate.Chinese Journal of Computers,2012,35(3):639-644(in Chinese)(王冬,陈汉武,朱皖宁等.多值逻辑量子置换门的酉矩阵表示.计算机学报,2012,35(3):639-644)
[83]Wu Wan-Qing,Zhang Huan-Guo,Wang Hou-Zhen,Mao Shao-Wu.Polynomial-time quantum algorithms for finding the linear structures of Boolean function.Quantum Information Processing,2015,14(4):1215-1226
[84]Bennett C H.Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states.Physical Review Letters,1992,69(20):2881-2884
[85]Braunstein S L,Kimble H J.A posteriori teleportation.Nature,1998,394(6696):840-841
[86]Ohya M,Masuda N.NP problem in quantum algorithm.Open Systems&Information Dynamics,2000,7(1):33-39
[87]Iriyama S,Ohya M.Generalized quantum turing machine and its use to find an algorithm solving NP-complete problem//Proceedings of the 3rd International Symposium on Applied Sciences in Biomedical and Communication Technologies.Rome,Italy,2010:1-5
[88]Cleve R.The query complexity of order-finding.Information and Computation,2004,192(2):162-171
[89]Harrow A W,Hassidim A,Lloyd S.Quantum algorithm for linear systems of equations.Physical Review Letters,2009,103(15):150502
[90]Laarhoven T,Mosca M,van de Pol J.Solving the shortest vector problem in lattices faster using quantum search//Gaborit P ed.International Workshop on Post-Quantum Cryptography.Berlin:Springer,2013:83-101
[91]Patarin J.Generic Attacks on Feistel Schemes//Boyd C ed.Advances in Cryptology-ASIACRYPT 2001.Berlin Heidelberg:Springer-Verlag,2001:222-238
[92]Buhrman H,Spalek R.Quantum Verification of Matrix Products.Philadelphia,USA:ACM Press,2004:880-889
[93]Bao W S,Song Z,Zhong P C,et al.Quantum mechanical meet-in-the-middle algorithm for subset sum problem.Acta Electronica Sinica,2011,39(1):128-132
[94]Regev O.A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space//Proceedings of the Annual Symposium on the Foundations of Computer Science.Philadelphia,USA,2004:124-134
[95]Wu Wan-Qing,Zhang Huan-Guo,Mao Shao-Wu,et al.Apublic key cryptosystem based on data complexity under quantum environment.Science China Information Sciences.2015,58(11):1-11
[96]Du Ding-Zhu,Ge Ke-Yi,Wang Jie.Introduction to Computational Complexity.Beijing:Higher Education Press,2002
[97]Cleve R.An introduction to quantum complexity theory.Collected Papers on Quantum Computation and Quantum Information Theory,1999,26(5):103-127
[98]Meyers R E,Deacon K S,Tunick A.Space-time quantum imaging//Proceedings of the SPIE 2013.London,UK,2013:1508-1534
[99]Loepp S,Wootters W K.Protecting Information:From Classical Error Correction to Quantum Cryptography.New York,USA:Cambridge University Press,2006
[100]Vedral V,Barenco A,Ekert A.Quantum networks for elementary arithmetic operations.Physical Review,1996,54(1):147-153
[101]Wu Kun,Ma Lei.Study on construction of quantum fullsummator.Chinese Journal of Quantum Electronics,2004,21(1):27-30(in Chinese)(吴昆,马雷.量子全加器构造的探讨.量子电子学报,2004,21(1):27-30)
[102]Takahashi Y,Kunihiro N.A quantum circuit for Shor’s factoring algorithm using 2n+2qubits.Quantum Information and Computation,2006,6(2):184-192
[103]Beauregard S.Circuit for Shor’s algorithm using 2n+3qubits.Quantum Information and Computation,2003,3(2):175-185
[104]Pavlidis A,Gizopoulos D.Fast quantum modular exponentiation architecture for Shor’s factoring algorithm.Quantum Information and Computation,2014,14(7-8):649-682
[105]Fu X Q,Bao W S,Zhou C.Speeding up implementation for Shor’s factorization quantum algorithm.Chinese Science Bulletin,2010,55(32):3648-3653
[106]Fu Xiang-Qun,Bao Wan-Su,Zhou Chun,et al.t-bit semiclassical quantum Fourier transform.Chinese Science Bull,2011,56(26):2250-2255(in Chinese)(付向群,鲍皖苏,周淳等.t比特半经典量子Fourier变换.科学通报,2011,56(26):2250-2255)
[107]Politi A,Matthews J C F,O’Brien J L.Shor’s quantum factoring algorithm on a photonic chip.Science,2009,325(5945):1221
[108]Crespi A,Ramponi R,Osellame R,et al.Integrated photonic quantum gates for polarization qubits.Nature Communications,2011,2(10):193-198
[109]Barz S,Kashefi E,Broadbent A,et al.Demonstration of blind quantum computing.Science,2012,335(6066):303-308
[110]Ukai R,Iwata N,Shimokawa Y,et al.Demonstration of unconditional one-way quantum computations for continuous variables.Physical Review Letters,2011,106(24):240504
[111]Zhang Yi,Lu Kai,Gao Ying-Hui.Quantum algorithm and quantum inspired algorithms.Chinese Journal of Computers,2013,36(9):1835-1842(in Chinese)(张毅,卢凯,高颖慧.量子算法与量子衍生算法.计算机学报,2013,36(9):1835-1842)
[112]Wang Yu-Ping,Li Ying-Hua.A novel quantum genetic algorithm for TSP.Chinese Journal of Computers,2007,30(5):748-755(in Chinese)(王宇平,李英华.求解TSP的量子遗传算法.计算机学报,2007,30(5):748-755)
[113]Wang S,Song X,Niu X.Quantum cosine transform based watermarking scheme for quantum images.Chinese Journal of Electronics,2015,24(2):321-325
[114]Crowley P J D,Duric T,Vinci W,et al.Quantum and Classical in Adiabatic Computation.Physical Review A,2014,90(4):1-9
[115]Aharonov D,Van Dam W,Kempe J,et al.Adiabatic quantum computation is equivalent to standard quantum computation.SIAM Review,2008,50(4):755-787
[116]Schnorr C P,Euchner M.Lattice basis reduction:Improved practical algorithms and solving subset sum problems.Mathematical Programming,1994,66(1-3):181-199
[117]Regev O.On lattices,learning with errors,random linear codes,and cryptography.Journal of the ACM,2009,56(6):84-93
[118]Goldreich O,Goldwasser S,Halevi S.Eliminating decryption errors in the Ajtai-Dwork cryptosystem//Kaliski Jr B S ed.Advances in Cryptology.Lecture Notes in Computer Science1294.Berlin Heidelberg:Springer-Verlag,1997:105-111
[119]Nguyen P Q,Stern J.The two faces of lattices in cryptology//Silverman J H ed.Cryptography and Lattices.LNCS2146.Berlin Heidelberg:Springer-Verlag,2001:146-180
[120]Goldreich O,Goldwasser S,Halevi S.Public-key cryptosystems from lattice reduction problems//Kaliski Jr B S ed.Advances in Cryptology-CRYPTO’97.Berlin Heidelberg:Springer-Verlag,1996:112-131
[121]Micciancio D.Improving lattice based cryptosystems using the hermite normal form//Silverman J H ed.Cryptography and Lattices.Berlin Heidelberg:Springer-Verlag,2001:126-145
[122]Babai L.On Lovasz lattice reduction and the nearest lattice point problem.Combinatorica,1986,6(1):1-13
[123]Hostein J,Pipher J,Silverman J.NTRU:A new high speed public key cryptosystem//Buhler J P ed.Algorithmic Number Theory(ANTS III).Lecture Notes in Computer Science 1423.Berlin Heidelberg:Springer-Verlag,1998:267-288
[124]Regev O.New lattice based cryptographic constructions.Journal of the ACM,2004,51(6):899-942
[125]Aharonov D,Regev O.A lattice problem in quantum NP//Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science(FOCS’03).Washington,USA,2003:210-219
[126]Aharonov D,Regev O.Lattice problems in NP∩coNP.Journal of the ACM,2004,5(5):362-371
[127]Regev O.Quantum computation and lattice problems.SIAM Journal on Computing,2003,33(3):520-529
[128]Laarhoven T,Mosca M,Pol J V D.Finding shortest lattice vectors faster using quantum search.Designs Codes and Cryptography,2015,77(2-3):1-26
[129]Micciancio D,Voulgaris P.Faster exponential time algorithms for the shortest vector problem.Electronic Colloquium on Computational Complexity,2010,16:1468-1480
[130]Nguyen P Q,Vidick T.Sieve algorithms for the shortest vector problem are practical.Journal of Mathematical Cryptology,2008,2(2):181-207
[131]Wang X,Liu M,Tian C,et al.Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem//Proceedings of the 6th ACM Symposium on Information,Computer and Communications Security.Hong Kong,China,2011:1-9
[132]Laarhoven T,Weger B D.Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing//Lauter K,Rodríguez-Henríquez F eds.Progress in Cryptology-LATIN-CRYPT 2015.Switzerland:Springer International Publishing,2015:101-118
[133]Becker A.,Laarhoven T.Efficient sieving in(ideal)lattices using cross-polytopic LSH.International Association for Cryptologic Research,2015:823-849
[134]Lyubashevsky V,Peikert C,Regev O.On ideal lattices and learning with errors over rings.Journal of the ACM,2013,60(6):3-18
[135]Ajtai M,Dwork C.A public-key cryptosystem with worstcase/average-case equivalence//Proceedings of the 29th Annual ACM Symposium on Theory of Computing.New York,USA,1997:284-293
[136]IEEE.P1363.1Public-Key Cryptographic Techniques Based on Hard Problems over Lattices,June 2003
[137]Silverman J H.Almost inverses and fast NTRU key creation.Katholieke University Leoven,Netherlands:Technical Report 014,1999
[138]Jaulmes E,Joux A.A choosen-ciphertext attak against NTRU//Bellare M ed.Advances in Cryptology-CRYPTO2000.Berlin:Springer-Verlag,2000:20-35
[139]Han D,Hong J,Han J W,et al.Key recovery attacks on NTRU without ciphertext validation routine//Proceedings of the 8th Australasian Conference on Information Security and Privacy.Wollongong,Australia,2003:274-284
[140]Howgrave-Graham N,Nguyen P Q,Pointcheval D,Proos J,et al.The impact of decryption failures on the security of NTRU encryption//Boneh D ed.Advances in CryptologyCRYPTO 2003.Berlin Heidelberg:Springer-Verlag,2003:226-246
[141]Yao Jun,Zeng Guihua.Enhanced NTRU cryptosystem eliminating decryption failures.Journal of Systems Engineering and Electronics,2006,17(4):890-895
[142]Hoffstein J,Silverman J.Optimizations for NTRU.In Publickey Cryptography and Computational Number Theory.Berlin,Germany:American Mathematical Society,2000:11-15
[143]Banks W D,Shparlinski I E.A variant of NTRU with noninvertible polynomials//Menezes A,Sarkar P eds.Progress in Cryptology-INDOCRYPT 2002.Berlin Heidelberg:Springer-Verlag,2002:62-70
[144]Coglianese M,Goi B M.MaTRU:A new NTRU-based cryptosystem//Maitra S,Madhavan C E V,Venkatesan Reds.Progress in Cryptology-INDOCRYPT 2005.Berlin Heidelberg:Springer-Verlag,2005:232-243
[145]Chi Y W,Hua M X,Ke H D.Study on NTRU decryption failure.Journal of the China Railway Society,2005,2:454-459
[146]Xu J,Hu L,Sun S,et al.Cryptanalysis of countermeasures against multiple transmission attacks on NTRU.IETCommunications,2014,8(12):2142-2146
[147]Ajtai M.Representing hard lattices with O(nlogn)bits//Proceedings of the 37th Annual ACM Symposium on Theory of Computing.New York,USA,2005:94-103
[148]Cai J Y,Cusick T W.A lattice-based public-key cryptosystem.Information and Computation,1998,151(1-2):17-31
[149]Calude C S,Pavlov B.Coins,quantum measurements,and Turing’s barrier.Quantum Information Processing,2002,1(1-2):107-127
[150]Kieu T D.Quantum algorithm for Hilbert’s tenth problem.International Journal of Theoretical Physics,2003,42(7):1461-1478
[151]Miszczak J.Models of quantum computation and quantum programming languages.Bulletin of the Polish Academy of Sciences:Technical Sciences,2011,59(3):305-324
[152]Etesi G,Németi I.Non-Turing computations via MalamentHogarth space-times.International Journal of Theoretical Physics,2002,41(2):341-370
[153]Abrams S,Lloyd S.Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and#P problems.Physics Review Letter,1998,81(18):3992-3995
[154]Guo H,Long G L,Li F.Quantum algorithms for some well-known NP problems.Communications in Theoretical Physics,2002,37(4):424-426
[155]Plandowski W.Satisfiability of word equations with constants is in NEXPTIME//Proceedings of the Annual ACM Symposium on Theory of Computing.New York,USA,1999:721-725
(1)Milner K,Gutoski G,Hayden P,et al.Quantum interactive proofs and the complexity of entanglement detection.Preprint arXiv,2013,1308
(1)Brassard G,Hoyer P,Tapp A.Quantum algorithm for the collision problem.arXiv preprint quant-ph/9705002,1997
(1)Smolin J A,Smith G,Vargo A.Pretending to factor large numbers on a quantum computer.http://arxiv.org/.arXiv preprint arXiv:1301.7007,2013
(1)Micciancio D.Lattice Based Cryptography:A Global Improvement.http://eprint.iacr.org/.IACR Cryptology ePrint Archive,1999,1999:5
(1)Vats N.NNRU,a noncommutative analogue of NTRU.http://arxiv.org/.arXiv preprint arXiv:0902.1891,2009
[2]Simon D.On the power of quantum computation//Proceedings of the 35th Annual Symposium on Foundations of Computer Science.Santa Fe,NM,1994:116-123
[3]Grover L K.Quantum mechanics helps in searching for a needle in a haystack.Physical Review Letters,1997,79(2):325-328
[4]Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM Journal on Computing,1997,26(5):1484-1509
[5]Mosca M,Ekert A.The hidden subgroup problem and eigenvalue estimation on a quantum computer//Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communication.California,USA,1999:174-188
[6]Hallgren S,Russell A,Ta-Shma A.The hidden subgroup problem and quantum computation using group representations.SIAM Journal on Computing,2003,32(4):916-934
[7]Schack R.Using aquantum computer to investigate quantum chaos.Physical Review A,1998,57(3):1634-1635
[8]Terraneo M,Georgeot B,Shepelyansky D L.Strange attractor simulated on a quantum computer.The European Physical Journal D-Atomic,Molecular,Optical and Plasma Physics,2003,22(1):127-130
[9]Schindler P,Müller M,Nigg D,et al.Quantum simulation of dynamical maps with trapped ions.Nature Physics,2013,9(6):361-367
[10]Munhoz P P,Semiao F L.Multipartite entangled states with two bosonic modes and qubits.The European Physical Journal D,2010,59(3):509-519
[11]Proos J,Zalka C.Shor’s discrete logarithm quantum algorithm for elliptic curves.Quantum Information and Computation,2003,3(4):317-344
[12]Zhang Huan-Guo,Guan Hai-Ming,Wang Hou-Zhen.Research on the quantum cryptography system.China’s Cryptography Development Report 2010.Changsha:Electronic Industry Press,2011:1-31(in Chinese)(张焕国,管海明,王后珍.抗量子密码体制的研究现状.中国密码学发展报告2010.长沙:电子工业出版社,2011:1-31)
[13]Hankerson D,Menezes A,Vanstone S.Guide to Elliptic Curve Cryptography.New York,USA:Springer-Verlag,2004
[14]Bennett C H,Brassard G.Quantum cryptography:Public key distribution and coin tossing//Proceedings of the IEEEInternational Conference on Computers,Systems and Signal Processing.Bangalor,India,1984:10-12
[15]Bennett C H,Brassard G,Crépeau C,et al.Teleporting an unknown quantum state via dual classical and Einstein-PodolskyRosen channels.Physical Review Letters,1993,70(13):1895
[16]Bennett C H,DiVincenzo D P,Smolin J A,et al.Mixedstate entanglement and quantum error correction.Physical Review A,1996,54(5):3824
[17]Leung D W.Quantum vernam cipher.Physics,2000,2(1):14-34
[18]Shi J J,Shi R H,Guo Y,et al.Batch proxy quantum blind signature scheme.Science China Information Sciences,2013,56(5):1-9
[19]Xiao F Y,Chen H W.Construction of minimal trellises for quantum stabilizer codes.Science China Information Sciences,2013,56(1):1-11
[20]Gehani A,LaBean T H,Reif J H.DNA-Based Cryptography.DNA Based Computers V.Providence,USA:American Mathematical Society,2000
[21]Lu Mingxin,Lai Xuejia,Xiao Guozhen,et al.A symmetric key cryptography with DNA technology.Science in China Series F:Information Sciences,2007,50(3):324-333
[22]Lai Xuejia,Lu Mingxin,Qin Lei,et al.Asymmetric encryption and signature method with DNA technology.Science China:Information Sciences,2010,53(3):506-514
[23]Okamoto T,Tanaka K,Uchiyama S.Quantum public-key cryptosystems//Bellare M ed.Advances in CryptologyCRYPTO 2000.Berlin:Springer,2000:147-165
[24]Bernstein D J,Buchmann J,Dahmen E.Post-Quantum Cryptography.New York:Springer-Verlag,2000
[25]Wang H Z,Zhang H G,Wang Z Y,et al.Extended multivariate public key cryptosystems with secure encryption function.Science China Information Sciences,2011,54(6):1161-1171
[26]Mu L W,Liu X C,Liang C L.Improved construction of LDPC convolutional codes with semi-random parity-check matrices.Science China Information Sciences,2014,57(2):1-10
[27]Heckey J,Patil S,Javadiabhari A,et al.Compiler management of communication and parallelism for quantum computation.ACM Sigplan Notices,2015,50:445-456
[28]Perez-Garcia B,Francis J,Mclaren M,et al.Quantum computation with classical light:The Deutsch Algorithm.Physics Letters A,2015,379(s28-29):1675-1680
[29]Cheung D,Maslov D,Mathew J,et al.On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography//Kawano Y,Mosca M eds.Theory of Quantum Computation,Communication,and Cryptography.Berlin:Springer,2008:96-104
[30]Peev M,Nlle M,Maurhardt O,et al.A novel protocolauthentication algorithm ruling out a man-in-the middle attack in quantum cryptography.International Journal of Quantum Information,2005,3(1):225-231
[31]Krovi H,Russell A.Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups.Communications in Mathematical Physics,2015,334(2):743-777
[32]Jozsa R.Classical simulation and complexity of quantum computations//Ablayev F,Mayr E W eds.Computer Science Theory and Applications.Berlin Heidelberg:Springer-Verlag,2010:252-258
[33]Diao Z,Zubairy M S,Chen G.A quantum circuit design for Grover’s algorithm.Zeitschrift Für Naturforschung A,2014,57(8):701-708
[34]Zheng S,Qiu D.From quantum query complexity to state complexity//Calude C S,Freivalds R,Kazuo I eds.Computing with New Resources.Switzerland:Springer International Publishing,2014:231-245
[35]Yan C,Xu C X,Zhang S B,et al.Quantum secure direct communication and authentication protocol with single photons.Chinese Science Bulletin,2013,58(36):4571-4576
[36]Feynman R P.Simulating physics with computers.International Journal of Theoretical Physics,1982,21(6-7):467-488
[37]Deutsch D.Quantum theory,the church-turing principle and the universal quantum computer.Royal Society,1985,400(1818):97-117
[38]Bernstein E,Vazirani U.Quantum complexity theory//Proceedings of the 25th Annual ACM Symposium on Theory of Computing.New York,USA,1993:11-20
[39]Yimsiriwattana A,Lomonaco Jr S J.Distributed quantum computing:A distributed Shor algorithm//Defense and Security.International Society for Optics and Photonics,2004:360-372
[40]Dash T,Nayak T.Comparative analysis on turing machine and quantum turing machine.Journal of Global Research in Computer Science,2012,3(5):51-56
[41]Bennett C H,Bernstein E,Brassard G,et al.Strengths and weaknesses of quantum computing.SIAM Journal on Computing,1997,26(5):1510-1523
[42]Ohya M,Volovich I V.New quantum algorithm for studying NP-complete problems.Reports on Mathematical Physics,2003,52(1):25-33
[43]Iriyama S,Ohya M.On generalized quantum turing machine and its applications.Open Systems&Information Dynamics,2004,16(2-3):195-204
[44]Ohya M,Volovich I V.Quantum computing and the chaotic amplifier.Journal of Optics B Quantum and Semiclassical Optics,2003,5(6):639-642
[45]Yamakami T.A foundation of programming a multi-tape quantum turing machine//Kutylowski M,Pacholski L,Wierzbicki T eds.Mathematical Foundations of Computer Science 1999.Berlin Heidelberg:Springer-Verlag,1999
[46]Ozawa M,Nishimura H.Local transition functions of quantum Turing machines.RAIRO-Theoretical Informatics and Applications,2000,34(05):379-402
[47]Carpentieri M.On the simulation of quantum turing machines.Theoretical Computer Science,2003,304(1):103-128
[48]Shor P W.Algorithms for quantum computation:Discrete logarithms and factoring//Proceedings of the 35th Annual Symposium on Foundations of Computer Science.Washington,USA,1994:124-134
[49]Spakowski H,Thakur M,Tripathi R.Quantum and classical complexity classes:Separations,collapses,and closure properties.Lecture Notes in Computer Science,2003,200(1):1-34
[50]Fortnow L,Rogers J.Complexity limitations on quantum computation.Journal of Computer and System Sciences,1999,59(2):240-252
[51]Lm A,Huang M,Demarrais J.Quantum computability.SIAM Journal on Computing,1997,26(5):1524-1540
[52]Janzing D,Wocjan P,Zeier R,et al.Thermodynamic cost of reliability and low temperatures:Tightening landauer’s principle and the second law.International Journal of Theoretical Physics,2000,39(12):2717-2753
[53]Tanaka Y.Exact non-identity check is NQP-complete.International Journal of Quantum Information,2010,8(5):807-819
[54]Fenner S,Green F,Homer S,et al.Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy.Proceedings of the Royal Society A,1999,455(1991):3953-3966
[55]Kitaev A Y,Shen A H,Vyalyi M N.Classical and quantum computation.American Mathematical Monthly,Boston,MA,USA,2003:110-257
[56]Beigi S,Shor P W.On the complexity of computing zeroerror and Holevo capacity of quantum channels.Quantum Physics,2007
[57]Kobayashi H,Matsumoto K,Yamakami T.Quantum merlinarthur proof systems:Are multiple merlins more helpful to arthur//Proceedings of the 14th International Symposium.Kyoto,Japan,2003:189-198
[58]Moore C,Nilsson M.Parallel quantum computation and quantum codes.SIAM Journal on Computing,2002,31(3):799-815
[59]Fenner S,Fortnow L,Kurtz S.Gap-definable counting classes.Journal of Computer and System Sciences,1994,48(1):116-148
[60]Fenner S A.PP-lowness and a simple definition of AWPP.Theory of Computing Systems,2003,36(2):199-212
[61]Kobler J,Schoning U,Torn J.Graph isomorphism is low for PP.Computational Complexity,1992,2(4):301-330
[62]Spakowski H,Tripathi R.Degree bounds on polynomials and relativization theory//Levy J-J,Mayr E W,Mitchell J Ceds.Exploring New Frontiers of Theoretical Informatics.Springer US,2004:97-110
[63]Aaronson S.Quantum computing,postselection,and probabilistic polynomial-time.Proceedings of the Royal Society of London A Mathematical Physical and Engineering Sciences,2005,461(2063):3473-3482
[64]Aharonov D,Naveh T.Quantum NP-A survey.Physics,2002
[65]Morimae T,Nishimura H.Quantum interpretations of AWPPand APP.Computer Science,2015
[66]Aharonov D,Ta-Shma A.Adiabatic quantum state generation and statistical zero knowledge//Proceedings of the 35th Annual ACM Symposium on Theory of Computing.New York,USA,2003:20-29
[67]Aaronson S,Bouland A,Fitzsimons J,et al.The space“just above”BQP//Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science.Cambridge,USA,2016:271-280
[68]Watrous J.Quantum computational complexity//Meyers RA ed.Encyclopedia of Complexity and Systems Science.New York:Springer-Verlag,2008:7174-7201
[69]Jain R,Ji Z,Upadhyay S,et al.QIP=PSPACE.Journal of the ACM,2011,58(6):30-58
[70]Jain R,Watrous J.Parallel approximation of non-interactive zero-sum quantum games//Proceedings of the Annual IEEEConference on Computational Complexity.Paris,France,2008:243-253
[71]Beigi S,Shor P,Watrous J.Quantum interactive proofs with short messages.Theory of Computing,2010:101-117
[72]Deutsch D.Quantum computational networks.Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences,1989,425(1868):73-90
[73]Yao C C.Quantum circuit complexity//Proceedings of the34th Symposium on Foundations of Computer Science.Palo Alto,USA,1993:352-361
[74]Juliá-Díaz B,Burdis J M,Tabakin F.QDENSITY-Amathematica quantum computer simulation.Computer Physics Communications,2006,174(11):914-934
[75]Kempe J,Vidick T.Quantum algorithms//Benatti F,Fannes M,Floreanini R,Petritis D eds.Quantum Information,Computation and Cryptography.Berlin Heidelberg:SpringerVerlag,2010:309-342
[76]Gerdt V P,Prokopenya A N.The circuit model of quantum computation and its simulation with mathematica//Adam G,Bua J,Hnatiˇc M eds.Mathematical Modeling and Computational Science.Berlin Heidelberg:Springer-Verlag,2012:43-55
[77]Childs A M,Leung D W,Nielsen M A.Unified derivations of measurement-based schemes for quantum computation.Physical Review A,2005,71(3):032318
[78]Daskin A,Grama A,Kais S.A universal quantum circuit scheme for finding complex eigenvalues.Quantum Information Processing,2014,13(2):333-353
[79]Pan J,Cao Y,Yao X,et al.Experimental realization of quantum algorithm for solving linear systems of equations.Physical Review A,2013,89(2):1150-1154
[80]Alfailakawi M,Ahmad I,Alterkawi L,et al.Depth optimization for topological quantum circuits.Quantum Information Processing,2014,14(2):447-463
[81]Wu Wan-Qing,Zhang Huan-Guo,Mao Shao-Wu,Wang Hou-Zhen.Quantum algorithm to find invariant linear structure of MD hash functions.Quantum Information Processing,2015,14(3):813-829
[82]Wang Dong,Chen Han-Wu,Zhu Wan-Ning,et al.Unitary matrix of multiple-valued quantum purmutation gate.Chinese Journal of Computers,2012,35(3):639-644(in Chinese)(王冬,陈汉武,朱皖宁等.多值逻辑量子置换门的酉矩阵表示.计算机学报,2012,35(3):639-644)
[83]Wu Wan-Qing,Zhang Huan-Guo,Wang Hou-Zhen,Mao Shao-Wu.Polynomial-time quantum algorithms for finding the linear structures of Boolean function.Quantum Information Processing,2015,14(4):1215-1226
[84]Bennett C H.Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states.Physical Review Letters,1992,69(20):2881-2884
[85]Braunstein S L,Kimble H J.A posteriori teleportation.Nature,1998,394(6696):840-841
[86]Ohya M,Masuda N.NP problem in quantum algorithm.Open Systems&Information Dynamics,2000,7(1):33-39
[87]Iriyama S,Ohya M.Generalized quantum turing machine and its use to find an algorithm solving NP-complete problem//Proceedings of the 3rd International Symposium on Applied Sciences in Biomedical and Communication Technologies.Rome,Italy,2010:1-5
[88]Cleve R.The query complexity of order-finding.Information and Computation,2004,192(2):162-171
[89]Harrow A W,Hassidim A,Lloyd S.Quantum algorithm for linear systems of equations.Physical Review Letters,2009,103(15):150502
[90]Laarhoven T,Mosca M,van de Pol J.Solving the shortest vector problem in lattices faster using quantum search//Gaborit P ed.International Workshop on Post-Quantum Cryptography.Berlin:Springer,2013:83-101
[91]Patarin J.Generic Attacks on Feistel Schemes//Boyd C ed.Advances in Cryptology-ASIACRYPT 2001.Berlin Heidelberg:Springer-Verlag,2001:222-238
[92]Buhrman H,Spalek R.Quantum Verification of Matrix Products.Philadelphia,USA:ACM Press,2004:880-889
[93]Bao W S,Song Z,Zhong P C,et al.Quantum mechanical meet-in-the-middle algorithm for subset sum problem.Acta Electronica Sinica,2011,39(1):128-132
[94]Regev O.A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space//Proceedings of the Annual Symposium on the Foundations of Computer Science.Philadelphia,USA,2004:124-134
[95]Wu Wan-Qing,Zhang Huan-Guo,Mao Shao-Wu,et al.Apublic key cryptosystem based on data complexity under quantum environment.Science China Information Sciences.2015,58(11):1-11
[96]Du Ding-Zhu,Ge Ke-Yi,Wang Jie.Introduction to Computational Complexity.Beijing:Higher Education Press,2002
[97]Cleve R.An introduction to quantum complexity theory.Collected Papers on Quantum Computation and Quantum Information Theory,1999,26(5):103-127
[98]Meyers R E,Deacon K S,Tunick A.Space-time quantum imaging//Proceedings of the SPIE 2013.London,UK,2013:1508-1534
[99]Loepp S,Wootters W K.Protecting Information:From Classical Error Correction to Quantum Cryptography.New York,USA:Cambridge University Press,2006
[100]Vedral V,Barenco A,Ekert A.Quantum networks for elementary arithmetic operations.Physical Review,1996,54(1):147-153
[101]Wu Kun,Ma Lei.Study on construction of quantum fullsummator.Chinese Journal of Quantum Electronics,2004,21(1):27-30(in Chinese)(吴昆,马雷.量子全加器构造的探讨.量子电子学报,2004,21(1):27-30)
[102]Takahashi Y,Kunihiro N.A quantum circuit for Shor’s factoring algorithm using 2n+2qubits.Quantum Information and Computation,2006,6(2):184-192
[103]Beauregard S.Circuit for Shor’s algorithm using 2n+3qubits.Quantum Information and Computation,2003,3(2):175-185
[104]Pavlidis A,Gizopoulos D.Fast quantum modular exponentiation architecture for Shor’s factoring algorithm.Quantum Information and Computation,2014,14(7-8):649-682
[105]Fu X Q,Bao W S,Zhou C.Speeding up implementation for Shor’s factorization quantum algorithm.Chinese Science Bulletin,2010,55(32):3648-3653
[106]Fu Xiang-Qun,Bao Wan-Su,Zhou Chun,et al.t-bit semiclassical quantum Fourier transform.Chinese Science Bull,2011,56(26):2250-2255(in Chinese)(付向群,鲍皖苏,周淳等.t比特半经典量子Fourier变换.科学通报,2011,56(26):2250-2255)
[107]Politi A,Matthews J C F,O’Brien J L.Shor’s quantum factoring algorithm on a photonic chip.Science,2009,325(5945):1221
[108]Crespi A,Ramponi R,Osellame R,et al.Integrated photonic quantum gates for polarization qubits.Nature Communications,2011,2(10):193-198
[109]Barz S,Kashefi E,Broadbent A,et al.Demonstration of blind quantum computing.Science,2012,335(6066):303-308
[110]Ukai R,Iwata N,Shimokawa Y,et al.Demonstration of unconditional one-way quantum computations for continuous variables.Physical Review Letters,2011,106(24):240504
[111]Zhang Yi,Lu Kai,Gao Ying-Hui.Quantum algorithm and quantum inspired algorithms.Chinese Journal of Computers,2013,36(9):1835-1842(in Chinese)(张毅,卢凯,高颖慧.量子算法与量子衍生算法.计算机学报,2013,36(9):1835-1842)
[112]Wang Yu-Ping,Li Ying-Hua.A novel quantum genetic algorithm for TSP.Chinese Journal of Computers,2007,30(5):748-755(in Chinese)(王宇平,李英华.求解TSP的量子遗传算法.计算机学报,2007,30(5):748-755)
[113]Wang S,Song X,Niu X.Quantum cosine transform based watermarking scheme for quantum images.Chinese Journal of Electronics,2015,24(2):321-325
[114]Crowley P J D,Duric T,Vinci W,et al.Quantum and Classical in Adiabatic Computation.Physical Review A,2014,90(4):1-9
[115]Aharonov D,Van Dam W,Kempe J,et al.Adiabatic quantum computation is equivalent to standard quantum computation.SIAM Review,2008,50(4):755-787
[116]Schnorr C P,Euchner M.Lattice basis reduction:Improved practical algorithms and solving subset sum problems.Mathematical Programming,1994,66(1-3):181-199
[117]Regev O.On lattices,learning with errors,random linear codes,and cryptography.Journal of the ACM,2009,56(6):84-93
[118]Goldreich O,Goldwasser S,Halevi S.Eliminating decryption errors in the Ajtai-Dwork cryptosystem//Kaliski Jr B S ed.Advances in Cryptology.Lecture Notes in Computer Science1294.Berlin Heidelberg:Springer-Verlag,1997:105-111
[119]Nguyen P Q,Stern J.The two faces of lattices in cryptology//Silverman J H ed.Cryptography and Lattices.LNCS2146.Berlin Heidelberg:Springer-Verlag,2001:146-180
[120]Goldreich O,Goldwasser S,Halevi S.Public-key cryptosystems from lattice reduction problems//Kaliski Jr B S ed.Advances in Cryptology-CRYPTO’97.Berlin Heidelberg:Springer-Verlag,1996:112-131
[121]Micciancio D.Improving lattice based cryptosystems using the hermite normal form//Silverman J H ed.Cryptography and Lattices.Berlin Heidelberg:Springer-Verlag,2001:126-145
[122]Babai L.On Lovasz lattice reduction and the nearest lattice point problem.Combinatorica,1986,6(1):1-13
[123]Hostein J,Pipher J,Silverman J.NTRU:A new high speed public key cryptosystem//Buhler J P ed.Algorithmic Number Theory(ANTS III).Lecture Notes in Computer Science 1423.Berlin Heidelberg:Springer-Verlag,1998:267-288
[124]Regev O.New lattice based cryptographic constructions.Journal of the ACM,2004,51(6):899-942
[125]Aharonov D,Regev O.A lattice problem in quantum NP//Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science(FOCS’03).Washington,USA,2003:210-219
[126]Aharonov D,Regev O.Lattice problems in NP∩coNP.Journal of the ACM,2004,5(5):362-371
[127]Regev O.Quantum computation and lattice problems.SIAM Journal on Computing,2003,33(3):520-529
[128]Laarhoven T,Mosca M,Pol J V D.Finding shortest lattice vectors faster using quantum search.Designs Codes and Cryptography,2015,77(2-3):1-26
[129]Micciancio D,Voulgaris P.Faster exponential time algorithms for the shortest vector problem.Electronic Colloquium on Computational Complexity,2010,16:1468-1480
[130]Nguyen P Q,Vidick T.Sieve algorithms for the shortest vector problem are practical.Journal of Mathematical Cryptology,2008,2(2):181-207
[131]Wang X,Liu M,Tian C,et al.Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem//Proceedings of the 6th ACM Symposium on Information,Computer and Communications Security.Hong Kong,China,2011:1-9
[132]Laarhoven T,Weger B D.Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing//Lauter K,Rodríguez-Henríquez F eds.Progress in Cryptology-LATIN-CRYPT 2015.Switzerland:Springer International Publishing,2015:101-118
[133]Becker A.,Laarhoven T.Efficient sieving in(ideal)lattices using cross-polytopic LSH.International Association for Cryptologic Research,2015:823-849
[134]Lyubashevsky V,Peikert C,Regev O.On ideal lattices and learning with errors over rings.Journal of the ACM,2013,60(6):3-18
[135]Ajtai M,Dwork C.A public-key cryptosystem with worstcase/average-case equivalence//Proceedings of the 29th Annual ACM Symposium on Theory of Computing.New York,USA,1997:284-293
[136]IEEE.P1363.1Public-Key Cryptographic Techniques Based on Hard Problems over Lattices,June 2003
[137]Silverman J H.Almost inverses and fast NTRU key creation.Katholieke University Leoven,Netherlands:Technical Report 014,1999
[138]Jaulmes E,Joux A.A choosen-ciphertext attak against NTRU//Bellare M ed.Advances in Cryptology-CRYPTO2000.Berlin:Springer-Verlag,2000:20-35
[139]Han D,Hong J,Han J W,et al.Key recovery attacks on NTRU without ciphertext validation routine//Proceedings of the 8th Australasian Conference on Information Security and Privacy.Wollongong,Australia,2003:274-284
[140]Howgrave-Graham N,Nguyen P Q,Pointcheval D,Proos J,et al.The impact of decryption failures on the security of NTRU encryption//Boneh D ed.Advances in CryptologyCRYPTO 2003.Berlin Heidelberg:Springer-Verlag,2003:226-246
[141]Yao Jun,Zeng Guihua.Enhanced NTRU cryptosystem eliminating decryption failures.Journal of Systems Engineering and Electronics,2006,17(4):890-895
[142]Hoffstein J,Silverman J.Optimizations for NTRU.In Publickey Cryptography and Computational Number Theory.Berlin,Germany:American Mathematical Society,2000:11-15
[143]Banks W D,Shparlinski I E.A variant of NTRU with noninvertible polynomials//Menezes A,Sarkar P eds.Progress in Cryptology-INDOCRYPT 2002.Berlin Heidelberg:Springer-Verlag,2002:62-70
[144]Coglianese M,Goi B M.MaTRU:A new NTRU-based cryptosystem//Maitra S,Madhavan C E V,Venkatesan Reds.Progress in Cryptology-INDOCRYPT 2005.Berlin Heidelberg:Springer-Verlag,2005:232-243
[145]Chi Y W,Hua M X,Ke H D.Study on NTRU decryption failure.Journal of the China Railway Society,2005,2:454-459
[146]Xu J,Hu L,Sun S,et al.Cryptanalysis of countermeasures against multiple transmission attacks on NTRU.IETCommunications,2014,8(12):2142-2146
[147]Ajtai M.Representing hard lattices with O(nlogn)bits//Proceedings of the 37th Annual ACM Symposium on Theory of Computing.New York,USA,2005:94-103
[148]Cai J Y,Cusick T W.A lattice-based public-key cryptosystem.Information and Computation,1998,151(1-2):17-31
[149]Calude C S,Pavlov B.Coins,quantum measurements,and Turing’s barrier.Quantum Information Processing,2002,1(1-2):107-127
[150]Kieu T D.Quantum algorithm for Hilbert’s tenth problem.International Journal of Theoretical Physics,2003,42(7):1461-1478
[151]Miszczak J.Models of quantum computation and quantum programming languages.Bulletin of the Polish Academy of Sciences:Technical Sciences,2011,59(3):305-324
[152]Etesi G,Németi I.Non-Turing computations via MalamentHogarth space-times.International Journal of Theoretical Physics,2002,41(2):341-370
[153]Abrams S,Lloyd S.Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and#P problems.Physics Review Letter,1998,81(18):3992-3995
[154]Guo H,Long G L,Li F.Quantum algorithms for some well-known NP problems.Communications in Theoretical Physics,2002,37(4):424-426
[155]Plandowski W.Satisfiability of word equations with constants is in NEXPTIME//Proceedings of the Annual ACM Symposium on Theory of Computing.New York,USA,1999:721-725
(1)Milner K,Gutoski G,Hayden P,et al.Quantum interactive proofs and the complexity of entanglement detection.Preprint arXiv,2013,1308
(1)Brassard G,Hoyer P,Tapp A.Quantum algorithm for the collision problem.arXiv preprint quant-ph/9705002,1997
(1)Smolin J A,Smith G,Vargo A.Pretending to factor large numbers on a quantum computer.http://arxiv.org/.arXiv preprint arXiv:1301.7007,2013
(1)Micciancio D.Lattice Based Cryptography:A Global Improvement.http://eprint.iacr.org/.IACR Cryptology ePrint Archive,1999,1999:5
(1)Vats N.NNRU,a noncommutative analogue of NTRU.http://arxiv.org/.arXiv preprint arXiv:0902.1891,2009