PaperlayerView exact revision on arXiv

Source-linked AI summary

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

Atul Mantri

arXiv:2610.37635v1quant-phcs.CCcs.CR

TL;DR

The paper addresses whether a classical polynomial-time verifier can check polynomial-time quantum computation without computational assumptions. It constructs an oracle-relative verification protocol for a language exactly decidable in quantum polynomial time but outside PH.

  • Problem

    It is unknown whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions.

    Source: §1 · p. 3

  • Method

    A recursive Fourier sampling variant lets a quantum algorithm recover secrets exactly while a classical verifier checks the prover’s secrets recursively.

    Source: §1 · p. 4

  • Results

    Relative to a classical oracle, the language lies outside PH and has a public-coin proof with perfect completeness and soundness error at most 1/4.

    Source: §1 · p. 3, §1.1 · p. 4

  • Takeaways & Limitations

    The result proves that such classical verification can extend beyond AM relative to an oracle, contrary to what was previously established for this proof-system setting.

    Source: §1 · p. 3

    The lower bound does not cover recursive Fourier sampling with a fixed polynomial-time predicate; whether that variant lies outside PH relative to an oracle remains open.

    Source: §7.4 · p. 43

Abstract

from arXiv · show

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so H{\aa}stad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-\Omega(n)}$ when the answer of a random instance is flipped by changing a single leaf.

1 Introduction

The section introduces an oracle language exactly decidable in quantum polynomial time, outside the polynomial hierarchy, and verifiable by a classical interactive proof with an efficient quantum honest prover, with slowly growing resource bounds and a matching message lower bound. It also presents a switching theorem for recursive restrictions in which one secret determines both fixed code bits and the free data coordinate, and uses the freedom of the data tables in the lower bound.

1 Introduction

  • An oracle language lies outside PH while an exact quantum algorithm decides it and a public-coin classical protocol has perfect completeness and soundness error at most 1/4.Soundness holds against computationally unbounded provers; the protocol uses at most log n/4 messages on input 1^n.Source: §1 · p. 3, §1.1 · p. 4
  • The recursive Fourier-sampling variant encodes secrets in code tables that address data tables, while a new switching theorem bounds how constant-depth circuits respond to flipping one leaf.For sufficiently tall instances, circuits of size 2^poly(n) change their output with probability at most 2^-Ω(n); the correlated restrictions fix code bits and choose free leaves using the same secrets.Source: §1 · p. 4, §1.1 · p. 7

1.1 Our results

  • For any unbounded polynomial-time computable f, a variant uses at most f(n) messages and 2f(n) queries per participant; for query bound Q(n), it uses ⌊log2 Q(n)⌋ messages.The variants retain exact quantum decision, perfect completeness, and soundness error at most 1/4 against computationally unbounded provers.Source: §1.1 · pp. 5–6
  • For a suitable oracle, every qualifying verifier needs more than β_V h(n) messages on infinitely many input lengths, even with private coins and computationally unbounded honest provers.The protocol using 2h(n) messages is therefore optimal up to a verifier-dependent constant factor.Source: §1.1 · p. 6
  • The construction works with code families beyond Hadamard codes and tolerates code tables within a fixed relative distance below 1/4 of a codeword.For the noisy-table promise, a bounded-error quantum algorithm and public-coin proof achieve completeness at least 0.99 and soundness at most 0.01 with polynomially many messages; the circuit lower bound is unchanged.Source: §1.1 · p. 8

1.2 Related work

  • Earlier recursive Fourier-sampling verification established exclusion from MA but left exclusion from PH open; prior Forrelation separations lacked known classical proofs with efficient quantum honest provers.The paper positions its contribution as a decision language verified by a single prover and excluded from every level of PH relative to an oracle.Source: §1.2 · p. 8

1.3 Techniques

  • The switching theorem handles correlated random projections because the same secret fixes code bits and selects the free coordinate, a dependence not covered by independent-restriction switching lemmas.The fixed codeword reveals the free coordinate, so one level can turn a small-width CNF into an AND of arbitrarily many free variables.Source: §1.3 · p. 9
  • Unlike fixed-predicate recursive Fourier sampling [BV97, Section 8.4; McK10], each data-table entry here is its subtree’s value, leaving the table unconstrained except at a prescribed selected entry.The lower bound exploits this freedom through an auxiliary experiment with independently chosen secrets and data tables, conditioned on selected entries.Source: §1.3 · p. 9
  • The proof controls this dependence with an algebraic bound on the first satisfied DNF term, then converts sensitivity to certificates and builds truncated decision trees across levels.Its one-sided approximation has an error bound for each fixed assignment to free variables, allowing errors to compose over a constant number of levels.Source: §1.3 · p. 10

2 Proof outline

The proof outline builds a recursive table problem whose quantum algorithm recovers secrets exactly, then uses a classical verifier and a switching argument to establish verification and circuit hardness. The oracle stores only leaves, and a separate argument makes the protocol's message count optimal up to a verifier-dependent constant.

2.1 The problem and the distributions

  • Each node's secret is encoded by a code table and addresses an unconstrained data table; recursively composing these nodes leaves only the exponentially large leaf table as input.The dimensions shrink by a factor of sixteen per level, up to rounding, and the construction is described using the Hadamard code.Source: §2.1 · p. 10, §2 · p. 10
  • Using independent random projections at each level, the coupled root-value instances differ in exactly one leaf, while each node's secret determines both fixed code bits and the free data coordinate.The composition remains defined on the whole cube, including assignments that are not valid tree values.Source: §2.1 · pp. 10–11

2.2 The quantum algorithm and the protocol

  • The quantum algorithm recovers each secret with a Hadamard transform, uses three recursive calls per level, and makes 3h leaf queries; the verifier batches claimed secrets by height and tests fresh random code entries and the selected data entry.Conditioning on the history and claimed secrets yields a soundness bound of 4^-F for a list with F false claims; batching gives 2h messages and perfect completeness.Source: §2.2 · p. 11

2.3 The constant-depth circuit lower bound

  • For sufficiently tall instances, constant-depth circuits of size 2^poly(n) change their output on the coupled pair with probability at most 2^-Ω(n).The switching argument bounds certificate complexity through sensitivity and pointwise approximation; several projection levels are needed because one level can leave an accepting input with certificate complexity as large as the number of blocks.Source: §2.3 · pp. 11–13

2.4 The oracle

  • The oracle stores valid instances' leaves and diagonalizes against polynomial-time predicates by finding instances on which their induced constant-depth circuits err.It fixes queried addresses after each stage, preserving those errors while defining the unary language by the root value.Source: §2.4 · p. 14

2.5 The lower bound on the number of messages

  • Every correct protocol for a suitable oracle needs at least a verifier-dependent constant fraction of the proposed protocol's messages on infinitely many lengths.The lower-bound argument reduces an r-round public-coin protocol to a two-message verifier with n^O(r) queries, then uses width reduction to force a large distinguishing DNF.Source: §2.5 · p. 14

3 Preliminaries

The preliminaries establish the Boolean-function and circuit notions used later, define oracle complexity classes and interactive proof systems, and specify codes that permit exact quantum secret recovery.

3 Preliminaries

  • DNFs and CNFs are measured by width and number of terms or clauses, while circuit depth counts gates along a longest path and AC0 denotes constant-depth, polynomial-size circuits.The later lower-bound circuits have constant depth and size 2^poly(n) on 2^Θ(n) inputs.Source: §3 · p. 15
  • Decision trees query variables along paths, certificates fix coordinates sufficient to force an output, and projections substitute constants or free variables into input coordinates.Projected DNFs and CNFs do not increase width after normalization.Source: §3 · pp. 15–16

3.1 Oracle classes and interactive proof systems

  • EQPO comprises languages decided exactly by uniform polynomial-size quantum circuits with oracle gates, while interactive proofs use randomized polynomial-time oracle verifiers and classical communication.The honest prover may be an efficient quantum algorithm; soundness is against classical or quantum provers.Source: §3.1 · p. 16
  • Public-coin systems use uniformly random verifier messages and a fixed input-determined schedule, and PH relative to an oracle is the union of alternating polynomial-quantifier classes.The verifier's decision and oracle queries can be deferred until interaction ends.Source: §3.1 · p. 16

3.2 Codes with exact quantum decoders

  • The code family has efficiently computable coordinates of bounded polynomial degree and an exact quantum decoder for the phase state, enabling secret recovery and supporting the circuit lower bound.Distinct codewords have relative distance exactly 1/2, so the code is injective.Source: §3.2 · p. 17

4 The recursive problem and the distributions

The recursive problem encodes each node's value by a code-addressed entry in a data table, with only leaf values supplied as input. Random projections couple instances of opposite root values so they differ at one leaf while retaining correlated restrictions.

4.1 Trees and the promise

  • A height-j tree has a node whose code and data children are disjoint height-(j−1) trees, and validity requires the code-child values to form a codeword.The node value is the data-child value at the secret encoded by that codeword; the leaves uniquely determine node values and secrets.Source: §4.1 · p. 18
  • The promised input is the leaf table of a valid tree, and its answer is the root value; for positive height, the leaf table has exponentially many bits in the size parameter.The dimensions decrease toward the root, while the leaf-address length remains linear in n.Source: §4.1 · pp. 18–19

4.2 Random projections and the coupled pair

  • At each node, a random projection fixes the codeword of a uniform secret and other data entries, leaving only the data entry selected by that same secret free.Thus the fixed code bits and free coordinate are correlated, unlike restrictions that fix other coordinates independently.Source: §4.2 · p. 19
  • Using the same independent projections for both root values produces valid coupled instances that differ in exactly one leaf, with all secrets and other leaves matching.Across a block of levels, the composed projection has exactly one free leaf and is independent of the prescribed root value.Source: §4.2 · p. 19

5 Exact quantum evaluation and classical verification

A clean quantum recursion decodes tree values exactly, while a classical verifier checks claimed secrets through recursive code and data claims. Batching claims by height yields perfect completeness, soundness at most 1/4, and 2j messages for a height-j claim.

5.1 The exact quantum algorithm

  • A clean quantum algorithm computes every valid height-j tree exactly using 3^j leaf queries and time 3^j poly(n, j).Cleanliness lets the algorithm be called in superposition over child subtrees without retaining information about their addresses.Source: §5.1 · pp. 20–21

5.2 Recursive verification

  • In the recursive protocol, the prover sends a claimed secret; the verifier checks three random code-child values and the data child addressed by that secret.All four recursive checks are executed in the prescribed order, and the verifier accepts only if all accept.Source: §5.2 · pp. 21–22

5.3 Verification batched by height

  • Height batching sends secrets for all current claims together, then reveals all random challenges together, requiring joint soundness control over the resulting list.The next list is determined by the transcript, and the soundness analysis tracks the number of false claims jointly.Source: §5.3 · pp. 22–23
  • For a list containing F false claims, the batched protocol accepts with conditional probability at most 4^-F.Three independent code checks make a wrong-secret induction factor 125/512, below 1/4.Source: §5.3 · p. 23
  • True claims are accepted with probability one, false claims with probability at most 1/4, and a height-j claim uses 2j public-coin messages.The honest quantum prover recovers each secret exactly; the verifier’s soundness bound holds even against classical or quantum provers exchanging classical messages.Source: §5.3 · p. 24
  • For a height-j claim, the verifier uses at most 4^j leaf queries, while the honest prover uses 4^j − 3^j leaf queries.Both parties run in time 4^j poly(n, j).Source: §5.3 · p. 24

6 The constant-depth circuit lower bound

This section develops rank, sensitivity, certificate-complexity, and switching bounds, then uses depth reduction and coupling to analyze the considered constant-depth circuits. For sufficiently tall instances, the bounds yield exponentially small distinguishing advantage; the switching guarantee is pointwise for each fixed input.

6.1 A rank bound for the first satisfied term

  • A rank argument bounds the probability that the first satisfied term has many light blocks, without requiring a bound on the DNF’s number of terms.It counts secret tuples for each first satisfied term and bounds the number of such terms by the rank of functions of the secrets.Source: §6.1 · pp. 25, 27

6.2 Term deletion and sensitivity to the free leaves

  • Deleting terms with more than J light blocks preserves rejection, while projection reduces the retained DNF’s width to at most J + ⌊W/(t + 1)⌋.Applied level by level from the bottom up, this deletion scheme bounds the probability of losing acceptance at each level by 2^−(7/25)νr.Source: §6.2 · pp. 27, 28, 30
  • For sufficiently large n, a width-W DNF with W ≤ n^α accepts and is sensitive to every block’s free leaf with probability at most 2^-νr/4.Here the r independent blocks have height j = ⌊α⌋ + 1 and dimensions m_u through m_{u+j−1}, with ν = m_{u+j−1}; the bound is uniform over prescribed root values.Source: §6.2 · p. 28
  • Theorem 6.8 extends the sensitivity bound to independent blocks of any height at least j whose bottom level has dimension μ.Its proof exposes projections above level u+j−1, leaving independent height-j subtrees to which Theorem 6.5 applies.Source: §6.2 · pp. 30–31

6.3 A tail bound for certificate complexity

  • Claim 6.13 states that for every fixed family U as above, the probability of the associated event E_U under ρ is at most 2^(-γΛ).Source: §6.3 · p. 33

6.4 Switching under correlated projections

  • A CNF of width W with a 1-certificate of size at most q at z has a depth-at-most-Wq decision tree that accepts z and never accepts where the CNF rejects.The tree is determined by the CNF and q, enabling the switching construction.Source: §6.4 · p. 34
  • For each fixed input z, the projection switches a width-W CNF to a DNF with at most 2Wq terms of width at most Wq, with pointwise high-probability agreement; the dual statement also holds.The switched DNF is bounded above by the projected CNF everywhere, and the theorem’s size threshold is independent of instance height.Source: §6.4 · p. 35

6.5 Depth reduction and the coupling bound

  • After constantly many switching stages, the resulting depth-two polynomial-width formula distinguishes the coupled inputs with probability at most 2^-Ω(n).The inputs are generated by the same projections and differ in one coordinate; the depth reduction starts from a layered formula of depth and size bounded as stated in Claim 6.16.Source: §6.5 · p. 36
  • Iterative switching reduces the formula to depth two with polynomial width, while the accumulated error across stages remains exponentially small.Each stage replaces bottom two-layer subformulas using a shared fresh projection; the number of stages and exposed levels are constant for fixed D and A.Source: §6.5 · pp. 37–38
  • For the final depth-two formula, paired instances generated from the same projections disagree with probability at most 2^-c*n.The bound follows by applying the switching estimate to the final formula and summing the two root-value orientations.Source: §6.5 · p. 38
  • The coupling and distinguishing bounds are at most 2^-cn for a constant c independent of the instance height h.The result applies when h0 ≤ h ≤ hmax(n), for sufficiently large n; c, h0, and the threshold n0 do not depend on h.Source: §6.5 · p. 39

7 Proofs of the main theorems

The proofs construct an oracle separating exact quantum polynomial-time computation from the polynomial hierarchy while giving the language a classical interactive proof with an efficient quantum honest prover. They establish resource bounds, rule out constant-message proofs for the main language, and extend evaluation and verification to noisy code tables.

7.1 Constructing the oracle

  • The oracle is built in stages to make each enumerated polynomial-time machine with a constant number of alternating quantifiers err on a selected input.For each stage, the construction reduces acceptance to a bounded-depth, size-2^poly(n) circuit on target leaves and selects a valid table on which it errs.Source: §7 · p. 39, §7.1 · pp. 40–41
  • The oracle stores instance leaves only; all addresses of an instance have the same length, and internal secrets and node values have no addresses.The quantum algorithm and protocol evaluate the recursively defined instance using oracle access.Source: §7.1 · pp. 39, 41

7.2 The separation and the resource bounds

  • The language is outside PH^O, is decided exactly in EQPO^O, and has a public-coin proof with perfect completeness and soundness error at most 1/4.The protocol uses 2h(n) messages; for h=hmax, this is at most log n/4.Source: §7.2 · p. 41
  • For every unbounded polynomial-time computable f, the construction can bound the message count by f(n) and each party’s query count by 2f(n).A separate choice based on an unbounded query bound Q(n) makes the message count at most ⌊log2 Q(n)⌋ and each query count at most Q(n).Source: §7.2 · pp. 41–42
  • A direct procedure decides Lh with at most 2h(n) quantifier blocks, while the paper does not prove an Ω(h(n)) lower bound on required alternations.The procedure existentially guesses a secret and universally checks a code child or the data child indexed by that secret.Source: §7.2 · p. 42

7.3 Excluding constant-message interactive proofs

  • A constant-message classical proof for L would yield an AM^O proof and hence place L in PH^O, contradicting Theorem 1.1.The argument applies the Goldwasser–Sipser transformation and the two-message reduction; these steps relativize and do not require an efficient honest prover.Source: §7.3 · p. 42

7.4 Extension to noisy code tables

  • For code tables within relative distance η<1/4 of a codeword, evaluation and verification have bounded error, and constant-depth circuits of size 2^poly(n) cannot compute every valid instance.The theorem gives completeness at least 0.99 and soundness error at most 0.01; its circuit lower bound follows from exact valid instances and does not assert a correlation estimate for corrupted tables.Source: §7.4 · pp. 42–43
  • The separation uses data tables unconstrained beyond their entry at the secret; whether fixed-predicate recursive Fourier sampling lies outside PH relative to an oracle remains open.It is also open whether such an interactive-proof language can require more than logarithmically many alternations relative to an oracle.Source: §7.4 · p. 43

A Quantum evaluation and verification with noisy code tables

The appendix sets the noise parameter and explains how noisy code tables retain a uniquely identifiable secret. A gap in codeword agreement supports secret validation and the protocol’s soundness argument.

A Quantum evaluation and verification with noisy code tables

A.1 Decoding and evaluation with noisy code tables

The appendix decodes secrets from noisy code tables, uses those decoders to evaluate trees recursively, and constructs unitaries that approximate clean value oracles. The resulting evaluation and decoding procedures retain polynomial-time and constant-per-node query bounds for fixed noise parameters.

A.1 Decoding and evaluation with noisy code tables

  • A noisy code table’s secret can be recovered with error at most ζ using a constant number of code-table queries.The decoder generates candidate secrets by Fourier sampling, then validates them by checking agreement at random positions.Source: §A.1 · pp. 48–49
  • A node’s value can be computed with error at most ζ using a constant number of queries to its tables.The one-node procedure decodes the secret and then queries the data table at that secret.Source: §A.1 · pp. 48–49
  • A unitary W approximates a clean oracle on valid addresses with zero work registers, while using the address register only as a control.Its time, query, and space overhead is at most a constant factor depending on the chosen error δ.Source: §A.1 · pp. 49–50
  • For height j, recursive evaluation computes a noisy-valid tree’s value with error at most 1/10, at most Cη^j leaf queries, and time Cη^j poly(n,j).The recursion replaces child-value table queries with unitaries approximating clean value oracles, controlling accumulated error by a hybrid argument.Source: §A.1 · pp. 50–51

A.2 Verification with noisy code tables

The noisy-table protocol recursively checks a prover’s secret using a random code position and the data child at that secret. Repeated trials and a threshold yield bounded soundness and completeness with polynomial communication and an efficient quantum honest prover.

A.2 Verification with noisy code tables

  • For claims about trees valid with noise rate η<1/4, the protocol has completeness at least 0.99, soundness error at most 0.01, and an efficient uniform quantum honest prover.For height j, verifier queries and communication are bounded by (2tη)^j poly(n,j), and the honest prover’s time by (2tηCη)^j poly(n,j).Source: §A.2 · pp. 51, 53
  • Each internal-node trial asks the prover for a secret, samples a fresh uniform code position, then recursively checks the code-child and secret-indexed data-child claims.A trial succeeds only if both recursive checks accept; the verifier accepts after at least 3t/4 trials succeed.Source: §A.2 · p. 51
  • The protocol is public-coin because verifier messages contain only fresh random bits, and both parties derive child claims from the transcript.The recursive calls are run even after a malformed secret message, keeping their number and order independent of the prover’s messages.Source: §A.2 · pp. 51–52
  • For a false claim, each trial’s conditional success probability is at most 3/4−7κ/8, so the threshold bounds acceptance probability by ε.The argument conditions on the transcript and therefore also applies to quantum provers sending classical messages.Source: §A.2 · p. 52
  • For a true claim, the honest prover decodes the secret in each trial; the recursive checks and a tail bound keep rejection probability at most ε.The decoder’s error and the two recursive rejection probabilities contribute to the trial-success bound.Source: §A.2 · pp. 52–53

B A matching lower bound on the number of messages

Appendix B proves a message lower bound by first bounding how small-width DNFs distinguish root values, then transferring that bound to protocols and modifying the oracle construction.

B A matching lower bound on the number of messages

  • The argument applies to instances of size n and height at most hmax(n), with thresholds tied to the levels of the instance.The appendix defines P(n,0)=1 using the threshold for light blocks.Source: B A matching lower bound on the number… · p. 53
  • The proof proceeds from a DNF indistinguishability bound to a query lower bound for two-message protocols, then reduces general public-coin protocols to two messages.The appendix combines these steps to prove the message lower bound and adds verifier stages to the oracle construction.Source: B A matching lower bound on the number… · p. 53

B.1 DNFs of small width cannot distinguish the root values

The appendix shows that DNFs below a height-dependent width threshold have nearly identical expected outputs on instances with opposite root values, uniformly over the allowed heights.

B.1 DNFs of small width cannot distinguish the root values

  • The threshold satisfies P(n,h) ≤ (n+1)^h.The proof also uses bounds on the level dimensions to control the probability accumulated across levels.Source: §B.1 · p. 53
  • The level-by-level argument is uniform for every height h ≤ hmax(n), rather than applying only to a fixed number of bottom levels.The proof conditions on projections below and above a level, then bounds the probability of a light block at that level.Source: §B.1 · pp. 53–54
  • At each level, the proof deletes terms containing a light block and projects the remaining terms, reducing width by a factor of at least ti+1.After all levels, width below P(n,h) yields a width-zero DNF that is constant and independent of the root value.Source: §B.1 · p. 54
  • For DNF width below P(n,h), the expected outputs on coupled instances with opposite root values differ by at most 2^-3√n.The same bound holds with the root values exchanged; at height zero, the difference is zero.Source: §B.1 · pp. 53–54

B.2 From protocols to DNFs

The appendix converts protocol correctness into DNF width and query lower bounds, reduces public-coin rounds to two messages, and derives a communication-slot lower bound.

B.2 From protocols to DNFs

  • A correct two-message protocol making at most q queries to the leaf table must have q ≥ P(n,h).Fixing the verifier's randomness yields a DNF of width at most q whose expected acceptance separates the two root values.Source: §B.2 · p. 55
  • An r-round public-coin protocol can be replaced by a two-message protocol using at most q∆^r queries, with values at least 5/6 or at most 1/6 in the corresponding completeness and soundness cases.The construction samples challenges on a complete ∆-ary tree and accepts when at least half of its paths accept.Source: §B.2 · pp. 55–56
  • The round-reduction construction preserves protocol value on each fixed leaf table while replacing the original interaction with a single challenge and reply.It uses a labelled tree of transcripts and compares the fraction of accepting paths with the original protocol's value.Source: §B.2 · pp. 55–56
  • Every correct public-coin verifier with the stated time bound requires at least h/(14a) communication slots when h ≥ 42a.The lower bound follows by converting a protocol with fewer slots into a two-message protocol whose query cost contradicts the DNF-derived bound.Source: §B.2 · p. 57
  • Private-coin protocols can be transformed into public-coin protocols with at most c0(M(n)+1) slots while preserving the stated completeness and soundness thresholds.The transformation applies after fixing the schedule and padding early-halting protocols with dummy messages.Source: §B.2 · p. 57

B.3 The oracle

The oracle construction diagonalizes against clocked verifiers by capping their messages and using the finite-height lower bound to select instances on which they fail.

B.3 The oracle

  • The construction enumerates clocked verifier, exponent, and repetition-index triples so each verifier-exponent pair recurs infinitely often.At each stage it uses the finite-form lower bound to find a target instance on which the capped verifier is incorrect.Source: §B.3 · pp. 57–58
  • A capped verifier is padded to a fixed slot count and transformed into a public-coin verifier with polynomial overhead independent of the cap parameter.The cap is ⌊h(n)/K⌋ slots, with early decisions preserved by dummy messages.Source: §B.3 · p. 58
  • The completed oracle retains the quantum algorithm, proof system, and resource bounds while placing the language outside PH relative to that oracle.The message lower bound is optimal up to verifier-dependent constant factors on infinitely many lengths.Source: §B.3 · pp. 58–59
  • For every polynomial-time verifier V, the construction forces more than βVh(n) communication slots on infinitely many input lengths.The constant depends on the verifier, and the lower bound holds at lengths where h(n) is sufficiently large.Source: §B.3 · pp. 58–59

C Codes from bent functions

The section builds code families from shifts of bent functions, whose duals enable exact recovery of the hidden shift. It gives an explicit cubic family and connects the Hadamard-code addressing function to 3-fold Forrelation.

C Codes from bent functions

  • A bent function has Fourier coefficients of equal magnitude 2^-m/2, and its dual records their signs.The code C_m(s, x) uses the shifts g(x + s) as codewords.Source: C Codes from bent functions · p. 59
  • When the dual of a bent function is efficiently computable, the unitary H^⊗m D_ĝ H^⊗m recovers the shift s exactly.This is Rötteler’s hidden-shift algorithm with the dual computed rather than queried [Rot10].Source: C Codes from bent functions · p. 59
  • For every positive multiple m of eight, efficiently computable bent functions and duals of degree at most d yield a code family of degree d.Each codeword is C_m(s, x) = g_m(x + s); translation preserves the degree bound.Source: C Codes from bent functions · p. 59
  • An explicit degree-three code family exists for every m = 8r, using a Maiorana–McFarland construction with a permutation acting on groups of four bits.The construction’s bent function and dual have degree three and polynomial-size circuits implementing their phase oracles exactly.Source: C Codes from bent functions · pp. 59–60
  • For the Hadamard code with η = 0, (−1)^R_s equals the 3-fold Forrelation of (−1)^L, (−1)^R, and (−1)^L.Here L is the codeword of s, and the Hadamard transform maps its phase state to |s⟩.Source: C Codes from bent functions · p. 60

Related papers

Loading 2610.37635v1…