Oracles with costs

DOI10.4230/LIPICS.TQC.2015.1MaRDI QIDQ5278017zbMATH OpenOpenAlexFDO

Authors Shelby Kimmel, Cedric Yen-Yu Lin, Han-Hsuan Lin

Publication date 12 July 2017

Full work available at URL https://arxiv.org/abs/1502.02174

zbMATH Keywords

amplitude amplificationquantum algorithmsquery complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.

Recommendations

• STACS 2004
• Improved Algorithms for Quantum Identification of Boolean Oracles
• Improved algorithms for quantum identification of Boolean oracles
• Quantum oracles in terms of universal gate set
• An optimal quantum algorithm for the oracle identification problem

Cited in

(3)

• On low for speed oracles
• Quantum procedures for nested search problems -- with applications in cryptanalysis
• Improvements to quantum search techniques for block-ciphers, with applications to AES

This page was built for publication: Oracles with costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5278017)