New Developments in Quantum Algorithms

Details New Developments in Quantum Algorithms New Developments in Quantum Algorithms

2010-06-21

arxiv.org/abs/1006.4014v1

Physics

Quantum Physics

11 pages, 1 figure, to appear as an invited survey talk at MFCS'2010

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

New Developments in Quantum Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New Developments in Quantum Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Developments in Quantum Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-600943