2026-07-22T19:23:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5545 2024-03-06T10:36:38Z ddc:004 open_access

Oracles with Costs Kimmel, Shelby Lin, Cedric Yen-Yu Lin, Han-Hsuan Quantum Algorithms Query Complexity Amplitude Amplification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shelby Kimmel and Cedric Yen-Yu Lin and Han-Hsuan Lin 2015 Is Part Of LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2015.1 urn:nbn:de:0030-drops-55459 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.1 eng https://creativecommons.org/licenses/by/3.0/legalcode