2026-07-29T10:45:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18321 2024-03-06T11:01:40Z ddc:004 open_access

On the Power of Nonstandard Quantum Oracles Bassirian, Roozbeh Fefferman, Bill Marwaha, Kunal quantum complexity QCMA expander graphs representation theory We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roozbeh Bassirian and Bill Fefferman and Kunal Marwaha 2023 Is Part Of LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2023.11 urn:nbn:de:0030-drops-183215 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode