Pages

June 26, 2010

New Developments in Quantum Algorithms

Ad Support : Nano Technology   Netbook    Technology News    Computer Software

There is a new quantum algorithm for quantum speedups for any problem that can be expressed via Boolean formulas and another for solving systems of linear equations.

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(root 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.


Here is the 11 page paper that describes both algorithms.

In 2007, in a breakthrough result, Farhi et al. showed that the full binary AND-OR tree can be evaluated in O(pN) quantum time in continuous-time counterpart of the query model.
Several improvements followed soon. Ambainis et al. translated the algorithm of Farhi to the conventional discrete time quantum query model and extended it to evaluating arbitrary Boolean formulas with O(N1/2+o(1)) quantum queries.

Soon after, Reichardt and ˇ Spalek discovered a far-reaching generalization of this result. Namely, the quantum algorithm was generalized to evaluating span programs. A span program is an algebraic model of computation, originally invented for proving lower bounds on circuit size

If you liked this article, please give it a quick review on Reddit, or StumbleUpon. Thanks

Supporting Advertising

Business Success
   How to Make Money    
Executive Jobs    
Paid Surveys


Thank You
blog comments powered by Disqus