Open Research Index

A Separation Between Types of Quantum Oracle Separations

Scott Aaronson, Adam Bouland, Jordan Docter, Barak Nehoran

arXivarxiv/2609.38704Sep 30, 2026quant-phscore 0

Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.38704
curl -X POST /api/v1/records/arxiv/2609.38704/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.38704/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'