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

Almost-Everywhere Superiority for Quantum Polynomial-Time Languages

Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand

Published Aug 1, 2002• 1 citation
OpenAlex

Abstract

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

Related papers

Almost-Everywhere Superiority for Quantum Polynomial Time

Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand

arXiv:quant-ph/9910033•Information and Computation•Jun 1, 2002•19 citations

Quantum Computation

Cristopher Moore, Stephan Mertens

Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.

Oxford University Press eBooks•Aug 11, 2011•0 citations

Magic coins are useful for small-space quantum machines

A. C. Cem Say, Abuzer Yakaryılmaz

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double logarithmic space, it is known that such “magic coins” give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton (2qcfa) that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.

arXiv:1411.7647•Quantum Information and Computation•Sep 1, 2017•13 citations

On the Class of Languages Recognizable by 1-Way Quantum Finite Automata

Andris Ambainis, Arnolds Ķikusts, Māris Valdats

Springer eBooks•Jun 12, 2007•46 citations

Computational Complexity Theory of Quantum Turing Machines and Quantum Circuits

Harumichi Nishimura, 治道 西村

•Mar 26, 2001•1 citation

Quantum function computation using sublogarithmic space (abstract & poster)

A. C. Cem Say, Abuzer Yakaryılmaz

We prove that quantum Turing machines are strictly superior to probabilistic Turing machines in function computation for any space bound $ o(\log(n)) $.

arXiv:1009.3124•Sep 16, 2010•5 citations
Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double logarithmic space, it is known that such “magic coins” give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton (2qcfa) that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.