Continuous-time quantum algorithms for unstructured problems
From MaRDI portal
Abstract: We consider a family of unstructured problems, for which we propose a method for constructing analog, continuous-time quantum algorithms that are more efficient than their classical counterparts. In this family of problems, which we refer to as `scrambled output' problems, one has to find a minimum-cost configuration of a given integer-valued n-bit function whose output values have been scrambled in some arbitrary 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 a deterministic analog 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.
Recommendations
Cited in
(3)
This page was built for publication: Continuous-time quantum algorithms for unstructured problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404810)
