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
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.