PaperlayerView exact revision on arXiv

Source-linked AI summary

Verifiable quantum advantage based on polynomials with planted structures

Markus Bläser, Michael Gullans, Dominik Hangleiter, Yuxuan Liu, Youming Qiao

arXiv:2609.39918v1quant-phcs.CCcs.CRcs.DS

TL;DR

Quantum advantage experiments have lacked verification from their classical outputs alone. This paper plants secret structure in IQP circuits so a verifier can evaluate an XEB test faster than an adversary can pass it; under conjectures, the scheme gives a polynomial gap between their exponential runtimes.

  • Problem

    Quantum advantage experiments have lacked classical verification from their outputs, requiring separate data and immense classical computation for validation.

    Source: §1.1 · p. 2

  • Method

    The verifier plants a secret independent space in a random IQP circuit, using that structure to evaluate XEB probabilities faster than an adversary without the secret.

    Source: §1.2 · p. 5

  • Results

    Under fine-grained complexity conjectures, passing XEB without the secret requires Ω(2^κn) time, while verification takes Õ(2^(n(1/2+ε))) time for arbitrarily small ε>0.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The output distribution's high entropy gives the protocol a potential application to classically certified randomness.

    Source: §1.6 · p. 10

    Exponential-runtime quantum adversaries can pass XEB with lower-min-entropy samples, collapsing the security gap; security is conjectured against polynomial-time quantum adversaries.

    Source: §1.6 · p. 11

Abstract

from arXiv · show

A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advantage. A verifier can use a simulation secret to evaluate a cross-entropy test faster than it would take a classical adversary to pass the test. We instantiate this idea using IQP circuits described by cubic polynomials with planted independent spaces. These correspond to the largest independent set in the orbit of a polynomial under the general linear group and yield a low-rank stabilizer decomposition of the corresponding state. We conjecture that large independent spaces are invisible to a computationally bounded adversary, and therefore they cannot exploit them to pass the protocol. A second conjecture regards the fine-grained complexity of producing samples that pass the cross-entropy test for uniformly random polynomials. Under these conjectures, our scheme results in a polynomial gap between the verification time and the time a classical adversary would need to pass the protocol---both are exponential. It has a potential application to generating classically certifiable randomness, since the output distributions have high min-entropy. We estimate that the planted polynomial scheme is implementable using 100 logical qubits at logical error rates around $10^{-6}$.

1 Introduction

The section introduces simulation-secret verification for random-like IQP computations, using planted independent spaces as structure for secret-aided simulation, and develops algorithms and limits for those spaces. It motivates a cubic XEB hardness conjecture and surveys applications, open directions, and the paper’s remaining technical sections.

1.1 Motivation

  • The proposal plants secret structure in random IQP circuits so the verifier can compute XEB probabilities faster while outputs retain high entropy, supporting a possible route to classically certified randomness.The authors estimate computations with up to 100,000 transversal gates on around 100 logical qubits or fewer may be verifiable, and conjecture the structure remains hidden from quantum adversaries.Source: §1.1 · pp. 3–4

1.2 Quantum circuits from polynomials with planted independent spaces

  • A cubic polynomial with a planted independent space of dimension h yields an IQP circuit simulable in time 2^(n-h), and the space may occur in the polynomial’s GL(n, F2) orbit.The construction generalizes planted independent sets; planting dimension ≲ n/2 gives a polynomial gap between verification and simulation.Source: §1.2 · pp. 4–6
  • For random cubic polynomials, the typical independent-space dimension is at most n/6; planted-space detection has a 2^Θ(n^1.5) enumeration regime below (1/2 − ε)n and faster algorithms above (1/2 + ε)n.The faster regime uses Hessian-slice rank profiles and runs in ~O(2^(n-h)).Source: §1.2 · pp. 5–6

1.3 Verifiable advantage from planted independent spaces

  • Under Conjectures 2 and 3, planted-space IQP circuits have verification time ~O(2^cn), honest quantum acceptance with high probability, and no polynomial-space classical passer in o(2^κn) time.This yields a polynomial verification–simulation gap; for n ≲ 100 and c > 1/2, verification is estimated to require simulating at most a 50-qubit IQP circuit.Source: §1.3 · p. 7

1.4 The planted independent space problem for cubic polynomials

  • Worst-case decision-IndSp is NP-complete, while the average-case search-to-decision reduction remains open.The NP-completeness result follows from equivalences with support vertex cover, strength, and symmetric slice rank; the reduction to slice rank uses.Source: §1.4 · p. 8
  • For h ≥ (1/2 + ϵ)n, search-h-PlantedIndSp is solvable in ˜O(2^(n−h)) time using rank profiles of Hessian slices at random vectors.A rank deficiency typically distinguishes planted from uniform polynomials at points in the independent space; one such point suffices to distinguish, and a constant number can determine the space.Source: §1.4 · p. 8

1.5 The cubic XEB problem

  • No known sub-2^n-time classical algorithm achieves an XEB score close to ideal, motivating the conjecture that passing cubic XEB is exponentially difficult.Known XEB spoofers exploit circuit noise; the passage identifies no known sub-2^n-time classical algorithm meeting the conjectured ideal-score requirement.Source: §1.5 · p. 10

1.6 Discussion and outlook

  • The high-entropy output distribution could enable classically certified randomness, but the proposed security remains conjectural against polynomial-time quantum and polynomial-space classical adversaries.The discussion says quantum amplitude amplification can pass XEB in O(2^(n/2)) time using a lower-min-entropy distribution, and leaves full security analysis to future work.Source: §1.6 · pp. 10–11
  • Recovery and distinguishing of independent spaces above h = n/2 limit the scheme to at most a polynomial verification-simulation gap, rather than an exponential gap.Both tasks take ˜O(2^(n−h)) time in this regime.Source: §1.6 · p. 11
  • The paper proposes exploring other hidden circuit structures and polynomial orbits, and extending planted independent spaces beyond Boolean polynomials to finite fields.Possible structures include low entanglement; possible orbits include Clifford circuits and efficiently computable invertible Boolean functions.Source: §1.6 · pp. 11–12
  • Efficient recovery of block-diagonal structure rules out the proposed forrelation approach to verifiable advantage that depends on hiding product/block structure.The cited proposal relies on efficient classical computation of the forrelator when the product structure is known, but hardness of detecting that structure.Source: §1.6 · pp. 11–12

1.7 Overview

  • The paper proceeds from polynomial and tensor preliminaries and the planted-space conjecture to the verifiable-advantage application, then analyzes worst- and average-case hardness.These topics are assigned to Sections 2, 3, and 4–5, respectively.Source: §1.7 · p. 12

AI Statement

The authors report using generative AI to assist with proof-related work and draft feedback.

AI Statement

  • Generative AI assisted with proving lemmas, checking technical correctness, and giving feedback on earlier drafts.The authors state that the paper's original concepts and proof strategies are their own.Source: AI Statement · p. 12

2 The polynomial planted independent space problem

This section characterizes independent spaces of cubic Boolean polynomials via associated alternating trilinear forms and describes how to plant and hide such spaces using random linear changes of variables. It defines related decision, distinguishing, and search problems, identifies search as central, and states an exponential-hardness conjecture for distinguishing in a specified dimension range.

2.1 Boolean polynomials and tensors

  • The associated alternating trilinear form captures a polynomial’s cubic coefficients and is unaffected by its quadratic and linear terms.Under a linear change of variables g = f ◦ A, the form transforms as Tg(u, v, w) = Tf(Au, Av, Aw).Source: §2.1 · pp. 15–16

2.2 Planted independent space

  • A subspace V is independent for a cubic polynomial g exactly when Tg vanishes on V^3, equivalently when deg(g|V) ≤ 2.For random cubic polynomials, the section also proves a high-probability upper bound on the maximum independent-space dimension α(f).Source: §2.2 · pp. 16–17

2.3 Statement of independent space problems

  • The planting procedure zeros cubic coefficients within a fixed h-dimensional coordinate subspace, then applies a uniformly random invertible linear transformation to hide that subspace.The quadratic and linear part is independently sampled and left unchanged during the planting step.Source: §2.3 · p. 17
  • Under P3(n,h), V is a uniformly random h-dimensional subspace on which the restriction of g has degree at most two.The final lower-degree part of g is uniformly random and independent of the cubic part and V.Source: §2.3 · p. 17
  • The section defines decision problems for detecting an independent space of dimension at least h or distinguishing planted from uniformly random polynomials, and search problems for finding V.The planted search problem takes g sampled from P3(n,h); whether search-to-decision reductions exist remains open.Source: §2.3 · pp. 17–18
  • The central task is to recover the planted h-dimensional independent space V from a cubic polynomial g sampled with that space planted.The public instance gives n, h, and g; V and the linear substitution A remain secret.Source: §2.3 · pp. 17–18
  • Conjecture 28 posits exponential hardness for distinguishing planted from uniform instances when h ≤ (1/2 − ϵ)n, against classical algorithms running in o(2^n) time.The passage states that probabilities include the algorithm’s internal randomness, but does not provide the conjecture’s full distinguishing criterion.Source: §2.3 · p. 18

3 Verification of IQP circuit sampling from planted independent spaces

The section develops XEB-based verification for IQP sampling with planted independent spaces, including a conditional gap between verification and classical simulation times. It also considers planted sampling for certified randomness under additional entropy and hardness assumptions.

3.1 IQP circuits and their statistical properties

  • Random cubic IQP sampling is classically intractable within constant total-variation distance under polynomial-hierarchy noncollapse and constant-fraction GapP-hardness of outcome probabilities; amplitudes are GapP-hard to approximate.Source: §3.1 · p. 19
  • For the polynomial family M(n), the first three moments match those of P2(n), including m2 = 3 + o(1) and m3 = 15 + o(1).Source: §3.1 · pp. 20–21

3.2 Verification via XEB

  • Average XEB distinguishes uniform from ideal samples, whose score is χ = 2 + o(1), and an ideal sampler passes the ℓ = 1 test with χ̂ ≥ 1 with probability at least 1 − 10/L.Source: §3.2 · pp. 22–23
  • Conjecturally, no polynomial-time classical algorithm can achieve high average XEB for polynomially many uniformly random cubic polynomials with high probability.The conjecture rules out success probability at least 1 − 1/poly(L) for XEB1,ℓ when L, ℓ = poly(n).Source: §3.2 · p. 23

3.3 Simulating IQP circuits with and without planted independent spaces

  • For random cubic polynomials, gap computation takes ˜O(2^0.9965n) time, while conjecturally high-XEB sampling in polynomial space requires Ω(2^κn · poly(n)) time for some κ > 1/2.Source: §3.3 · pp. 23–24
  • A vertex cover of the polynomial’s hypergraph yields a low-rank stabilizer decomposition of its amplitudes, with each cover-variable assignment defining a quadratic polynomial on the remaining variables.Source: §3.3 · pp. 24–25
  • A cubic polynomial with an h-dimensional independent space allows exact amplitude computation in O(2^{n−h}n^3) time when the polynomial and a basis are given.The algorithm uses the independent space to obtain a vertex-cover decomposition and reduces the remaining computation to evaluating quadratic-polynomial gaps.Source: §3.3 · p. 25
  • Under ExpPlantedIndSp and ExpXEB, the verifier’s planted-polynomial XEB test admits an honest polynomial-time quantum prover, while no classical polynomial-space algorithm running in o(2^κn) passes with failure probability 1/poly(n).The theorem uses h = (1 − c)n with 1/2 < c ≤ κ ≤ 1 and ℓ, L = poly(n).Source: §3.3 · p. 26

3.4 Towards certified randomness from planted IQP circuits

  • Planted IQP circuits may enable more efficient post-hoc certification of randomness because the assumed verification–simulation time gap makes classical spoofing infeasible with available resources.The output distributions have high min-entropy with high probability; the authors say this may relax or remove the fast-response timing requirement, while noting stronger security guarantees are needed against quantum adversaries.Source: §3.4 · pp. 26–27

3.4.1 The certified randomness protocol

  • Planted and uniformly random cubic IQP outputs have, respectively, 2n/3 − O(log 1/δ) and n − O(√n) bits of min-entropy with high and overwhelming probability.The certified-randomness argument adapts Aaronson and Hung’s framework, which relates successful XEB performance to producing samples with a linear amount of average entropy under its hardness assumption.Source: §3.4.1 · p. 27

3.4.2 Application to cubic IQP circuits

  • Under LLHAB(P3(n, h)) with B = Θ(n), a polynomial-time quantum prover passing planted single-circuit XEB with probability at least 1 − ε is subject to the stated entropy bound.The bound’s formula is not included in the supplied passage; the authors say ruling out classical polynomial-space provers with verifier-comparable time requires a separate hardness assumption and leave a complete security analysis for future work.Source: §3.4.2 · p. 28

4 Worst-case hardness of the independent space problem

The section proves worst-case NP-hardness for finding large independent spaces in cubic forms by relating them to slice-rank problems. For trilinear forms with antichain support, slice rank and symmetric slice rank coincide.

4 Worst-case hardness of the independent space problem

  • Deciding whether a cubic form has an independent space of a given size is NP-hard, as is computing its symmetric slice rank and strength.The proof relates large independent spaces to low symmetric slice rank and reduces from the NP-hard trilinear slice-rank problem.Source: §4 · p. 28, §4.2 · p. 33

4.1 Slice rank (trilinear case)

  • For a trilinear form P, SR(P) ≤ r exactly when it has an independent triple of spaces of total dimension at least ℓ + m + n − r.When supp(P) is an antichain, its slice rank also equals the vertex-cover number of that support.Source: §4.1 · pp. 29–30

4.2 Symmetric slice rank (polynomial case)

  • For cubic forms, symmetric slice rank at most r exactly corresponds to a formally independent space of dimension at least n − r.For cubic forms, symmetric slice rank equals strength.Source: §4.2 · p. 31
  • For trilinear forms with antichain support, slice rank equals the symmetric slice rank of the corresponding cubic form.The section establishes a lower bound by the support hypergraph’s vertex-cover number, yielding the equality; strength equals these ranks as well.Source: §4.2 · pp. 31–32

5 Cryptanalysis of the planted independent space problem

The section gives algorithms that recover planted independent spaces when their dimension exceeds half the ambient dimension by a constant fraction. It also examines a Bell-sampling attack motivated by low stabilizer rank and finds that stabilizer nullity is too loose to make it effective.

5.1 The h/n > 1/2 regime

  • With h ≥ (1/2 + ϵ)n, Algorithm 1 recovers the planted independent space in O(hn^3 2^(n−h)) time with probability 1 − e^−Ω(n).It uses polynomial space and applies to sufficiently large n for fixed 0 < ϵ < 1/2.Source: §5.1.1 · p. 34
  • A second recovery algorithm takes 2^(n−h) · poly(n) time and uses O(C · 2^(n−h)) samples, versus O(h · 2^(n−h)) for Algorithm 1.It collects low-rank tensor slices and uses canonical shrunk-subspace computation to recover the planted space.Source: §5.1.1 · p. 33, §5.1.2 · pp. 35, 37

5.2 Analysis of Bell-sampling attacks

  • Bell sampling raises a possible attack because planted circuits have lower stabilizer rank, but stabilizer nullity is maximally loose for vertex-cover decompositions of random circuits.For h ≤ (1 − ϵ)n, the analysis gives a 2^−Ωϵ(n^2) bound.Source: §5.2 · pp. 37–38

A Attack on block-diagonal structure

The section describes how to recover block-diagonal structure in a tensor by computing its centroid algebra and finding a non-trivial idempotent.

A Attack on block-diagonal structure

  • A tensor that is isomorphic to a block-diagonal tensor can be transformed to reveal its component blocks.The proposed task is to compute the transformation that exposes this structure.Source: A Attack on block-diagonal structure · p. 44
  • For a non-degenerate trilinear form, the centroid algebra can be computed efficiently, and it contains a non-trivial idempotent exactly when the form is isomorphic to a block-diagonal tensor.The centroid algebra consists of endomorphism triples acting consistently across the three arguments.Source: A Attack on block-diagonal structure · p. 44
  • The search for a non-trivial idempotent is reduced to solving the problem in the algebra’s simple components, then gluing solutions and lifting through the radical.The procedure first computes the Jacobson radical and semisimple quotient decomposition.Source: A Attack on block-diagonal structure · p. 44

Related papers

Loading 2609.39918v1…