Improved quantum algorithms for the ordered search problem via semidefinite programming

Abstract

One of the most basic computational problems is the task of finding a desired 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 the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find new quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using 4 log_{605} N \approx 0.433 log_2 N queries, which improves upon the previously best known exact algorithm.

8 pages, 4 figures

References in corpus (3)

• Strengths and Weaknesses of Quantum Computing
• Invariant Quantum Algorithms for Insertion into an Ordered List
• Quantum Search in an Ordered List via Adaptive Learning

Cited by in corpus (12)

• Certainty and Uncertainty in Quantum Information Processing
• Prospective Algorithms for Quantum Evolutionary Computation
• Optimal quantum adversary lower bounds for ordered search
• Channel-Adapted Quantum Error Correction
• Quantum Search in an Ordered List via Adaptive Learning
• Reconstructing Strings from Substrings with Quantum Queries
• Quantum Machine Learning and its Supremacy in High Energy Physics
• Partial Boolean functions with exact quantum 1-query complexity
• Engineering and Business Applications of Sum of Squares Polynomials
• Quantum Communication-Query Tradeoffs
• A Formulation of a Matrix Sparsity Approach for the Quantum Ordered Search Algorithm
• Quantum search of partially ordered sets