Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1111.3125 · Fundamenta Informaticae

Proving the Power of Postselection

Abuzer Yakaryılmaz, A. C. Cem Say

Published Jan 1, 2013• 10 citations
arXivHTMLPDF

Abstract

It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machine
DOI
10.3233/fi-2013-803

Related papers

Almost-Everywhere Superiority for Quantum Polynomial-Time Languages

Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand

We prove that there are languages for which polynomial-time quantum machines are exponentially faster than each classical machine almost everywhere.

•Aug 1, 2002•1 citation

Postselection Finite Quantum Automata

Oksana Scegulnaja-Dubrovska, Lelde Lāce, Rūsiņš Freivalds

Lecture notes in computer science•Jan 1, 2010•6 citations

Probabilistic and quantum finite automata with postselection

Abuzer Yakaryılmaz, A. C. Cem Say

We prove that endowing a real-time probabilistic or quantum computer with the ability of postselection increases its computational power. For this purpose, we provide a new model of finite automata with postselection, and compare it with the model of Lāce et al. We examine the related language classes, and also establish separations between the classical and quantum versions, and between the zero-error vs. bounded-error modes of recognition in this model.

arXiv:1102.0666•Feb 3, 2011•14 citations

Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization

Tianrong Lin

In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time $O(n^k)$ for every $k\in\mathbb{N}_1$ and accepts a language $L_d\notin\mathcal{P}$. We further show that $L_d\in\mathcal{BPP}$, thereby separating $\mathcal{BPP}$ from $\mathcal{P}$ (i.e., $\mathcal{P}\subsetneqq\mathcal{BPP}$). Since the complexity class $\mathcal{BQP}$ of {\em bounded error quantum polynomial-time computation} contains $\mathcal{BPP}$ (i.e., $\mathcal{BPP}\subseteq\mathcal{BQP}$), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic 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 establish the following separations: (1) $\mathcal{P}\subsetneqq\mathcal{RP}$; (2) $\mathcal{P}\subsetneqq{\rm co}\mathcal{RP}$; (3) $\mathcal{P}\subsetneqq\mathcal{ZPP}$. These relationships were long-standing open questions in complexity theory. In addition, the separation $\mathcal{P}\subsetneqq\mathcal{BPP}$ demonstrates that {\em randomness} plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting $L_d$ cannot 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$ with $k(n)=O(\log n)$.

arXiv:2308.09549•Aug 18, 2023•0 citations

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Marshall, Simon C., Scott Aaronson, Vedran Dunjko

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.

arXiv:2410.20935•Leibniz international proceedings in informatics•Oct 28, 2024•14 citations

Investigating the Use of Quantum Computing and Quantum Machine Learning in Speech Recognition Systems: A Comprehensive Survey of Recent Advancements

Paramita Basak Upama, Parama Sridevi, Shoumili Dutta +3 more

Communications in computer and information science•Jan 1, 2026•0 citations
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time O(nk)O(n^k)O(nk) for every k∈N1k\in\mathbb{N}_1k∈N1​ and accepts a language Ld∉PL_d\notin\mathcal{P}Ld​∈/P. We further show that Ld∈BPPL_d\in\mathcal{BPP}Ld​∈BPP, thereby separating BPP\mathcal{BPP}BPP from P\mathcal{P}P (i.e., P⫋BPP\mathcal{P}\subsetneqq\mathcal{BPP}P⫋BPP). Since the complexity class BQP\mathcal{BQP}BQP of {\em bounded error quantum polynomial-time computation} contains BPP\mathcal{BPP}BPP (i.e., BPP⊆BQP\mathcal{BPP}\subseteq\mathcal{BQP}BPP⊆BQP), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e., P⫋BQP\mathcal{P}\subsetneqq\mathcal{BQP}P⫋BQP). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we establish the following separations: (1) P⫋RP\mathcal{P}\subsetneqq\mathcal{RP}P⫋RP; (2) P⫋coRP\mathcal{P}\subsetneqq{\rm co}\mathcal{RP}P⫋coRP; (3) P⫋ZPP\mathcal{P}\subsetneqq\mathcal{ZPP}P⫋ZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation P⫋BPP\mathcal{P}\subsetneqq\mathcal{BPP}P⫋BPP demonstrates that {\em randomness} plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting LdL_dLd​ cannot be reduced to O(log⁡n)O(\log n)O(logn); (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG): G:{0,1}O(log⁡n)→{0,1}n; G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n;G:{0,1}O(logn)→{0,1}n; (6) There exists no quick HSG H:k(n)→nH:k(n)\rightarrow nH:k(n)→n with k(n)=O(log⁡n)k(n)=O(\log n)k(n)=O(logn).
This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP=PostBPP\mathsf{PostBQP=PostBPP}PostBQP=PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling\mathsf{BosonSampling}BosonSampling, IQP\mathsf{IQP}IQP, DQC1\mathsf{DQC1}DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠FBPP\mathsf{FBQP\neq FBPP}FBQP=FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPPNP\mathsf{ZPP^{NP}}ZPPNP.