摘要: In this talk, we describe two recent developments in quantum algorithms. The first new development is a algorithm for evaluating Boolean formula consisting of AND and OR gates size N time O(√N). This provides speedups any problem that can be expressed via formulas. result also extended to span problems, generalization an optimal function the black-box query model. The second solving systems linear equations. contrast with traditional algorithms run O(N2.37...) where system, runs O(logc N). It outputs state describing solution system.
arxiv.org
springer.com
core.ac.uk
harvard.edu
lu.lv 
acm.org 
sci-hub.st 参考文章(65)
Ben W. Reichardt, Andrew M. Childs, Robert Spalek, Shengyu Zhang, Every NAND formula on N variables can be evaluated in time O(N^{1/2+eps}) ,(2007)
Roger A. Horn, Charles R. Johnson, Matrix Analysis Cambridge University Press. ,(1985) , 10.1017/CBO9780511810817
Dan Boneh, Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract) international cryptology conference. pp. 424- 437 ,(1995)
Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Quantum algorithm for linear systems of equations. Physical Review Letters. ,vol. 103, pp. 150502- 150502 ,(2009) , 10.1103/PHYSREVLETT.103.150502
M. Szegedy, Quantum speed-up of Markov chain based algorithms foundations of computer science. pp. 32- 41 ,(2004) , 10.1109/FOCS.2004.53
Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland, Finding Is as Easy as Detecting for Quantum Walks Automata, Languages and Programming. pp. 540- 551 ,(2010) , 10.1007/978-3-642-14165-2_46
Andris Ambainis, Quantum random walks - new method for designing quantum algorithms conference on current trends in theory and practice of informatics. pp. 1- 4 ,(2008) , 10.1007/978-3-540-77566-9_1
Golub Gene H. Et.Al, Matrix Computations, 3rd Edition ,(2007)
Dan Boneh, Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions international cryptology conference. pp. 424- 437 ,(1995) , 10.1007/3-540-44750-4_34
Andris Ambainis, A nearly optimal discrete query quantum algorithm for evaluating NAND formulas arXiv: Quantum Physics. ,(2007)