On the Power of Nonstandard Quantum Oracles - Complexity Theory and Oracle Models

Watch a conference talk from TQC 2023 exploring how different oracle designs impact the complexity of quantum property testing problems. Delve into research examining regular graphs of even degree encoded as invertible functions and presented through various oracle models. Learn about a one-query QMA protocol for testing disconnected subsets in graphs, and discover through representation theory why classical witnesses cannot help quantum verifiers efficiently decide this problem with in-place oracles. Explore an intriguing finding where simple oracle modifications prevent quantum verifiers from efficient decision-making even with unlimited witness access. Follow along as the presentation covers key concepts including complexity theory, quantum oracles, QCMA, spectral testing, randomized oracles, proof techniques, phase oracles, and pseudorandom states. Originally presented at the 18th Conference on the Theory of Quantum Computation, Communication and Cryptography at the University of Aveiro, this 23-minute talk provides theoretical insights into quantum information science and computational complexity.