Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2007 | Published
Book Section - Chapter Open

Finding quantum algorithms via convex optimization

Abstract

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.

Additional Information

© 2007 IEEE.

Attached Files

Published - 07069011.pdf

Files

07069011.pdf
Files (233.9 kB)
Name Size Download all
md5:268b3f9046e1455de7aaafecf554caa7
233.9 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023