TY - GEN
T1 - New developments in quantum algorithms
AU - Ambainis, Andris
PY - 2010
Y1 - 2010
N2 - In this talk, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(√N). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N2.37...) where N is the size of the system, the quantum algorithm runs in time O(logc N). It outputs a quantum state describing the solution of the system.
AB - In this talk, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(√N). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N2.37...) where N is the size of the system, the quantum algorithm runs in time O(logc N). It outputs a quantum state describing the solution of the system.
UR - https://www.scopus.com/pages/publications/78349259673
U2 - 10.1007/978-3-642-15155-2_1
DO - 10.1007/978-3-642-15155-2_1
M3 - Conference paper
AN - SCOPUS:78349259673
SN - 364215154X
SN - 9783642151545
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 11
BT - Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings
T2 - 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010
Y2 - 23 August 2010 through 27 August 2010
ER -