PaperlayerView exact revision on arXiv

Source-linked AI summary

A Separation Between Types of Quantum Oracle Separations

Scott Aaronson, Adam Bouland, Jordan Docter, Barak Nehoran

arXiv:2609.38704v1quant-phcs.CC

TL;DR

The paper asks how quantum oracle types affect whether complexity classes remain equal or become separated. It classifies the oracle models that can separate PostBQP from PreciseBQP, finding both equality and separation results across the specified models.

  • Problem

    PostBQP and PreciseBQP both equal PP relative to classical oracles, but their relationship becomes more complicated with quantum oracles.

    Source: §1.1 · p. 3

  • Method

    The paper classifies, within its oracle-pantheon taxonomy, which oracle models preserve equality between PostBQP and PreciseBQP and which separate them.

    Source: §1.1 · p. 3

  • Results

    PostBQP and PreciseBQP are equal for real or polynomial-dimensional unitary oracles and when inverse or conjugate queries are allowed, but a complex superpolynomial-dimensional diagonal unitary without those queries separates them.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The relativizing behavior of these classes depends subtly on the quantum oracle model being considered.

    Source: §1.6 · p. 9

    The equivalence between nonzero-probability postselection and the inverse-exponential formulation need not hold relative to an arbitrary unitary oracle.

    Source: §2 · p. 9

Abstract

from arXiv · show

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 separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.

1 Introduction

This section examines how oracle access types affect quantum relativization, comparing oracle pantheons by their ability to separate complexity classes and classifying the relationship between PostBQP and PreciseBQP across specified models. It presents a query-lower-bound argument for a complex, superpolynomial-dimensional unitary-oracle separation and raises further questions about pantheon separations.

1 Introduction

  • Recent quantum-oracle results show that changing access modes, including inverse, conjugate, or controlled queries, can alter the difficulty of quantum tasks.The introduction situates this work among studies of unitary and state-preparation oracles.Source: §1 · p. 2

1.1 Our results

  • The paper defines meta-complexity of quantum relativization by asking which oracle pantheons separate pairs of classes, with pantheons partially ordered by their separation power.Pantheons A and B are separated when some pair of classes separates relative to an oracle from A but remains equal relative to every oracle from B.Source: §1.1 · pp. 2–3
  • PostBQP and PreciseBQP are equal for real or polynomial-dimensional unitary oracles and with inverse or conjugate access, but separable by a complex one-qubit state oracle or a complex, superpolynomial-dimensional diagonal unitary without inverse or conjugate access.The single-qubit state separation cannot be lifted to an analogous single-qubit unitary separation.Source: §1.1 · p. 3

1.2 Proof sketch

  • The proof sketch proceeds from a one-qubit state-oracle separation and its limits, then develops a complex Forrelation-like unitary separation for the complex, inverse-free case.It also previews no-go results for attempts to generalize the state separation to low-dimensional unitaries.Source: §1.2 · p. 4

1.2.1 A one-qubit state separation

  • For the state oracle, phase averaging yields positive polynomials whose logarithmic derivatives are O(t), so a constant acceptance-ratio change across width ϵ requires t = Ω(1/ϵ).Setting ϵ = 2^-n gives a PreciseBQP state-oracle problem requiring exponentially many queries for PostBQP; this lower bound concerns structured polynomials, not arbitrary complex rational functions.Source: §1.2.1 · p. 5

1.3 No-go for unitary separations: polynomial dimensional

  • A d-dimensional unitary can implement its complex conjugate up to global phase using d−1 queries, implying polynomial-dimensional unitaries cannot hide conjugate entries from polynomial-time algorithms.This yields equivalence of PostBQP and PreciseBQP for polynomial-dimensional unitary oracles.Source: §1.3 · p. 6

1.4 No-go for unitary separations: real, conjugate, or inverse access

  • With inverse access, coherent reversal encodes a PreciseBQP acceptance probability as an amplitude; with conjugate access, postselected gate teleportation supplies inverse access, establishing the corresponding equality.The paper also states equality for real unitary oracles, while this passage describes the inverse- and conjugate-access proof methods.Source: §1.4 · p. 6

1.5 A unitary separation with complex, superpoly dimensional oracles

  • For complex, inverse-free unitaries, the authors construct diagonal-oracle distributions that PreciseBQP distinguishes but PostBQP cannot distinguish on average, yielding a separation through standard diagonalization.The construction uses a complex Forrelation-like promise problem whose imaginary components are necessary to the separation, and a polynomial-method lower bound after symmetrization.Source: §1.5 · pp. 6–7
  • The proof uses nonnegative acceptance-probability terms and multiplicative closeness of conditional distributions, whose broad densities change little under the relevant shifts.The terms are bounded because they are quantum-algorithm acceptance probabilities; the broad-density argument uses d ≫ t.Source: §1.5 · pp. 7–8
  • Correctness forces the accepting-to-rejecting ratio to change by at least four, yielding a query lower bound for distinguishing the two oracle distributions.Source: §1.5 · p. 8

1.6 Discussion

  • It notes a one-qubit unitary separation of QCMA and QCMA1 from and [Aar08], while their state-oracle relation remains open, and urges separating all listed pantheon pairs.The discussion also proposes extending the classification to other quantum complexity classes.Source: §1.6 · p. 9

2 Preliminaries

The preliminaries fix the circuit, oracle-access, and complexity-class conventions used in the paper. They also define oracle pantheons and state the classification result for which pantheons can be separated.

Complexity classes

  • PostBQP requires bounded-error acceptance conditioned on a postselection event, while PreciseBQP uses polynomial-time computable completeness and soundness thresholds.For PostBQP, the stated conditional acceptance bounds are at least 2/3 on yes-instances and at most 1/3 on no-instances.Source: §2 · p. 9

Circuit conventions

  • The postselection convention explicitly requires inverse-exponential success probability, since nonzero success alone need not be equivalent relative to arbitrary unitary oracles.The fixed-gate compilation framework allows inverse-exponential accuracy with polynomial overhead.Source: §2 · pp. 9–10

Oracle access

  • A unitary oracle is a sequence of polynomial-qubit unitaries, and the default model supplies ordinary query access unless additional gates are specified.The access variants include controlled, inverse, and entrywise-conjugate queries.Source: §2 · p. 10
  • A state oracle supplies a fresh copy of its specified state on each query, with no adjoint or other purification access.The paper also includes single-qubit state-preparation oracles among its pantheons.Source: §2 · pp. 10–11

Oracle pantheons

  • Theorem 2.6 states separations between every pantheon in {D, U, UT, S, S2} and every pantheon in {Upoly, R, D∗, U∗, U†, U, F}.These labels distinguish oracle families by properties including dimension, reality, access to inverse or conjugate queries, and whether the oracle prepares a state.Source: §2 · p. 11

3 Equivalence with inverse or conjugate access

Inverse or conjugate query access makes PostBQP and PreciseBQP equivalent relative to any unitary oracle. The proofs use postselected thresholding, with conjugate access supplying an inverse query through teleportation.

3.1 Inverse access

  • Inverse access lets a circuit run backward, placing its acceptance probability in an amplitude that postselection can compare against an exponentially close threshold.The thresholding lemma distinguishes acceptance probabilities separated by an inverse-exponential gap.Source: §3.1 · p. 11
  • PostBQP and PreciseBQP are equal relative to any unitary oracle when inverse queries are available.The proof establishes both containments between the classes.Source: §3.1 · pp. 11–12
  • The inverse-access construction retains inverse-exponential postselection probability, and fixed-gate compilation preserves the bounded-error inequalities with polynomial overhead.The amplified ideal circuit has joint postselection probability at least 2^-q(n) for some polynomial q; compilation changes conditional acceptance probability by at most 1/50.Source: §3.1 · p. 12

3.2 Conjugate access

  • PostBQP and PreciseBQP are also equal relative to any unitary oracle when conjugate queries are available.Conjugate queries implement inverse-query gates on postselected branches using teleportation, after which the thresholding lemma applies.Source: §3.2 · p. 12
  • A conjugate-query teleportation succeeds with probability d^-2 per oracle gate, so t queries succeed jointly with probability d^-2t.Because log d and t are polynomial, this joint probability is inverse exponential, sufficient for postselected thresholding.Source: §3.2 · p. 12

4 Equivalence with poly-dimension oracles

A d-dimensional unitary’s complex conjugate can be simulated exactly, up to a global phase, with d−1 queries. For polynomial-dimensional oracles, the approximate implementation remains efficient enough to rule out a separation.

4 Equivalence with poly-dimension oracles

  • The isometry V and its inverse can be approximated to operator-norm error δ using poly(d, log(1/δ)) gates.The passage gives the efficient approximate Schur transform followed by compilation over the fixed gate set as an implementation route.Source: §4 · p. 13
  • d−1 queries to a d-dimensional unitary simulate its complex conjugate exactly up to the irrelevant global phase det(U)−1.The construction uses the conjugate representation inside the (d−1)-fold tensor product.Source: §4 · pp. 13–14
  • For polynomial d, choosing δ ≤ μ/(200t) keeps the compiled simulation polynomial-time and changes conditional acceptance probability by at most 1/50.The hybrid argument bounds the final-state change by 2tδ, while the compiled circuit retains inverse-exponential postselection probability.Source: §4 · p. 14

5 Quantum state oracle separation

The section constructs a single-qubit state-oracle setting in which PreciseBQP solves a promise problem that PostBQP cannot solve with polynomially many queries. A lower bound and diagonalization yield a state oracle separating the classes.

5 Quantum state oracle separation

  • A quantum state oracle Oψ separates the classes: PostBQP^Oψ is strictly contained in PreciseBQP^Oψ.The separation follows from an exponential PostBQP query lower bound for a promise problem over single-qubit state oracles.Source: §5 · p. 14

5.2 Proof outline

  • The proof outline pairs a PreciseBQP solver with an Ω(2^n)-query lower bound for PostBQP on the same promise problem.The stated lemma says no PostBQP algorithm solves the problem with fewer than the exponential query bound.Source: §5.2 · p. 15

5.1 Quantum state oracle

  • The promise problem uses single-qubit states with τ=1/2 or τ=1/2+2^-n, which a PreciseBQP query algorithm can distinguish.Measuring one copy in the standard basis gives acceptance probability 1/2 or 1/2+2^-n, respectively.Source: §5.1 · p. 14, §5.2 · p. 15

5.3 PostBQP query lower bound

  • Phase averaging makes the acceptance analysis a ratio of positive-coefficient polynomials, limiting sensitivity to the small change in τ and forcing t=Ω(2^n).The argument bounds the derivative of the rational function representing acceptance probability.Source: §5.3 · pp. 16, 18

5.4 Proof of state oracle separation

  • Diagonalization chooses state-oracle components that defeat each enumerated PostBQP machine, while the resulting oracle still gives strict containment.The construction uses the promise-problem lower bound to choose a failing component at a fresh input length.Source: §5.4 · p. 18

6 Superpoly dimensional unitary oracle separation

The section separates PostBQP from PreciseBQP using forward-only access to complex diagonal unitaries of superpolynomial dimension. A one-query PreciseBQP test contrasts distributions that polynomial-query PostBQP algorithms cannot reliably distinguish.

6.1 PreciseBQP algorithm

  • One query distinguishes D_a from D_-a with completeness–soundness gap a/d; at input length n, the construction gives gap 2^-n.The test prepares a block qubit and uniform index register, applies U, then measures the block qubit after a Hadamard.Source: §6.1 · pp. 18–19

6.2 PostBQP query lower bound

  • For t=poly(n) and d=2^n, the expected sums of squared moduli change by only a 1+o(1) multiplicative factor between D_a and D_-a, unlike the factor of at least four required for correct postselection.The comparison uses the absence of U† or conjugate access and applies to joint acceptance and rejection probabilities.Source: §6.2 · p. 19, Then every sum of squares P defined… · p. 23

Then every sum of squares P defined above satisfies

  • After phase symmetrization, each surviving term depends on at most t coordinates; the conditional marginals on such coordinates are pointwise 1+o(1) close, so the polynomial expectations are also close.The comparison parameter δ_d,t,a tends to zero when a=O(1), t=poly(n), and d=2^n.Source: §6.2 · pp. 19–20, Then every sum of squares P defined… · p. 20

6 Superpoly dimensional unitary oracle separation

  • A complex diagonal unitary oracle of superpolynomial dimension, without inverse or conjugate queries, gives PostBQP^U ⊊ PreciseBQP^U.The oracle is constructed by diagonalization, and the separation uses a one-query PreciseBQP decision procedure.Source: §6.3 · p. 23

6.3 Proof of unitary oracle separation

  • Diagonalization selects unitary components that defeat every polynomial-time PostBQP machine, while Proposition 6.1 puts the resulting language in PreciseBQP.The construction uses the lower bound at fresh input lengths and has one query with an inverse-exponential gap.Source: §6.3 · p. 23

AI Disclosure

The authors report that AI tools assisted with key steps in the oracle-separation proof, and that the authors verified the content.

AI Disclosure

  • GPT 5.1 and 5.6 assisted with key steps of the separation proof; the authors report verifying the content, including references.The equivalence proofs were human-generated, while the separation assistance was subsequently distilled and simplified by the authors.Source: AI Disclosure · p. 23

A Proof of the central density estimate

The proof represents the density of a sum of independent cosine variables through its characteristic function. It controls the error in a Gaussian differential equation and uses that control to extend a density lower bound across a central window.

A Proof of the central density estimate

  • For m ≥ 5, the density f_m is continuously differentiable, as established from the integrability needed for Fourier inversion and differentiation under the integral.The characteristic function of each cosine variable is J0, so independence gives J0(ξ)^m for the sum.Source: A Proof of the central density estimate · p. 26
  • The proof controls R_m, the error in the Gaussian differential equation, through the Fourier representation, using cancellation near zero and bounds away from zero.The cancellation makes the error smaller than the main Gaussian term; continuity supplies a bound away from zero.Source: A Proof of the central density estimate · pp. 26–27
  • A variance-based density lower bound at x0 ∈ [-m^1/2, m^1/2] is carried across the central window using R_m's integrating-factor identity.The proof states that f_m(x0) ≥ 1/(4√m).Source: A Proof of the central density estimate · p. 28
Loading 2609.38704v1…