A Caltech Library Service

Finding quantum algorithms via convex optimization

Childs, Andrew M. and Landahl, Andrew J. and Parrilo, Pablo A. (2007) Finding quantum algorithms via convex optimization. In: 2007 European Control Conference (ECC). IEEE , Piscataway, NJ, pp. 854-859. ISBN 978-3-9524173-8-6.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


In this paper we describe how to use convex optimization to design quantum algorithms for certain computational tasks. In particular, we consider the ordered search problem, where it is desired to find a specific item in an ordered list of N items. While the best classical algorithm for this problem uses log_2 N queries to the list, a quantum computer can solve this problem much faster. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find quantum algorithms using 4 log_(605) N ≈ 0.433 log_2 N queries, which improves upon the previously best known exact algorithm.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Parrilo, Pablo A.0000-0003-1132-8477
Additional Information:© 2007 IEEE.
Record Number:CaltechAUTHORS:20150331-150443251
Persistent URL:
Official Citation:Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A., "Finding quantum algorithms via convex optimization," Control Conference (ECC), 2007 European , vol., no., pp.854,859, 2-5 July 2007
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:56257
Deposited By: Ruth Sustaita
Deposited On:31 Mar 2015 23:18
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page