Quantum algorithm design: techniques and applications. (English) Zbl 1409.81033
Summary: In recent years, rapid developments of quantum computer are witnessed in both the hardware and the algorithm domains, making it necessary to have an updated review of some major techniques and applications in quantum algorithm design.
In this survey as well as tutorial article, the authors first present an overview of the development of quantum algorithms, then investigate five important techniques: Quantum phase estimation, linear combination of unitaries, quantum linear solver, Grover search, and quantum walk, together with their applications in quantum state preparation, quantum machine learning, and quantum search. In the end, the authors collect some open problems influencing the development of future quantum algorithms.
In this survey as well as tutorial article, the authors first present an overview of the development of quantum algorithms, then investigate five important techniques: Quantum phase estimation, linear combination of unitaries, quantum linear solver, Grover search, and quantum walk, together with their applications in quantum state preparation, quantum machine learning, and quantum search. In the end, the authors collect some open problems influencing the development of future quantum algorithms.
MSC:
| 81P68 | Quantum computation |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68M07 | Mathematical problems of computer architecture |
| 68P10 | Searching and sorting |
| 60G50 | Sums of independent random variables; random walks |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
quantum algorithm; quantum computation; quantum machine learning; quantum search; quantum walkSoftware:
NTRUReferences:
| [1] | Benioff P, The computer as a physical system, Journal of Statistical Physics, 1980, 22: 563-591. · Zbl 1382.68066 · doi:10.1007/BF01011339 |
| [2] | Feynman R, Simulating physics with computers, International Journal of Theoretical Physics, 1982, 21: 467-488. · doi:10.1007/BF02650179 |
| [3] | Deutsch D, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. A, 1985, 400: 97-117. · Zbl 0900.81019 · doi:10.1098/rspa.1985.0070 |
| [4] | Deutsch D, Quantum computational networks, Proc. R. Soc. A, 1989, 425: 73-90. · Zbl 0691.68054 · doi:10.1098/rspa.1989.0099 |
| [5] | Yao, A. C-C, Quantum circuit complexity, 352-361 (1993) |
| [6] | Bernstein E and Vazirani U V, Quantum complexity theory, SIAM J. Comput., 1997, 26(5): 1411-1473. · Zbl 0895.68042 · doi:10.1137/S0097539796300921 |
| [7] | Deutsch D and Jozsa R, Rapid solution of problems by quantum computation, Proc. R. Soc. A, 1992, 439: 553-558. · Zbl 0792.68058 · doi:10.1098/rspa.1992.0167 |
| [8] | Simon D R, On the power of quantum computation, SIAM J. Comput., 1997, 26(5): 1474-1483. · Zbl 0883.03024 · doi:10.1137/S0097539796298637 |
| [9] | Shor P W, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 1997, 26(5): 1484-1509. · Zbl 1005.11065 · doi:10.1137/S0097539795293172 |
| [10] | Kitaev A Y, Quantum measurements and the abelian stabilizer problem, arXiv: quant-ph /9511026. |
| [11] | Ettinger M, Høyer P, and Knill E, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters, 2004, 91(1): 43-48. · Zbl 1178.68268 · doi:10.1016/j.ipl.2004.01.024 |
| [12] | Nielsen M A and Chuang I L, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000. · Zbl 1049.81015 |
| [13] | Hallgren, S., Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem, 653-658 (2002), New York · Zbl 1192.81069 |
| [14] | Proos J and Zalka C, Shor’s discrete logarithm quantum algorithm for elliptic curves, Quantum Information and Computation, 2003, 3: 317-344. · Zbl 1152.81800 |
| [15] | Bacon, D.; Childs, A. M.; Dam, W., From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, 469-478 (2005), Washington |
| [16] | Chi D P, Kim J S, and Lee S, Notes on the hidden subgroup problem on some semi-direct product groups, Phys. Lett. A, 2006, 359(2): 114-116. · Zbl 1236.81064 · doi:10.1016/j.physleta.2006.06.014 |
| [17] | Inui Y and Le Gall G, Efficient quantum algorithms for the hidden subgroup problem over a class of semi-direct product groups, Quantum Information and Computation, 2007, 7(5 & 6): 559-570. · Zbl 1152.81739 |
| [18] | Kuperberg G, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Comput., 2005, 35(1): 170-188. · Zbl 1084.81019 · doi:10.1137/S0097539703436345 |
| [19] | Moore, C.; Rockmore, D.; Russell, A.; etal., The power of basis selection in Fourier sampling: The hidden subgroup problem in affine groups, 1113-1122 (2004) · Zbl 1318.81018 |
| [20] | Gavinsky D, Quantum solution to the hidden subgroup problem for poly-near-Hamiltoniangroups, Quantum Information and Computation, 2004, 4: 229-235. · Zbl 1175.81055 |
| [21] | Hallgren S, Russell A, and Ta-Shma A, Normal subgroup reconstruction and quantum computation using group representations, SIAM J. Comput., 2003, 32(4): 916-934. · Zbl 1029.81015 · doi:10.1137/S009753970139450X |
| [22] | Ivanyos, G.; Magniez, F.; Santha, M., Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, 263-270 (2001), New York |
| [23] | Grigni M, Schulman L, Vazirani M, et al., Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Combinatorica, 2004, 24: 137-154. · Zbl 1057.81009 · doi:10.1007/s00493-004-0009-8 |
| [24] | van Dam W, Hallgren S, and Ip L, Quantum algorithms for some hidden shift problems, SIAM J. Comput., 2006, 36(3): 763-778. · Zbl 1126.81019 · doi:10.1137/S009753970343141X |
| [25] | Boneh, D.; Lipton, R. J.; Koblitz, N. (ed.), Algorithms for black-box fields and their application to cryptography, 283-297 (1996) · Zbl 1329.94053 |
| [26] | Kuwakado, H.; Morii, M., Quantum distinguisher between the 3-round Feistel cipher and the random permutation, 2682-2685 (2010) |
| [27] | Kuwakado, H.; Morii, M., Security on the quantum-type Even-Mansour cipher, 312-316 (2012) |
| [28] | Santoli T and Schaffner C, Using Simon’s algorithm to attack symmetric-key cryptographic primitives, arXiv: 1603.07856 [quant-ph]. |
| [29] | Kaplan M, Leurent G, and Leverrier A, Breaking symmetric cryptosystems using quantum period finding, arXiv: 1602.05973v3 [quant-ph]. · Zbl 1391.94766 |
| [30] | Ajtai, M.; Dwork, C., A public-key cryptosystem with worst-case/average-case equivalence, 284-293 (1997), New York · Zbl 0962.68055 |
| [31] | Regev O, New lattice-based cryptographic constructions, Journal of the ACM, 2004, 51(6): 899-942. · Zbl 1125.94026 · doi:10.1145/1039488.1039490 |
| [32] | Regev O, Quantum computation and lattice problems, SIAM J. Comput., 2004, 33(3): 738-760. · Zbl 1057.81012 · doi:10.1137/S0097539703440678 |
| [33] | Galbraith S and Stolbunov A, Improved algorithm for the isogeny problem for ordinary elliptic curves, Applicable Algebra in Engineering, Communication and Computing, 2013, 24(2): 107-131. · Zbl 1316.11113 |
| [34] | Couveignes J M, Hard Homogeneous Spaces, https://eprint.iacr.org/2006/291.pdf. |
| [35] | Rostovtsev A and Stolbunov A, Public-key cryptosystem based on isogenies, https://eprint.iacr.org/2006/145.pdf. |
| [36] | Stolbunov A, Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, Adv. Math. Commun., 2010, 4(2): 215-235. · Zbl 1213.94136 · doi:10.3934/amc.2010.4.215 |
| [37] | Childs A M, Jao D, and Soukharev V, Constructing elliptic curve isogenies in quantum subexponential time, J. Mathematical Cryptology, 2014, 8: 1-29. · Zbl 1283.81046 · doi:10.1515/jmc-2012-0016 |
| [38] | Grover, L. K., A fast quantum mechanical algorithm for database search, 212-219 (1996), New York · Zbl 0922.68044 |
| [39] | Bennett C H, Bernstein E, Brassard G, et al., Strengths and weaknesses of quantum computing, SIAM J. Comput., 1997, 26(5): 1510-1523. · Zbl 0895.68044 · doi:10.1137/S0097539796300933 |
| [40] | Zalka C, Grover’s quantum searching algorithm is optimal, Phy. Rev. A, 1999, 60: 2746-2751. · doi:10.1103/PhysRevA.60.2746 |
| [41] | Long G L, Grover algorithm with zero theoretical rate, Phys. Lett. A, 2001, 64: 022307. |
| [42] | Ambainis A, Quantum search algorithms, SIGACT News, 2004, 35(2): 22-35. · doi:10.1145/992287.992296 |
| [43] | Campbell E, Khurana A, and Montanaro A, Applying quantum algorithms to constraint satisfaction problems, arXiv: 1810.05582 [quant-ph]. |
| [44] | Liu W Z, Zhang J F, and Long G L, A parallel quantum algorithm for the satisfiability problem, Common. Theor. Phys., 2008, 49(3): 629-630. · Zbl 1392.68190 · doi:10.1088/0253-6102/49/3/22 |
| [45] | Laarhoven, T.; Mosca, M.; Pol, J.; Gaborit, P. (ed.), Solving the shortest vector problem in lattices faster using quantum search, 83-101 (2013), Berlin, Heidelberg · Zbl 1306.94067 |
| [46] | Faugère J C, Horan K, Kahrobaei D, et al., Fast quantum algorithm for solving multivariate quadratic equations, arXiv: 1712.07211 [cs.CR]. |
| [47] | He X Y, Sun X M, Yang G, et al., Exact quantum query complexity of weight decision problems, arXiv: 1801.05717v1 [quant-ph]. |
| [48] | Le Gall F and Nishimura H, Quantum algorithms for matrix products over semirings, Chicago Journal of Theoretical Computer Science, 2017, 1: 1-25. · Zbl 1375.68056 · doi:10.4086/cjtcs.2017.001 |
| [49] | Dürr C and Høyer P, A quantum algorithm for finding the minimum, arXiv: quant-ph/9607014. |
| [50] | Kowada L A B, Lavor C, Portugal R, et al., A new quantum algorithm for solving the minimum searching problem, International Journal of Quantum Information, 2008, 6(3): 427-436. · Zbl 1192.81085 · doi:10.1142/S021974990800361X |
| [51] | Brassard G, Høyer P, and Tapp A, Quantum Counting, Automata, Languages and Programming, Eds. by Larsen K G, et al., LNCS 1443, Springer, Berlin, Heidelberg, 1998, 820-831. |
| [52] | Brassard G, Høyer P, and Mosca M, Quantum amplitude amplification and estimation, Quantum Computation and Quantum Information, 2002, 305: 53-74. · Zbl 1063.81024 · doi:10.1090/conm/305/05215 |
| [53] | Brassard, G.; Høyer, P.; Tapp, A.; Lucchesi, C. L (ed.); Moura, A. V (ed.), Quantum cryptanalysis of hash and claw-free functions, 163-169 (1998), Berlin, Heidelberg · Zbl 1508.68118 · doi:10.1007/BFb0054319 |
| [54] | Aaronson S and Shi Y, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM, 2004, 51(4): 595-605. · Zbl 1169.68406 · doi:10.1145/1008731.1008735 |
| [55] | Wang X, Yao A, and Yao F, Cryptanalysis on SHA-1, http://csrc.nist.gov/groups/ST/hash/documents/Wang SHA1-New-Result.pdf. |
| [56] | Cochran M, Notes on the Wang, et al. 263 SHA-1 Differential Path, https://eprint.iacr.org/2007/474.pdf. |
| [57] | Hoffstein, J.; Pipher, J.; Silverman, J. H.; Buhler, J. P (ed.), NTRU: A ring-based public key cryptosystem, 267-288 (1998), Berlin, Heidelberg · Zbl 1067.94538 · doi:10.1007/BFb0054868 |
| [58] | Fluhrer S, Quantum cryptanalysis of NTRU, Cryptology ePrint Archive: Report 2015/676, 2015. |
| [59] | Childs A M, Universal computation by quantum walk, Phys. Rev. Lett., 2009, 102: 180501. · doi:10.1103/PhysRevLett.102.180501 |
| [60] | Magniez F, Santha M, and Szegedy M, Quantum algorithms for the triangle problem, SIAM J. Comput., 2007, 37(2): 413-424. · Zbl 1166.68032 · doi:10.1137/050643684 |
| [61] | Jeffery, S.; Kothari, R.; Magniez, F., Nested quantum walks with quantum data structures, 1474-1485 (2013) · Zbl 1423.68186 |
| [62] | Belovs, A.; Reichardt, B. W.; Epstein, L. (ed.); etal., Span programs and quantum algorithms for st-connectivity and claw detection, 193-204 (2012), Berlin, Heidelberg · Zbl 1368.68216 |
| [63] | Buhrman, H.; Cleve, R.; Wolf, R.; etal., Bounds for small-error and zero-error quantum algorithms, 358-368 (1999) |
| [64] | Dürr C, Heiligman M, and Høyer P, Quantum query complexity of some graph problems, SIAM J. Comput., 2006, 35(6): 1310-1328. · Zbl 1101.81024 · doi:10.1137/050644719 |
| [65] | Ambainis, A.; Kempe, J.; Rivosh, A., Coins make quantum walks faster, 1099-1108 (2005) · Zbl 1297.68076 |
| [66] | Tulsi A, Faster quantum-walk algorithm for the two-dimensional spatial search, Phys. Rev. A, 2008, 78: 012310. · Zbl 1255.81118 · doi:10.1103/PhysRevA.78.012310 |
| [67] | Magniez F, Nayak A, Richter P C, et al., On the hitting times of quantum versus random walks, Algorithmica, 2012, 63(1): 91-116. · Zbl 1236.68072 · doi:10.1007/s00453-011-9521-6 |
| [68] | Aaronson S and Ambainis A, Quantum search of spatial regions, Theory of Computing, 2005, 1: 47-79. · Zbl 1213.68279 · doi:10.4086/toc.2005.v001a004 |
| [69] | Childs A M, Cleve R, Jordan S P, et al., Discrete-query quantum algorithm for NAND trees, Theory of Computing, 2009, 5: 119-123. · Zbl 1213.68283 · doi:10.4086/toc.2009.v005a005 |
| [70] | Ambainis A, Childs A M, Reichardt B W, et al., Any AND-OR formula of size N can be evaluated in time n1/2+o(1) on a quantum computer, SIAM J. Comput., 2010, 39(6): 2513-2530. · Zbl 1207.68151 · doi:10.1137/080712167 |
| [71] | Reichardt, B. W., Faster quantum algorithm for evaluating game trees, 546-559 (2011) · Zbl 1376.68046 |
| [72] | Reichardt, B. W., Reflections for quantum query algorithms, 560-569 (2011) · Zbl 1373.68230 |
| [73] | Reichardt B W and Spalek R, Span-program-based quantum algorithm for evaluating formulas, Theory of Computing, 2012, 8: 291-319. · Zbl 1279.68097 · doi:10.4086/toc.2012.v008a013 |
| [74] | Childs A M and Kothari R, Quantum query complexity of minor-closed graph properties, SIAM Journal on Computing, 2012, 41(6): 1426-1450. · Zbl 1261.68057 · doi:10.1137/110833026 |
| [75] | Le Gall, F., Improved quantum algorithm for triangle finding via combinatorial arguments, 216-225 (2014) |
| [76] | Lee T, Magniez F, and Santha M, Improved quantum query algorithms for triangle finding and associativity testing, Algorithmica, 2017, 77: 459-486. · Zbl 1359.68091 · doi:10.1007/s00453-015-0084-9 |
| [77] | Bernstein, D. J.; Jeffery, S.; Lange, T.; etal.; Gaborit, P. (ed.), Quantum algorithms for the subset-sum problem, 16-33 (2013), Heidelberg · Zbl 1295.68127 · doi:10.1007/978-3-642-38616-9_2 |
| [78] | Ambainis A, Quantum walk algorithm for element distinctness, SIAM J. Comput., 2007, 37: 210-239. · Zbl 1134.81010 · doi:10.1137/S0097539705447311 |
| [79] | Magniez F and Nayak A, Quantum complexity of testing group commutativity, Algorithmica, 2007, 48(3): 221-232. · Zbl 1121.68056 · doi:10.1007/s00453-007-0057-8 |
| [80] | Buhrman, H.; Spalek, R., Quantum verification of matrix products, 880-889 (2006) · Zbl 1192.81056 |
| [81] | Le Gall, F., Improved output-sensitive quantum algorithms for Boolean matrix multiplication, 1464-1476 (2012), Philadelphia · Zbl 1422.68079 |
| [82] | Dorn, S.; Thierauf, T.; Csuhaj-Varjú, E. (ed.), The quantum query complexity of algebraic properties, 250-260 (2007), Berlin, Heidelberg · Zbl 1135.68438 · doi:10.1007/978-3-540-74240-1_22 |
| [83] | Feynman R, Quantum mechanical computer, Optics News, 1985, 11: 11-20. · doi:10.1364/ON.11.2.000011 |
| [84] | Chase B A and Landhal A J, Universal quantum walks and adiabatic algorithms by 1d Hamiltonians, arXiv: 0802.1207 [quant-ph]. |
| [85] | Farhi E and Gutmann S, Quantum computation and decision trees, Phys. Rev. A, 1998, 58: 915-928. · doi:10.1103/PhysRevA.58.915 |
| [86] | Meyer D, From quantum cellular automata to quantum lattice gases, J. Stat. Phys., 1996, 85: 551-574. · Zbl 0952.37501 · doi:10.1007/BF02199356 |
| [87] | Nayak A and Vishvanath A, Quantum walk on the line, arXiv: quant-ph/0010117. |
| [88] | Strauch F W, Connecting the discrete and continuous-time quantum walks, Phys. Rev. A, 2006, 74: 030301. · doi:10.1103/PhysRevA.74.030301 |
| [89] | Childs A M, On the relationship between continuous- and discrete-time quantum walk, Communications in Mathematical Physics, 2010, 294(2): 581-603. · Zbl 1207.81029 · doi:10.1007/s00220-009-0930-1 |
| [90] | Ambainis, A.; Bach, E.; Nayak, A.; etal., One-dimensional quantum walks, 37-49 (2001), New York · Zbl 1323.81021 |
| [91] | Kempe J, Discrete quantum walks hit exponentially faster, Probability Theory and Related Fields, 2005, 133(2): 215-235. · Zbl 1086.60025 · doi:10.1007/s00440-004-0423-2 |
| [92] | Shenvi N, Kempe J, and Whaley K B, A quantum random-walk search algorithm, Phys. Rev. A, 2003, 67: 052307. · doi:10.1103/PhysRevA.67.052307 |
| [93] | Childs, A. M.; Cleve, R.; Deotto, E.; etal., Exponential algorithmic speedup by quantum walk, 59-68 (2003), New York · Zbl 1192.81059 |
| [94] | Childs A M, Farhi E, and Gutmann S, An example of the difference between quantum and classical random walks, Quantum Inf. Process, 2002, 1(1 & 2): 35-43. · Zbl 1329.82006 · doi:10.1023/A:1019609420309 |
| [95] | Szegedy, M., Quantum speed-up of markov chain based algorithms, 32-41 (2004) |
| [96] | Magniez F, Nayak A, Roland J, et al., Search via quantum walk, SIAM J. Comput., 2011, 40(1): 142-164. · Zbl 1223.05289 · doi:10.1137/090745854 |
| [97] | Childs A M, Jeffery S, Kothari R, et al., A time-efficient quantum walk for 3-distinctness using nested updates, arXiv: 1302.7316 [quant-ph]. |
| [98] | Farhi E, Goldstone J, and Gutmann S, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing, 2008, 4: 169-190. · Zbl 1213.68284 · doi:10.4086/toc.2008.v004a008 |
| [99] | Harrow A W, Hassidim A, and Lloyd S, Quantum algorithm for solving linear systems of equations, Phys. Rev. Lett., 2009, 103(15): 150502. · doi:10.1103/PhysRevLett.103.150502 |
| [100] | Lloyd S, Universal quantum simulators, Science, 1996, 273(5278): 1073-1078. · Zbl 1226.81059 · doi:10.1126/science.273.5278.1073 |
| [101] | Suzuki M, General theory of fractal path integrals with applications to many-body theories and statistical physics, Journal of Mathematical Physics, 1991, 32(2): 400-407. · Zbl 0735.47009 · doi:10.1063/1.529425 |
| [102] | Aharonov, D.; Ta-Shma, A., Adiabatic quantum state generation and statistical zero knowledge, 20-29 (2003), New York · Zbl 1192.81048 |
| [103] | Berry D W, Ahokas G, Cleve R, et al., Efficient quantum algorithms for simulating sparse Hamiltonians, Comm. Math. Phys., 2007, 270(2): 359-371. · Zbl 1115.81011 · doi:10.1007/s00220-006-0150-x |
| [104] | Childs, A. M.; Kothari, R.; Dam, W. (ed.); etal., Simulating sparse Hamiltonians with star decompositions, 94-103 (2011) · Zbl 1309.68075 · doi:10.1007/978-3-642-18073-6_8 |
| [105] | Berry D W and Childs A M, Black-box Hamiltonian simulation and unitary implementation, Quantum Information and Computation, 2012, 12: 29-62. · Zbl 1268.81045 |
| [106] | Berry D W, Childs A M, Cleve R, et al., Simulating Hamiltonian dynamics with a truncated Taylor series, Phys. Rev. Lett., 2015, 114: 090502. · doi:10.1103/PhysRevLett.114.090502 |
| [107] | Berry, D. W.; Childs, A. M.; Kothari, R., Hamiltonian simulation with nearly optimal dependence on all parameters, 792-809 (2015) |
| [108] | Low G H and Chuang I L, Hamiltonian simulation by qubitization, arXiv: 1610.06546v2 [quantph]. |
| [109] | Chakraborty S, Gilyén A, and Jeffery S, The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation, arXiv: 1804.01973v1 [quant-ph]. · Zbl 07561526 |
| [110] | Gilyén A, Su Y, Low G H, et al., Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics, arXiv: 1806.01838 [quant-ph]. · Zbl 1433.68147 |
| [111] | Childs A M and Kothari R, Limitations on the simulation of non-sparse Hamiltonians, Quantum Information and Computation, 2010, 10: 669-684. · Zbl 1234.81133 |
| [112] | Rebentrost P, Steffens A, and Lloyd S, Quantum singular value decomposition of non-sparse low-rank matrices, Phys. Rev. A, 2018, 97: 012327. · doi:10.1103/PhysRevA.97.012327 |
| [113] | Kerenidis I and Prakash A, Quantum recommendation system, Proc. ITCSC 2017, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017, 49: 1-21. · Zbl 1402.68189 |
| [114] | Wang C H and Wossnig L, A quantum algorithm for simulating non-sparse Hamiltonians, arXiv: 1803.08273v1 [quant-ph]. |
| [115] | Childs A M, Kothari R, and Somma R D, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM J. Comput., 2017, 46: 1920-1950. · Zbl 1383.68034 · doi:10.1137/16M1087072 |
| [116] | Ambainis, A., Variable time amplitude amplification and quantum algorithms for linear algebra problems, 636-647 (2012) · Zbl 1245.68084 |
| [117] | Saad Y, Iterative Methods for Sparse Linear Systems, 2nd edition, Society for Industrial and Applied Mathematics, 2003. · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [118] | Clader B D, Jacobs B C, and Sprouse C R, Preconditioned quantum linear system algorithm, Phys. Rev. Lett., 2013, 110: 250504. · doi:10.1103/PhysRevLett.110.250504 |
| [119] | Wossnig L, Zhao Z K, and Prakash A, Quantum linear system algorithm for dense matrices, Phys. Rev. Lett., 2018, 120: 050502. · doi:10.1103/PhysRevLett.120.050502 |
| [120] | Chen Y A and Gao X S, Quantum algorithms for Boolean equation solving and quantum algebraic attack on cryptosystems, arXiv: 1712.06239v3 [quant-ph]. · Zbl 1483.68137 |
| [121] | Chen Y A, Gao X S, and Yuan C M, Quantum algorithms for optimization and polynomial systems solving over finite fields, arXiv: 1802.03856v2 [quant-ph]. |
| [122] | Schuld M and Petruccione F, Supervised Learning with Quantum Computers, Springer, 2018. · Zbl 1411.81008 · doi:10.1007/978-3-319-96424-9 |
| [123] | Wittek P, Quantum Machine Learning: What Quantum Computing Mean to Data Mining, Academic Press, 2014. · Zbl 1304.68008 |
| [124] | Wiebe N, Braun D, and Lloyd S, Quantum algorithm for data fitting, Phys. Rev. Lett., 2012, 109(5): 050505. · doi:10.1103/PhysRevLett.109.050505 |
| [125] | Schuld M, Sinayskiy I, and Petruccione F, Prediction by linear regression on a quantum computer, Phys. Rev. A, 2016, 94: 022342. · doi:10.1103/PhysRevA.94.022342 |
| [126] | Wang G M, Quantum algorithm for linear regression, Phy. Rev. A, 2017, 96: 012335. · doi:10.1103/PhysRevA.96.012335 |
| [127] | Lloyd S, Mohseni M, and Rebentrost P, Quantum algorithms for supervised and unsupervised machine learning, arXiv: 1307.0411v2 [quant-ph]. |
| [128] | Lloyd S, Rebentrost P, and Mohseni M, Quantum principal component analysis, Nature Physics, 2014, 10: 631-633. · doi:10.1038/nphys3029 |
| [129] | Rebentrost P, Mohseni M, and Lloyd S, Quantum support vector machine for big data classification, Phys. Rev. Lett., 2014, 113(13): 130503. · doi:10.1103/PhysRevLett.113.130503 |
| [130] | Rebentrost P, Bromley T R, Weedbrook C, et al., Quantum recurrent neural network, Phys. Rev. A, 2018, 98: 042308. · doi:10.1103/PhysRevA.98.042308 |
| [131] | Altaisky M V, Quantum neural network, arXiv: quant-ph/0107012v2. · Zbl 1070.81019 |
| [132] | Schuld M, Sinayskiy I, and Petruccione F, The quest for a quantum neural network, Quantum Inf. Process, 2014, 13: 2567-2586. · Zbl 1305.81055 · doi:10.1007/s11128-014-0809-8 |
| [133] | Schuld M, Sinayskiy I, and Petruccione F, Simulating a perceptron on a quantum computer, Phys. Lett. A, 2015, 379: 660-663. · Zbl 1342.81091 · doi:10.1016/j.physleta.2014.11.061 |
| [134] | Wan K H, Dahlsten O, Kristjánsson H, et al., Quantum generalisation of feedforward neural networks, NPJ Quantum Information, 2017, 3(1): 36-43. · doi:10.1038/s41534-017-0032-4 |
| [135] | Wiebe N, Kapoor A, and Svore K, Quantum perceptron models, Advances in Neural Information Processing Systems, 2016, 29: 3999-4007. |
| [136] | Yamamoto A Y, Sundqvist K M, Li P, et al., Simulation of a multidimensional input quantum perceptron, Quantum Inf. Process, 2018, 17(6): 128-139. · Zbl 1448.81262 · doi:10.1007/s11128-018-1858-1 |
| [137] | Schützhold R, Pattern recognition on a quantum computer, Phys. Rev. A, 2003, 67: 062311. · doi:10.1103/PhysRevA.67.062311 |
| [138] | Trugenberger C A, Quantum pattern recognition, Quantum Inf. Process, 2002, 1(6): 471-493. · doi:10.1023/A:1024022632303 |
| [139] | Ventura D and Martinez T, Quantum associative memory, Information Sciences, 2000, 124(1): 273-296. · doi:10.1016/S0020-0255(99)00101-2 |
| [140] | Low G H, Yoder T J, and Chuang I L, Quantum inference on Bayesian networks, Phys. Rev. A, 2014, 89: 062315. · doi:10.1103/PhysRevA.89.062315 |
| [141] | Sentís G, Calsamiglia J, Muñoz-Tapia R, et al., Quantum learning without quantum memory, Scientific Reports, 2012, 2(708): 1-8. |
| [142] | Barry J, Barry D T, and Aaronson S, Quantum POMDPs, Phys. Rev. A, 2014, 90: 032311. · doi:10.1103/PhysRevA.90.032311 |
| [143] | Clark, L. A.; Huang, W.; Barlow, T. M.; etal.; Sanayei, A. (ed.); etal., Hidden quantum Markov models and open quantum systems with instantaneous feedback, 143-151 (2015) |
| [144] | Adachi S H and Henderson M P, Application of quantum annealing to training of deep neural networks, arXiv: 1510.06356 [quant-ph]. |
| [145] | Wiebe N, Kapoor A, and Svore K, Quantum deep learning, arXiv: 1412.3489 [quant-ph]. |
| [146] | Amin M H, Andriyash E, Rolfe J, et al., Quantum Boltzmann machine, Phys. Rev. X, 2018, 8: 021050. |
| [147] | Crawford D, Levit A, Ghadermarzy N, et al., Reinforcement learning using quantum Boltzmann machines, arXiv: 1612.05695 [quant-ph]. |
| [148] | Kieferova M and Wiebe N, Tomography and generative data modeling via quantum Boltzmann training, Phys. Rev. A, 2017, 96: 062327. · doi:10.1103/PhysRevA.96.062327 |
| [149] | Messiah A, Quantum Mechanics, Vol. II. Wiley, New Jersey, 1976. · Zbl 0102.42602 |
| [150] | Farhi E, Goldstone J, Gutmann S, et al., Quantum computation by adiabatic evolution, arXiv: quant-ph/0001106v1. · Zbl 1187.81063 |
| [151] | Childs A M, Farhi E, and Preskill J, Robustness of adiabatic quantum computation, Phys. Rev. A, 2001, 65: 012322. · doi:10.1103/PhysRevA.65.012322 |
| [152] | Roland J and Cerf N, Quantum search by local adiabatic evolution, Phys. Rev. A, 2002, 65: 042308. · doi:10.1103/PhysRevA.65.042308 |
| [153] | Aharonov D, van Dam W, Kempe J, et al., Adiabatic quantum computation is equivalent to standard quantum computation, SIAM J. Comput., 2007, 37(1): 166-194. · Zbl 1134.81009 · doi:10.1137/S0097539705447323 |
| [154] | Childs A M, Farhi E, Goldstone J, et al., Finding cliques by quantum adiabatic evolution, Quantum Information and Computation, 2002, 2(181): 181-191. · Zbl 1187.81063 |
| [155] | Farhi E, Goldstone F, Gutmann S, et al., A quantum adiabatic evolution algorithm applied to instances of an NP-complete problem, Science, 2001, 292(5516): 472-475. · Zbl 1226.81046 · doi:10.1126/science.1057726 |
| [156] | Hogg T, Adiabatic quantum computing for random satisfiability problems, Phys. Rev. A, 2003, 67: 022314. · doi:10.1103/PhysRevA.67.022314 |
| [157] | Reichardt, B. W., The quantum adiabatic optimization algorithm and local minima, 502-510 (2004), New York · Zbl 1192.81098 |
| [158] | van Dam W and Vazirani U V, Limits on quantum adiabatic optimization, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.2905&rep=rep1&type=pdf. |
| [159] | Neven H, Denchev V S, Rose E, et al., Training a binary classifier with the quantum adiabatic algorithm, arXiv: 0811.0416 [quant-ph]. |
| [160] | Pudenz K L and Lidar D A, Quantum adiabatic machine learning, Quantum Inf. Process, 2013, 12(5): 2027-2070. · Zbl 1271.81052 · doi:10.1007/s11128-012-0506-4 |
| [161] | Gaitan F and Clark L, Ramsey numbers and adiabatic quantum computing, Phys. Rev. Lett., 2012, 108: 010501. · doi:10.1103/PhysRevLett.108.010501 |
| [162] | Gaitan F and Clark L, Graph isomorphism and adiabatic quantum computing, Phys. Rev. A, 2014, 89(2): 022342. · doi:10.1103/PhysRevA.89.022342 |
| [163] | Kitaev A Y, Fault-tolerant quantum computation by anyons, Annals of Physics, 2003, 303(1): 2-30. · Zbl 1012.81006 · doi:10.1016/S0003-4916(02)00018-0 |
| [164] | Freedman M H, Kitaev A, Larsen M J, et al., Topological quantum computation, Bull. Amer. Math. Soc., 2003, 40: 31-38. · Zbl 1019.81008 · doi:10.1090/S0273-0979-02-00964-3 |
| [165] | Aharonov, D.; Jones, V.; Landau, Z., A polynomial quantum algorithm for approximating the jones polynomial, 427-436 (2006), New York · Zbl 1301.68129 |
| [166] | Aharonov D, Arad I, Eban E, et al., Polynomial quantum algorithms for additive approximations of the potts model and other points of the tutte plane, arXiv: quant-ph/0702008. |
| [167] | Wocjan P and Yard J, The Jones polynomial: Quantum algorithms and applications in quantum complexity theory, Quantum Information and Computation, 2008, 8(1): 147-180. · Zbl 1153.81477 |
| [168] | Arad I and Landau Z, Quantum computation and the evaluation of tensor networks, SIAM J. Comput., 2010, 39(7): 3089-3121. · Zbl 1209.68261 · doi:10.1137/080739379 |
| [169] | Aaronson S, The limits of quantum computers, Scientific American, 2008, 298(3): 62-69. · doi:10.1038/scientificamerican0308-62 |
| [170] | Aaronson, S., BQP and the polynomial hierarchy, 141-150 (2010), New York · Zbl 1293.68130 |
| [171] | Mahadev U, Classical Verification of Quantum Computations, arXiv: 1804.01082v2 [quant-ph]. · Zbl 1500.81019 |
| [172] | Cirac J and Zoller P, Quantum computation with cold trapped ions, Phys. Rev. Lett., 1995, 74: 4091-4094. · doi:10.1103/PhysRevLett.74.4091 |
| [173] | Gershenfeld N and Chuang I L, Bulk spin resonance quantum computing, Science, 1997, 275: 350-356. · Zbl 1226.81047 · doi:10.1126/science.275.5298.350 |
| [174] | Loss D and Di Vincenzo D, Quantum computation with quantum dots, Phys. Rev. A, 1998, 57: 120-126. · doi:10.1103/PhysRevA.57.120 |
| [175] | Vandersypen L M K, Steffen M, Breyta G, et al., Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature, 2001, 414(6866): 883-887. · doi:10.1038/414883a |
| [176] | Zhao Z, Chen Y A, Zhang A N, et al., Experimental demonstration of five-photon entanglement and open-destination teleportation, Nature, 2004, 430(6995): 54-58. · doi:10.1038/nature02643 |
| [177] | 12-qubits reached in quantum information quest, https://www.sciencedaily.com/releases/2006/05/060508164700.htm. |
| [178] | World’s First 28 qubit Quantum Computer Demonstrated Online at Supercomputing 2007 Conference, https://www.nanowerk.com/news/newsid=3274.php. |
| [179] | Dwave System’s 128 qubit chip has been made, https://www.nextbigfuture.com/2008/12/dwavesystems-128-qubit-chip-has-been.html. |
| [180] | Monz T, Schindler P, Barreiro J T, et al., 14-Qubit Entanglement: Creation and Coherence, Phys. Rev. Lett., 2011, 106(13): 130506. · doi:10.1103/PhysRevLett.106.130506 |
| [181] | D-wave systems breaks the 1000 qubit quantum computing barrier, https://www.dwavesys.com/press-releases/d-wave-systems-breaks-1000-qubit-quantum-computing-barrier. |
| [182] | O’Malley P J J, Babbush R, Kivlichan I D, et al., Scalable quantum simulation of molecular energies, Phys. Rev. X, 2016, 6: 031007. |
| [183] | IBM just made a 17 qubit quantum processor, its most powerful one yet, https://motherboard.vice.com/enus/article/wnwk5w/ibm-17-qubit-quantum-processor-computer-google. |
| [184] | Quantum inside: Intel manufactures an exotic new chip, https://www.technologyreview.com/s/609094/quantum-inside-intel-manufactures-an-exotic-new-chip/. |
| [185] | IBM Q Experience, https://quantumexperience.ng.bluemix.net/qx/experience. |
| [186] | Coles P J, Eidenbenz S, Pakin S, et al., Quantum Algorithm Implementations for Beginners, arXiv: 1804.03719v1 [cs.ET]. |
| [187] | China builds five qubit quantum computer sampling and will scale to 20 qubits by end of this year and could any beat regular computer next year, https://www.nextbigfuture.com/2017/05/chinabuilds-ten-qubit-quantum-computer-and-will-scale-to-20-qubits-by-end-of-this-year-and-couldany-beat-regular-computer-next-year.html. |
| [188] | IBM raises the bar with a 50-qubit quantum computer, https://www.technologyreview.com/s/609451/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/. |
| [189] | D-wave announces d-wave 2000q quantum computer and first system order, https://www.dwavesys.com/press-releases/d-wave-announces-d-wave-2000q-quantum-computer-and-first-system-order. |
| [190] | CES 2018: Intel’s 49-qubit chip shoots for quantum supremacy, https://spectrum.ieee.org/techtalk/computing/hardware/intels-49qubit-chip-aims-for-quantum-supremacy. |
| [191] | Google moves toward quantum supremacy with 72-qubit computer, https://www.sciencenews.org/article/google-moves-toward-quantum-supremacy-72-qubit-computer. |
| [192] | Lu C Y, Browne D E, and Yang T, Demonstration of a compiled version of Shor’s quantum factoring algorithm Using Photonic Qubits, Phys. Rev. Lett., 2007, 99: 250504. · doi:10.1103/PhysRevLett.99.250504 |
| [193] | Lanyon B P, Weinhold T J, Langford N K, et al., Experimental demonstration of a compiled version of Shor’s algorithm with quantum entanglement, Phys. Rev. Lett., 2007, 99(25): 250505. · doi:10.1103/PhysRevLett.99.250505 |
| [194] | Martin-Lopez E, Laing A, Lawson T, et al., Experimental realisation of Shor’s quantum factoring algorithm using qubit recycling, Nat. Photon., 2012, 6: 773-776. · doi:10.1038/nphoton.2012.259 |
| [195] | Chuang I L, Gershenfeld N, and Kubinec M, Experimental implementation of fast quantum searching, Phys. Rev. Lett., 1998, 80: 3408-3411. · doi:10.1103/PhysRevLett.80.3408 |
| [196] | Vandersypen L M K, Steffen M, Sherwood M H, et al., Implementation of a three-quantum-bit search algorithm, Appl. Phys. Lett., 2000, 76: 646-648. · doi:10.1063/1.125846 |
| [197] | Barz S, Kassal I, and Ringbauer M, Solving systems of linear equations on a quantum computer, Sci. Rep., 2014, 4: 115. |
| [198] | Cai X D, Weedbrook C, Su Z E, et al., Experimental quantum computing to solve systems of linear equations, Phys. Rev. Lett., 2013, 110(23): 230501. · doi:10.1103/PhysRevLett.110.230501 |
| [199] | Pan J W, Cao Y D, Yao X W, et al., Experimental realization of quantum algorithm for solving linear systems of equations, Phys. Rev. A, 2014, 89: 022313. · doi:10.1103/PhysRevA.89.022313 |
| [200] | Ambainis, A.; Hlineny, P. (ed.); etal., New Developments in Quantum Algorithms, 1-11 (2010), Berlin, Heidelberg · Zbl 1287.68050 |
| [201] | Cleve R, Ekert A, Macchiavello C, et al., Quantum algorithms revisited, Proc. R. Soc. A, 1997, 454(1969): 339-354. · Zbl 0915.68050 · doi:10.1098/rspa.1998.0164 |
| [202] | Montanaro A, Quantum algorithms: An overview, npj Quantum Information, 2016, 2: 15023. · doi:10.1038/npjqi.2015.23 |
| [203] | Shor P W, Progress in quantum algorithms, Quantum Inf. Process, 2004, 3: 5-13. · Zbl 1075.68602 · doi:10.1007/s11128-004-3878-2 |
| [204] | Sun X M, A survey on quantum computing, Sci. China Inf. Sci., 2016, 8: 982-1002 (in Chinese). |
| [205] | Dervovic D, Herbster M, Mountney P, et al., Quantum linear systems algorithms: A primer, arXiv: 1802.08227v1 [quant-ph]. |
| [206] | Kaye P, Laflamme R, and Mosca M, An Introduction to Quantum Computing, Oxford University Press, New York, 2007. · Zbl 1297.68001 |
| [207] | Rieffel E and Polak W, Quantum Computing — A Gentle Introduction, The MIT Press, Cambridge, Massachusetts London, England, 2011. · Zbl 1221.81003 |
| [208] | Ambainis A, Quantum walks and their algorithmic applications, International Journal of Quantum Information, 2003, 1: 507-518. · Zbl 1069.81505 · doi:10.1142/S0219749903000383 |
| [209] | Elías S, Venegas-Andraca S E, Quantum walks: A comprehensive review, Quantum Inf. Process, 2012, 11(5): 1015-1106. · Zbl 1283.81040 · doi:10.1007/s11128-012-0432-5 |
| [210] | Nayak, A.; Richter, P. C.; Szegedy, M.; Kao, M. Y (ed.), Quantum analogs of markov chains, 1-10 (2014), Berlin, Heidelberg |
| [211] | Santha, M., Quantum walk based search algorithms, 31-46 (2008) · Zbl 1139.68338 |
| [212] | Kempe J, Quantum random walks - an introductory overview, Contemporary Physics, 2003, 44(4): 307-327. · doi:10.1080/00107151031000110776 |
| [213] | Childs A M, Maslov D, Nam Y, et al., Toward the first quantum simulation with quantum speedup, Proceedings of the National Academy of Sciences, 2018, 115: 9456-9461. · Zbl 1415.68107 · doi:10.1073/pnas.1801723115 |
| [214] | Adcock J C, Allen E, Day M, et al., Advances in quantum machine learning, arXiv: 1512.02900v1 [quant-ph]. |
| [215] | Arunachalam S and de Wolf R, A Survey of Quantum Learning Theory, arXiv:1701.06806v3[quant-ph]. · Zbl 1440.68096 |
| [216] | Biamonte J, Wittek P, Pancotti N, et al., Quantum machine learning, Nature, 2017, 549: 195-202. · doi:10.1038/nature23474 |
| [217] | Ciliberto C, Herbster M, Ialongo A D, et al., Quantum machine learning: A classical perspective, Proc. R. Soc. A, 2018, 474(2209): 20170551. · Zbl 1402.68154 · doi:10.1098/rspa.2017.0551 |
| [218] | Dunjko V and Briegel H J, Machine learning & artificial intelligence in the quantum domain, arXiv: 1709.02779v1 [quant-ph]. · Zbl 1452.82040 |
| [219] | Schuld M, Sinayskiy I, and Petruccione F, An introduction to quantum machine learning, Contemporary Physics, 2015, 56(2): 172-185. · Zbl 1342.81091 · doi:10.1080/00107514.2014.964942 |
| [220] | Albash T and Lidar D A, Adiabatic quantum computing, Rev. Mod. Phys., 2018, 90: 015002. · doi:10.1103/RevModPhys.90.015002 |
| [221] | Quantum algorithm zoo, https://math.nist.gov/quantum/zoo/. |
| [222] | Childs A M, Lecture notes on quantum algorithms, http://www.cs.umd.edu/amchilds/qa/. |
| [223] | Christopher M D and Nielsen A, The Solovay-Kitaev algorithm, Quantum Information and Computation, 2006, 6(1): 81-95. · Zbl 1152.81706 |
| [224] | Abrams D S and Lloyd S, Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors, Phys. Rev. Lett., 1999, 83(24): 5162-5165. · doi:10.1103/PhysRevLett.83.5162 |
| [225] | Buhrman H, Cleve R, Watrous J, et al., Quantum fingerprinting, Phys. Rev. Lett., 2001, 87(16): 167902. · doi:10.1103/PhysRevLett.87.167902 |
| [226] | Long G L, General quantum interference principle and duality computer, Common. Theor. Phys., 2006, 45: 825-844. · doi:10.1088/0253-6102/45/5/013 |
| [227] | Childs A M and Wiebe N, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information and Computation, 2012, 12: 901-924. · Zbl 1263.81112 |
| [228] | Kerenidis I and Prakash A, Quantum gradient descent for linear systems and least squares, arXiv: 1704.04992v3 [quant-ph]. · Zbl 1402.68189 |
| [229] | Rebentrost P, Schuld M, Wossnig L, et al., Quantum gradient descent and Newton’s method for constrained polynomial optimization, arXiv: 1612.01789v2 [quant-ph]. |
| [230] | Grover L K and Rudolph T, Creating superpositions that correspond to efficiently integrable probability distributions, arXiv: quant-ph/0208112. |
| [231] | Soklakov A N and Schack R, Efficient state preparation for a register of quantum bits, Phys. Rev. A, 2006, 73: 012307. · doi:10.1103/PhysRevA.73.012307 |
| [232] | Alpaydin E, Introduction to Machine Learning, 3rd Edition, The MIT Press, Massachusetts, 2015. · Zbl 1298.68002 |
| [233] | Mackay D, Information Theory, Inference and Learning Algorithms, Cambridge University Press, Cambridge, 2003. · Zbl 1055.94001 |
| [234] | Sra S, Nowozin S, and Wright S J, Optimization for Machine Learning, The MIT Press, Massachusetts, 2011. · doi:10.7551/mitpress/8996.001.0001 |
| [235] | Golub G H and Van Loan C F, Matrix Computations, 4th Edition, The John Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037 |
| [236] | Hestenes M R and Stiefel E, Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 1952, 49: 409-436. · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [237] | Aaronson S, Quantum Machine Learning Algorithms: Read the Fine Print, Nature Physics, 2015, 11(4): 291-293. · doi:10.1038/nphys3272 |
| [238] | Childs A M, Quantum algorithms: Equation solving by simulation, Nature Physics, 2009, 5(5): 861. · doi:10.1038/nphys1473 |
| [239] | Harrow, A. W.; Kao, M. Y (ed.), Quantum algorithms for systems of linear equations, 1680-1683 (2016), Berlin, Heidelberg · doi:10.1007/978-1-4939-2864-4_771 |
| [240] | Giovannetti V, Lloyd S, and Maccone L, Architectures for a quantum random access memory, Phys. Rev. A, 2008, 78: 052310. · Zbl 1228.81125 · doi:10.1103/PhysRevA.78.052310 |
| [241] | Giovannetti V, Lloyd S, and Maccone L, Quantum random access memory, Phys. Rev. Lett., 2008, 100: 160501. · Zbl 1228.81125 · doi:10.1103/PhysRevLett.100.160501 |
| [242] | Kerenidis I and Prakash A, A quantum interior point method for LPs and SDPs, arXiv: 1808.09266v1 [quant-ph]. |
| [243] | Bardet M, Faugère J C, Salvy B, et al., On the complexity of solving quadratic boolean systems, Journal of Complexity, 2013, 29(1): 53-75. · Zbl 1255.65090 · doi:10.1016/j.jco.2012.07.001 |
| [244] | Hastie T, Tibshirani R, and Friedman J, The Elements of Statistical Learning, Springer, New York, 2001. · Zbl 0973.62007 · doi:10.1007/978-0-387-21606-5 |
| [245] | Haykin S, Neural Networks and Learning Machines, 3rd Edition, Pearson, 2009. |
| [246] | Cleveland W S, Robust locally weighted regression and smoothing scatterplots, Journal of the American Statistical Association, 1979, 74(368): 829-836. · Zbl 0423.62029 · doi:10.1080/01621459.1979.10481038 |
| [247] | Cleveland W S and Devlin S J, Locally-weighted regression: An approach to regression analysis by local fitting, Journal of the American Statistical Association, 1988, 83(403): 596-610. · Zbl 1248.62054 · doi:10.1080/01621459.1988.10478639 |
| [248] | Ng A, Supervised learning, discriminative algorithms, http://cs229.stanford.edu/notes/cs229-notes1.pdf. |
| [249] | Suykens J A K and Vandewalle J, Least squares support vector machine classifiers, Neural Processing Letters, 1999, 9(3): 293-300. · doi:10.1023/A:1018628609742 |
| [250] | Levin D A, Peres Y, and Wilmer E L, Markov Chains and Mixing Times, American Mathematical Society, Providence, Rhode Island, 2009. · Zbl 1160.60001 |
| [251] | Lovász, L., Random walks on graphs — A survey, 1-46 (1993) · Zbl 1077.05500 |
| [252] | Gerschgorin S, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk, 1931, 7: 749-754. · JFM 57.1340.06 |
| [253] | Høyer, P.; Komeili, M., Efficient quantum walk on the grid with multiple marked elements, 42:1-42:14 (2017) · Zbl 1402.68066 |
| [254] | Watrous J, Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences, 2001, 62(2): 376-391. · Zbl 0990.68519 · doi:10.1006/jcss.2000.1732 |
| [255] | Aharonov, D.; Ambainis, A.; Kempe, J.; etal., Quantum walks on graphs, 50-59 (2001), New York · Zbl 1323.81020 |
| [256] | Kendon V, Quantum walks on general graphs, Int. J. Quantum Inf., 2006, 4(5): 791-805. · Zbl 1121.81025 · doi:10.1142/S0219749906002195 |
| [257] | Potocek V, Gabris A, Kiss T, et al., Optimized quantum random-walk search algorithms on the hypercube, Phys. Rev. A, 2009, 79: 012325. · doi:10.1103/PhysRevA.79.012325 |
| [258] | Tonchev H, Alternative coins for quantum random walk search optimized for a hypercube, Journal of Quantum Information Science, 2015, 5: 6-15. · doi:10.4236/jqis.2015.51002 |
| [259] | Ambainis A, Quantum search with variable times, Theory of Computing Systems, 2010, 47(3): 786-807. · Zbl 1204.68095 · doi:10.1007/s00224-009-9219-1 |
| [260] | Boyer M, Brassard G, Høyer P, et al., Tight bounds on quantum searching, Fortsch. Phys. Prog. Phys., 1998, 46(4-5): 493-505. · doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P |
| [261] | Grover L K, Fixed-point quantum search, Phys. Rev. Lett., 2005, 95: 150501. · Zbl 1255.81106 · doi:10.1103/PhysRevLett.95.150501 |
| [262] | Yoder T J, Low G H, Chuang I L, Optimal fixed-point quantum amplitude amplification using Chebyshev polynomials, Phys. Rev. Lett., 2014, 113: 210501. · doi:10.1103/PhysRevLett.113.210501 |
| [263] | Brassard G, Høyer P, and Tapp A, Quantum algorithm for the collision problem, ACM SIGACT News, 1997, 28: 14-19. · doi:10.1145/261342.261346 |
| [264] | Falk M, Quantum search on the spatial grid, arXiv: 1303.4127 [quant-ph]. · JFM 02.0554.02 |
| [265] | Buhrman H, Dürr C, Heiligman M, et al., Quantum algorithms for element distinctness, SIAM J. Comput., 2005, 34(6): 1324-1330. · Zbl 1081.68029 · doi:10.1137/S0097539702402780 |
| [266] | Belovs, A., Learning-graph-based quantum algorithm for k-distinctness, 207-216 (2012) |
| [267] | Jeffery S, Frameworks for quantum algorithms, PhD thesis, University of Waterloo, 2014. |
| [268] | Krovi H, Magniez F, Ozols M, et al., Quantum walks can find a marked element on any graph, Algorithmica, 2016, 74(2): 851-907. · Zbl 1336.68083 · doi:10.1007/s00453-015-9979-8 |
| [269] | Dohotaru C and Høyer P, Controlled quantum amplification, Proc. ICALP 2017, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017, 18: 1-13. · Zbl 1441.68057 |
| [270] | Ambainis, A.; Kokainis, M., Analysis of the extended hitting time and its properties (2012) |
| [271] | Portugal R, Santos R A M, Fernandes T D, et al., The staggered quantum walk model, Quantum Information Processing, 2016, 15: 85-101. · Zbl 1333.81213 · doi:10.1007/s11128-015-1149-z |
| [272] | Aggarwal, D.; Dadush, D.; Regev, O.; etal., Solving the shortest vector problem in 2n time via discrete Gaussian sampling, 733-742 (2014), New York |
| [273] | Chen Y, Chung K, and Lai C, Space-efficient classical and quantum algorithms for the shortest vector problem, Quantum Information and Computation, 2018, 18(3 & 4): 285-307. |
| [274] | Becker, A.; Ducas, L.; Gama, N.; etal., New directions in nearest neighbor searching with applications to lattice sieving, 10-24 (2016) · Zbl 1410.68093 |
| [275] | Laarhoven T, Search problems in cryptography, PhD dissertation, Eindhoven University of Technology, Eindhoven, 2015. · Zbl 1336.94060 |
| [276] | Ettinger M and Høyer P, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics, 2000, 25(3): 239-251. · Zbl 0967.68076 · doi:10.1006/aama.2000.0699 |
| [277] | Bacon, D.; Childs, A. M.; Dam, W., Optimal measurements for the dihedral hidden subgroup problem (2006) · Zbl 1117.81010 |
| [278] | Regev O, A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space, arXiv: quant-ph/0406151. |
| [279] | Babai L, On the complexity of canonical labeling of strongly regular graphs, SIAM J. Comput., 1980, 9: 212-216. · Zbl 0446.68052 · doi:10.1137/0209018 |
| [280] | Spielman D A, Faster isomorphism testing of strongly regular graphs, Proc. STOC 1996, ACM Press, New York, 576-584. · Zbl 0915.05104 |
| [281] | Wang F, The Hidden Subgroup Problem, Master’s Project, Aarhus Universitet, 2010. |
| [282] | Ettinger M and Høyer P, A quantum observable for the graph isomorphism problem, arXiv: quant-ph/9901029. · Zbl 0927.20001 |
| [283] | Beals, R., Quantum computation of Fourier transforms over symmetric groups, 48-53 (1997), New York · Zbl 0962.68070 |
| [284] | Boneh, D.; Lipton, R. J.; Coppersmith, D. (ed.), Quantum cryptanalysis of hidden linear functions, 424-437 (1995), Heidelberg · Zbl 0876.94023 |
| [285] | Hallgren S, Moore C, Roetteler M, et al., Limitations of quantum coset states for graph isomorphism, J. ACM, 2010, 57(6): 1-33. · Zbl 1327.68106 · doi:10.1145/1857914.1857918 |
| [286] | Moore C, Russell A, and Schulman L J, The symmetric group defies strong fourier sampling, SIAM J. Comput., 2008, 37(6): 1842-1864. · Zbl 1155.68029 · doi:10.1137/050644896 |
| [287] | Kawano, Y.; Sekigawa, H., Quantum fourier transform over symmetric groups, 227-234 (2013), New York · Zbl 1360.81111 |
| [288] | Kawano Y and Sekigawa H, Quantum Fourier transform over symmetric groups - improved result, J. Symb. Comp., 2016, 75: 219-243. · Zbl 1332.81032 · doi:10.1016/j.jsc.2015.11.016 |
| [289] | Williams, V. V.; Williams, R., Subcubic equivalences between path, matrix and triangle problems, 645-654 (2010), Las Vegas |
| [290] | Williams V V and Williams R, Finding, minimizing, and counting weighted subgraphs, SIAM J. Comput., 2013, 42(3): 831-854. · Zbl 1275.68080 · doi:10.1137/09076619X |
| [291] | Williams R, A new algorithm for optimal 2-constraint satisfaction and its implications, Theor. Comput. Sci., 348(2-3): 357-365. · Zbl 1081.68095 |
| [292] | Belovs, A., Span programs for functions with constant-sized 1-certificates, 77-84 (2012), New York · Zbl 1286.81043 |
| [293] | Grötschel M, Lovász L, and Schrijver A, Geometric Algorithms and Combinatorial Optimization, Springer, New York, 1988. · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4 |
| [294] | Lee, Y. T.; Sidford, A.; Wong, S. C., A faster cutting plane method and its implications for combinatorial and convex optimization, 1049-1065 (2015) |
| [295] | Brandão, F. G S. L.; Svore, K. M., Quantum speed-ups for solving semidefinite programs, 415-426 (2017), Berkeley |
| [296] | Apeldoorn, J. v.; Gilyén, A.; Gribling, S.; etal., Quantum SDP-solvers: Better upper and lower bounds, 403-414 (2017) |
| [297] | Apeldoorn J van and Gilyén A, Improvements in quantum SDP-solving with applications, arXiv: 1804.05058 [quant-ph]. · Zbl 07561592 |
| [298] | Brandão F G S L, Kalev A, Li T Y, et al., Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning, arXiv: 1710.02581v2 [quant-ph]. · Zbl 07561520 |
| [299] | Lee Y T, Sidford A, and Vempala S S, Efficient convex optimization with membership oracles, arXiv: 1706.07357 [cs.DS]. · Zbl 1452.68272 |
| [300] | Chakraborty S, Childs A M, Li T Y, et al., Quantum algorithms and lower bounds for convex optimization, arXiv: 1809.01731 [quant-ph]. |
| [301] | Apeldoorn J van, Gilyén A, Gribling S, et al., Convex optimization using quantum oracles, arXiv: 1809.00643v1 [quant-ph]. |
| [302] | Grassl, M.; Langenberg, B.; Roetteler, M.; etal.; Takagi, T. (ed.), Applying Grover’s Algorithm to AES: Quantum Resource Estimates, 29-43 (2016), Cham · Zbl 1405.81026 |
| [303] | Amy, M.; Matteo, O.; Gheorghiu, V.; etal.; Avanzi, R. (ed.); Heys, H. (ed.), Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3, 317-337 (2017), Cham · Zbl 1418.94028 |
| [304] | Dunjko V, Ge Y M, and Cirac I, Computational speedups using small quantum devices, arXiv: 1807.08970 [quant-ph]. |
| [305] | Schuld M, Bocharov A, Svore K, et al., Circuit-centric quantum classifiers, arXiv: 1804.00633 [quant-ph]. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
