6533b86ffe1ef96bd12ce6a7

RESEARCH PRODUCT

New Developments in Quantum Algorithms

Andris Ambainis

subject

Discrete mathematicsOR gateTrue quantified Boolean formulaGeneralizationTheoryofComputation_GENERAL0102 computer and information sciencesSystem of linear equations01 natural sciences010201 computation theory & mathematicsQuantum stateComputerSystemsOrganization_MISCELLANEOUS0103 physical sciencesQuantum algorithm010306 general physicsBoolean functionQuantumMathematics

description

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.

yearjournalcountryeditionlanguage
2010-01-01
https://doi.org/10.1007/978-3-642-15155-2_1