Itay Hen

Continuous-time quantum algorithms for unstructured problems

TitleContinuous-time quantum algorithms for unstructured problems
Publication TypeJournal Article
Year of Publication2014
AuthorsI. Hen

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 `scrambled input' 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's search problem of finding a marked item in an unstructured database, certain random energy models, and the functions of the Deutsch–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.