New Developments in Quantum Algorithms
arXiv:1006.4014 · doi:10.1007/978-3-642-15155-2_1
Abstract
In this survey, 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(\sqrt{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(N^{2.37...}) where N is the size of the system, the quantum algorithm runs in time O(\log^c N). It outputs a quantum state describing the solution of the system.
11 pages, 1 figure, to appear as an invited survey talk at MFCS'2010
References in corpus (11)
- Quantum algorithm for solving linear systems of equations
- Exponential algorithmic speedup by quantum walk
- Anderson localization casts clouds over adiabatic quantum optimization
- Faster quantum walk algorithm for the two dimensional spatial search
- How Powerful is Adiabatic Quantum Computation?
- Quantum walks can find a marked element on any graph
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
- Black-box Hamiltonian simulation and unitary implementation
- Quantum algorithms for testing properties of distributions
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
- Quantum algorithms for formula evaluation