Optimal Quantum Algorithms for Ordered Search

arXiv:2609.34293 · quant-ph · Submitted 2026-09-28 · Read on arXiv

quant-ph

Submitted: 2026-09-28

Updated: 2026-09-28

Terminology

• Query Complexity — 6× in this paper · explained in 2 episodes
• Core — 1× in this paper · explained in 2 episodes
• Hilbert Space — 1× in this paper · explained in 2 episodes
• Verification — 1× in this paper · explained in 2 episodes

Sources

• A Limit on the Speed of Quantum Computation for Insertion into an Ordered List
• A better lower bound for quantum algorithms searching an ordered list
• Invariant Quantum Algorithms for Insertion into an Ordered List
• Quantum lower bounds by quantum arguments
• Quantum complexities of ordered searching, sorting, and element distinctness
• Quantum Search in an Ordered List via Adaptive Learning
• Improved quantum algorithms for the ordered search problem via semidefinite programming
• Optimal quantum adversary lower bounds for ordered search
• One-Way Ticket to Las Vegas and the Quantum Adversary
• Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity