Quantum algorithms: an overview

Montanaro, School Of Mathematics, University Of Bristol, Bristol, Ashley Montanaro, You Can Also Search For This Author In, Author Information, Corresponding Author, Correspondence To

The task is to determine whether there exists an input to the circuit such that the output is 1. The answer should be ‘yes’ as there exists an input to the circuit such that the output is 1. boxed-text One way to solve the heuristic search problem classically is simply to repeatedly run A and check the output each time using f, which would result in an average of O(1/ϵ) evaluations of f. However, a quantum algorithm due to Brassard, Høyer, Mosca and Tapp22 can find w such that f(w)=1 with only O (1/ ε ) uses of f, and failure probability arbitrarily close to 0, thus achieving a quadratic speedup. For example, one of the most efficient classical algorithms known for the fundamental NP-complete constraint satisfaction problem 3-SAT is randomised and runs in time O((4/3)npoly(n)).23 Amplitude amplification can be applied to this algorithm to obtain a quantum algorithm with runtime O((4/3)n/2poly(n)), illustrating that quantum computers can speedup non-trivial classical algorithms for NP-complete problems. Adiabatic optimisation An alternative approach to quantum combinatorial optimisation is provided by the quantum adiabatic algorithm.30 The adiabatic algorithm can be applied to any constraint satisfaction problem (CSP) where we are given a sequence of constraints applied to some input bits, and are asked to output an assignment to the input bits, which maximises the number of satisfied constraints.

Visit Link