Theorem 4 — IQP versus the full polynomial hierarchy relative to one oracle
OpenIQPForrelation832.SingleQuery.Supplement.theorem_4computational-complexityforrelationiqp-circuitsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
There is a total Boolean oracle on finite binary strings and a language such that
The IQP class uses one deterministic polynomial-time circuit generator, actual diagonal-unitary gates and plain phase queries between the two Hadamard layers, and a length-indexed polynomial-time accepting-outcome test. It allows no classical random choice among circuits. The PH class ranges over every fixed finite number of alternations of polynomially bounded witnesses over a polynomial-clocked oracle predicate. The same oracle occurs in both class-membership clauses; no recursive-oracle restriction or external hardness assumption is imposed. This companion isolates the oracle-separation conclusion also included in Theorem 3.
Differences from the source:
- reading: uniform classical generation of IQP circuits with efficient accepting-set membership → fixed structural parser, effective finite diagonal gate library, polynomial resource bound, and a polynomial-time outcome decider; reason: Definition 3 names no gate set; the standard uniform reading with a fixed effective finite library is taken, which only narrows IQP^O and so makes the separation stronger; raw total-oracle queries have empty labels and no oracle is supplied to the classical machines
Preamble
import Definitions.Def_IQPForrelation832_SingleQuery_Supplement_Uniform set_option autoImplicit false
Formal statement
namespace IQPForrelation832.SingleQuery.Supplement
open QAlgorithms QAlgorithms.Complexity
theorem theorem_4 :
∃ (O : TotalOracle) (L : Language Bool), L ∈ IQPO O ∧ L ∉ PHO O := by sorry
end IQPForrelation832.SingleQuery.Supplement
Source
Quentin Buzet, André Chailloux, IQP circuits for 2-Forrelation, STOC 2027 submission #832 (October 2026), p. 24, Theorem 4; proof pp. 24. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/832.pdf