Continuous-Time Quantum Algorithms for Unstructured Problems

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.

8 pages, 4 figures

References in corpus (8)

• Bounds for the adiabatic approximation with applications to quantum computation
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Quantum Speedup by Quantum Annealing
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Algorithmic approach to adiabatic quantum optimization
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
• Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations

Cited by in corpus (12)

• Adiabatic Quantum Computing
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Finding spin-glass ground states using quantum walks
• Quantum Gates with Controlled Adiabatic Evolutions
• Analog Nature of Quantum Adiabatic Unstructured Search
• Period Finding with Adiabatic Quantum Computation
• Quantum Annealing - Foundations and Frontiers
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• How Fast Can Quantum Annealers Count?
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations