Unlocking Quantum Potential: The Impact of Nonstandard Oracles 🔍

Kunal Marwaha On the power of nonstandard quantum oracles https://arxiv.org/abs/2212.00098 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. Online talk. July 28, 2023 --------- TQC 2023 | 24-28 July 2023, University of Aveiro, Portugal http://tqc-conference.org 18th Conference on the Theory of Quantum Computation, Communication and Cryptography. TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field. Organisation: Squids - Schools for Quantum Information Development Universidade de Aveiro: Departamento de Matemática, CIDMA & Fábrica Sponsors: Phasecraft, UK Google Quantum AI, USA QuSoft, The Netherlands Quantum for Life Centre, Denmark Technology Innovation Institute, UAE ML4Q, Germany Dulwich Quantum