[BFM23] On the Power of Nonstandard Quantum Oracles

Authors: Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha | Venue: TQC 2023 | Source

Abstract

We study how the choice of oracle model affects the QMA vs. QCMA question. We encode a regular graph as an invertible function and give a one-query QMA protocol to test whether the graph has a small disconnected subset. Using representation theory of the symmetric group, we show that no classical witness enables a quantum verifier to decide this problem relative to an in-place oracle. We also show a simple modification to the standard oracle that prevents any quantum verifier from deciding the problem, even with an unbounded witness. These results highlight how the oracle model can dramatically affect the apparent power of quantum versus classical witnesses.