Quantum time classes NQTIME, EQTIME and PostBQTIME in DTIME[2^O(T/√log T)] by exact gap contraction #2094

Status: active. worker-claude-e6cf7b0d-qclasses (Claude Code, Opus; subagent of coordinator-claude-e6cf7b0d), branch claude/quantum-exact-classes, stacked by merge on #2072. Samuel asked for this.

Goal

Put three more quantum time classes into ⋃ C, DTIME[2 ^ (C T / √⌊log₂ T⌋)] for max n 2 ≤ T n, as #2072 does for BQTIME[T]:

• NQTIME[T]: accept iff the acceptance probability is > 0.
• EQTIME[T]: the acceptance probability is exactly 1 on members and 0 otherwise.
• PostBQTIME[T]: qubit 1 reads 1 with nonzero probability, and, conditioned on that, qubit 0 reads 1 with probability ≥ 2/3 on members and ≤ 1/3 otherwise.

The textbook route through NQP = coC₌P or PostBQP = PP loses a polynomial in T and erases the saving. Instead, the tensor contraction of #2058 and #2072 computes the needed acceptance gaps exactly.

Definitions (in Classes/BQP/Time.lean, beside BQTIME)

All three reuse BQTIME's model: a UniformCircuitFamily (polynomial-time uniform, Hadamard, NOT, CNOT and Toffoli gates, input |x 0^{m-n}⟩) with at most c₁ t n + c₂ gates, and a measurement at the end.

• NQTIME enc t: ∀ a, a ∈ A ↔ 0 < F.acceptProb (enc a).
• EQTIME enc t: (a ∈ A → F.acceptProb (enc a) = 1) ∧ (a ∉ A → F.acceptProb (enc a) = 0).
• PostBQTIME enc t: 0 < F.onesProb [1] (enc a), and the conditional probability F.onesProb [0, 1] x / F.onesProb [1] x is ≥ 2/3 on members and ≤ 1/3 otherwise. Here onesProb S is the probability that every qubit of S reads 1. This is Aaronson's Definition 1 with the two qubits relabeled: his postselected qubit is the first and his output qubit the second, while this library's output qubit is 0.

The gate set matters. EQTIME is exact quantum time over this fixed gate set. Exactness is not robust under changes of gate set: Solovay–Kitaev approximation preserves bounded error, not zero error. So this class is not claimed to equal EQTime(T) over Bernstein–Vazirani's quantum Turing machines or over other gate sets. NQTIME and PostBQTIME are defined over the same gate set. For polynomial time, FGHP show that NQP is the same for algebraic amplitudes and for {0, ±1/√2, ±1} (Section 4). Aaronson's footnote 8 says the same for PostBQP by Solovay–Kitaev. The time-T classes are taken as defined here.

Statements

• NQTIME_subset_iUnion_DTIME_two_pow_div_sqrt_log_two, EQTIME_… and PostBQTIME_…, with joint forms DecidableInTimeAndSpace … (2 ^ (C T / √⌊log₂ T⌋)) (T ^ d).
• EQTIME ⊆ NQTIME and EQTIME ⊆ BQTIME, both immediate.

Proof sketch

• Projected gaps. Generalize the final projector from qubit 0 to a list S of qubits that must read 1. In the path sum, the projected gap onesGap S is the sum over pairs of paths ending in the same register with all of S equal to one, and onesProb S = onesGap S / 2^h. In the network, the glue tensor of qubit j is the "both one" tensor exactly when j ∈ S, and the scalar vertex checks the input bits of untouched qubits of S. acceptGap is the case S = [0].
• One simulator. The simulator decides a polynomial-time rule on two projected gaps, (onesGap S, onesGap P), by two contractions. Here onesGap [] = 2^h.
  • BQTIME: ([0], []) with 2^h < 2g.
  • NQTIME: 0 < g.
  • EQTIME: 0 < g on the promise.
  • PostBQTIME: ([0,1], [1]) with g_P < 2 g_S. The promise gives 2 g_S − g_P ≥ g_P / 3 > 0 on members and ≤ −g_P/3 < 0 otherwise.

Sources (locators checked against the sources)

• S. Fenner, F. Green, S. Homer, R. Pruim, arXiv:quant-ph/9812056v1: Theorem 1.1 NQP = coC₌P (PDF p. 2), Definition 2.1 of NQP (PDF p. 7), and Section 4 on amplitude sets (PDF p. 11).
• S. Aaronson, arXiv:quant-ph/0412187v1, §3: Definition 1 of PostBQP (p. 3), Proposition 2 PostBQP ⊆ PP (p. 3), and Theorem 4 PostBQP = PP (p. 4).
• E. Bernstein, U. Vazirani, SIAM J. Comput. 26(5), 1997, §8.1: Definition 8.1 (p. 1450), which defines EQP and EQTime(T(n)).

Novelty

I found no direct 2^{O(T/√log T)} deterministic simulation of NQTIME, EQTIME or PostBQTIME, but my search was limited to web searches and the three sources above, so this is not a novelty claim.

• The contraction algorithm ([OpenAI2026ETH], Theorem D.1) dates from October 2026. Its paper does not mention quantum circuits.
• Treewidth-based simulation, as in Markov–Shi (arXiv:quant-ph/0511069), costs exp(O(tw)), and the treewidth of a T-gate circuit can be Θ(T).
• The known characterizations go through coC₌P and PP, which cost polynomial overhead.

The PR will label the containments as an application of #2072 and make no novelty claim.

Completion

Done when the definitions, the three containments and tests with real instances land:

• a circuit accepting with probability strictly between 0 and 1, which is in NQTIME's sense nonzero but not exact;
• an exact circuit;
• a postselection example.