pith. sign in

arxiv: 2308.09549 · v8 · pith:SVLMHOA4new · submitted 2023-08-18 · 💻 cs.CC · math.PR

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization

Tianrong Lin This is my paper

Pith reviewed 2026-05-24 07:26 UTC · model grok-4.3

classification 💻 cs.CC math.PR
keywords BPPPcomplexity class separationprobabilistic Turing machinederandomizationpseudorandom generatorChurch-Turing thesis
0
0 comments X

The pith

There exists a language L_d in BPP but not in P, proving probabilistic polynomial time strictly more powerful than deterministic polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends prior techniques to exhibit a language L_d accepted in polynomial time by a probabilistic Turing machine. It shows this language cannot be decided by any deterministic polynomial-time machine, establishing P proper subset BPP. Since BPP is contained in BQP, the separation also proves P proper subset BQP. The results further imply that randomness plays an essential role and that no efficient pseudorandom generator exists.

Core claim

There exists a probabilistic Turing machine running within time O(n^k) for all k in N_1 accepting a language L_d that is different from any language in P, and L_d in BPP, thus P proper subset BPP. Since BPP subset BQP this gives P proper subset BQP. As a consequence the Extended Church-Turing Thesis is disproved. The paper also shows P proper subset RP, P proper subset co-RP, P proper subset ZPP, that random bits for L_d cannot be reduced to O(log n), and that no efficient PRG or quick HSG exists.

What carries the argument

The language L_d constructed by extending techniques from prior work to be accepted by a probabilistic polynomial-time Turing machine while remaining outside all languages in P.

If this is right

  • P is properly contained in RP
  • P is properly contained in co-RP
  • P is properly contained in ZPP
  • The number of random bits for any probabilistic algorithm accepting L_d cannot be reduced to O(log n)
  • No efficient pseudorandom generator G from O(log n) bits to n bits exists

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation implies that derandomization techniques cannot succeed for every language in BPP without using superpolynomial resources.
  • Similar constructions might be adaptable to separate P from other probabilistic classes such as PP.
  • Verification could involve attempting to simulate the probabilistic machine on small inputs and comparing outputs to all possible deterministic polynomial-time procedures.

Load-bearing premise

The construction of L_d ensures it is not decidable by any deterministic polynomial-time Turing machine.

What would settle it

A deterministic polynomial-time Turing machine that accepts L_d would show the claimed separation does not hold.

Figures

Figures reproduced from arXiv: 2308.09549 by Tianrong Lin.

Figure 1
Figure 1. Figure 1: Cantor pairing function state qrej with probability 1 − (λ + ϵ) and then halts. Otherwise, M0 transfers its next state from the state qpa to the state qacc with probability 1 − (λ + ϵ) and to the state qrej with probability λ + ϵ and then halts, which is illustrated by [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The probabilistic transitions of M0 and the corresponding probabilities cells each, the blocks being separated by a single cell holding a marker #, i.e., there are (1 + ⌈log t⌉)n cells in all. Each tape symbol occurring in a cell of Mcj ’s tape will be encoded as a binary number in the corresponding block of the second tape of M0. Initially, M0 places Mcj ’s input, in binary coded form, in the blocks of ta… view at source ↗
Figure 3
Figure 3. Figure 3: The transitions of states of M0 and corresponding probabilities by setting λ = 2 3 Suppose now Ld were accepted by some, say, the i-th deterministic Turing machine in the enumeration e, which is a deterministic T(n) = n k + k time-bounded Turing machine Mci . Then by Lemma 2.1 we may assume that Mci is a single-tape deterministic Turing machine. Let Mci have s states and t tape symbols. Since Mci 3 appears… view at source ↗
Figure 4
Figure 4. Figure 4: The transitions of states and corresponding probabilities for [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The transitions of states of M0 and corresponding probabilities for Lcd ∈ co-RP Remark 7.1. As a matter of fact, Lcd is also in RP since for x ∈ Lcd, Pr[M0 accepts x] = 1 ≥ 1 2 , as ϵ tends to 0. For x ̸∈ Lcd, Pr[M0 accepts x] = 0, 25 [PITH_FULL_IMAGE:figures/full_fig_p025_5.png] view at source ↗
read the original abstract

In this paper, we extend the techniques used in our previous work to show that there exists a probabilistic Turing machine running within time $O(n^k)$ for all $k\in\mathbb{N}_1$ accepting a language $L_d$ that is different from any language in $\mathcal{P}$, and then further to prove that $L_d\in\mathcal{BPP}$, thus separating the complexity class $\mathcal{BPP}$ from the class $\mathcal{P}$ (i.e., $\mathcal{P}\subsetneqq\mathcal{BPP}$). Since the complexity class $\mathcal{BQP}$ of {\em bounded error quantum polynomial-time} contains the complexity class $\mathcal{BPP}$ (i.e., $\mathcal{BPP}\subseteq\mathcal{BQP}$), we thus confirm the widespread-belief conjecture that quantum computers are {\em rigorously more powerful} than traditional computers (i.e., $\mathcal{P}\subsetneqq\mathcal{BQP}$). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we also show that (1): $\mathcal{P}\subsetneqq\mathcal{RP}$; (2): $\mathcal{P}\subsetneqq{\rm co-}\mathcal{RP}$; (3): $\mathcal{P}\subsetneqq\mathcal{ZPP}$. Previously, whether the above relations hold or not were long-standing open questions in complexity theory. Meanwhile, the result of $\mathcal{P}\subsetneqq\mathcal{BPP}$ shows that {\em randomness} plays an essential role in probabilistic algorithm design. In particular, we go further to show that (4): The number of random bits used by any probabilistic algorithm that accepts the language $L_d$ can not be reduced to $O(\log n)$; (5): There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG). $$ G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n; $$ (6): There exists no quick HSG $H:k(n)\rightarrow n$ such that $k(n)=O(\log n)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The manuscript claims to show the existence of a probabilistic Turing machine that runs in time O(n^k) for all natural numbers k and accepts a language L_d not in P but in BPP, thereby proving P proper subset BPP (and thus P proper subset BQP), disproving the Extended Church-Turing Thesis. It also claims P proper subset RP, coRP, ZPP, and the non-existence of efficient pseudorandom generators and hitting set generators.

Significance. Were the claims substantiated with a valid construction and consistent formal definitions, they would resolve multiple fundamental open questions in complexity theory regarding the power of randomness and quantum computation. The manuscript, however, does not include the explicit construction of L_d or the detailed proofs, instead extending techniques from the author's previous papers.

major comments (3)
  1. [Abstract] Abstract: The assertion that there exists a single probabilistic Turing machine 'running within time O(n^k) for all k∈N_1' is ill-posed. Any fixed TM has a specific polynomial degree c such that its running time is O(n^c); the bound cannot hold for all k simultaneously in a way that satisfies the definition of BPP, which requires only some fixed polynomial bound. This inconsistency undermines the claim that L_d ∈ BPP.
  2. [Abstract] Abstract: The manuscript asserts the existence of L_d ∉ P without providing the construction of L_d, the proof that it lies outside P, or verification steps within this text. The central separation P ⊂ BPP therefore lacks supporting derivation in the provided manuscript and reduces to unexamined content from prior work.
  3. [Abstract] Abstract: The subsequent claims that this establishes P ⊂neq BQP, disproves the Extended Church-Turing Thesis, and yields separations for RP, coRP, and ZPP all depend on the above two issues and are therefore not supported.
minor comments (1)
  1. [Abstract] Abstract: The notation N_1 is nonstandard; typically N or N_0 is used for natural numbers starting from 1 or 0.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their thorough review and insightful comments. We address each of the major comments point by point below, providing our responses and indicating planned revisions to the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The assertion that there exists a single probabilistic Turing machine 'running within time O(n^k) for all k∈N_1' is ill-posed. Any fixed TM has a specific polynomial degree c such that its running time is O(n^c); the bound cannot hold for all k simultaneously in a way that satisfies the definition of BPP, which requires only some fixed polynomial bound. This inconsistency undermines the claim that L_d ∈ BPP.

    Authors: We agree that the phrasing is ill-posed and does not accurately reflect the definition of BPP. Our intent was to state that L_d is in BPP, meaning it is accepted by a probabilistic Turing machine running in time O(n^c) for some fixed c. We will revise the abstract to correct this misstatement. This does not affect the validity of the separation claim itself. revision: yes

  2. Referee: [Abstract] Abstract: The manuscript asserts the existence of L_d ∉ P without providing the construction of L_d, the proof that it lies outside P, or verification steps within this text. The central separation P ⊂ BPP therefore lacks supporting derivation in the provided manuscript and reduces to unexamined content from prior work.

    Authors: The explicit construction of L_d and the proof that L_d ∉ P are provided in our previous papers, upon which this work builds by extending the techniques to establish membership in BPP. This manuscript focuses on the extension and the resulting separation. To make the current paper more accessible, we will add a concise summary of the relevant construction and properties from prior work in the revised version. revision: partial

  3. Referee: [Abstract] Abstract: The subsequent claims that this establishes P ⊂neq BQP, disproves the Extended Church-Turing Thesis, and yields separations for RP, coRP, and ZPP all depend on the above two issues and are therefore not supported.

    Authors: Once the abstract is clarified regarding the time bound and a summary of the prior construction is included, the dependent claims are supported by the established P ⊂neq BPP together with the standard inclusions BPP ⊆ BQP, RP ⊆ BPP, etc. We will update the abstract and introduction to explicitly reference these connections. revision: yes

Circularity Check

1 steps flagged

Separation P ⊂ BPP reduces to self-cited prior work for the claim that Ld ∉ P

specific steps
  1. self citation load bearing [Abstract]
    "In this paper, we extend the techniques used in our previous work to show that there exists a probabilistic Turing machine running within time O(n^k) for all k∈N1 accepting a language Ld that is different from any language in P, and then further to prove that Ld∈BPP, thus separating the complexity class BPP from the class P (i.e., P⊊BPP)."

    The assertion that Ld is different from any language in P (the load-bearing premise for the separation) is not derived here but obtained by extending the author's own prior papers; the claimed P proper subset BPP therefore reduces directly to the content of those self-citations rather than to any new, independently verifiable step in this text.

full rationale

The paper's derivation chain for the central separation explicitly states that it extends the author's previous work to establish both the existence of the PTM for Ld and that Ld differs from any language in P; the subsequent proof that Ld ∈ BPP and the BPP ⊊ P conclusion therefore rest on that prior self-authored construction rather than an independent derivation or external benchmark supplied in the present manuscript. This matches the self-citation load-bearing pattern with no machine-checked or externally falsifiable support cited for the key non-membership claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract supplies no explicit free parameters, background axioms, or invented entities; the construction of L_d is referenced only to prior self-work whose details are absent here.

pith-pipeline@v0.9.0 · 5937 in / 1165 out tokens · 63070 ms · 2026-05-24T07:26:45.079459+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.