@article {Hen2014,
title = {Continuous-time quantum algorithms for unstructured problems},
volume = {47},
number = {4},
year = {2014},
pages = {045305},
abstract = {We consider a family of unstructured optimization problems, for which we propose a method for constructing analogue, continuous-time (not necessarily adiabatic) quantum algorithms that are faster than their classical counterparts. In this family of problems, which we refer to as {\textquoteleft}scrambled input{\textquoteright} problems, one has to find a minimum-cost configuration of a given integer-valued n -bit black-box function whose input values have been scrambled in some unknown way. Special cases within this set of problems are Grover{\textquoteright}s search problem of finding a marked item in an unstructured database, certain random energy models, and the functions of the Deutsch{\textendash}Josza problem. We consider a couple of examples in detail. In the first, we provide an O (1) deterministic analogue quantum algorithm to solve the seminal problem of Deutsch and Josza, in which one has to determine whether an n -bit boolean function is constant (gives 0 on all inputs or 1 on all inputs) or balanced (returns 0 on half the input states and 1 on the other half). We also study one variant of the random energy model, and show that, as one might expect, its minimum energy configuration can be found quadratically faster with a quantum adiabatic algorithm than with classical algorithms.},
url = {http://stacks.iop.org/1751-8121/47/i=4/a=045305},
author = {Hen, Itay}
}