Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Mathematics;quantum;computation;adiabatic;algorithms

Ioannou, Lawrence

University of Waterloo

关键词: Mathematics;    quantum;    computation;    adiabatic;    algorithms;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1129/1/lmioannou2002.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

One of the most important quantum algorithms is Grover;;s search algorithm [G96].Quantum searching can be used to speed up the search for solutions to NP-complete problems e.g. 3SAT.Even so, the best known quantum algorithms for 3SAT are considered inefficient.Soon after Grover;;s discovery, Farhi and Gutmann [FG96]devised a ;;continuous-time analogue;; of quantum searching.More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover;;s search algorithm can.I begin with a review of the discrete- and continuous-time models of quantum computation.I then make precise the notion of ;;efficient quantum algorithms;;, motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms.After reviewing threequantum search algorithms [F00,FG96,G96], I develop theadiabatic 3SAT algorithm as a natural extension of Farhi andGutmann;;s search algorithm.Along the way, I present theadiabatic search algorithm [vDMV01] and remark on itsdiscrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework.UPDATE (February 2003): Please see article http://arxiv.org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.