Composing quantum algorithms

Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing "efficient" algorithms should result in an "efficient" algorithm – even using this intuition to justify our definition of "efficient". Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms do not compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. In this article, we try to give some intuition for these results: why composing quantum algorithms is tricky, particularly in the zero-error setting, but why it nonetheless works better than classical composition in the bounded-error setting.

• View at Publisher

Full Text ( Final Version , 1mb )