Quantum computers speed up classical with probability zero

DOI10.1016/S0960-0779(98)00226-4MaRDI QIDQ1573934zbMATH OpenOpenAlexWikidataFDO

Authors Yuri Ozhigov

Publication date 9 August 2000

Published in Chaos, Solitons and Fractals (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9803064

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: Let $f$ denote length preserving function on words. A classical algorithm can be considered as $T$ iterated applications of black box representing $f$, beginning with input word $x$ of length $n$. It is proved that if $T=O(2^{n/(7+e)}),e>0$, and $f$ is chosen randomly then with probability 1 every quantum computer requires not less than $T$ evaluations of $f$ to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity $T$ and $f$ chosen randomly with probability 1 every quantum simulation of classical computation requires at least $Omega(sqrtT)$ evaluations of $f$.

Recommendations

• A little bit of classical magic to achieve (super-)quantum speedup
• Computing with a single qubit faster than the computation quantum speed limit
• Quantum computing with classical bits
• Quantum speedup of Bayes’ classifiers
• Quantum computers that can be simulated classically in polynomial time
• Understanding the quantum computational speed-up via de-quantisation
• Classical computation with quantum systems
• The elusive source of quantum speedup
• Problems and prospects for quantum computational speed-up

Cited in

(9)

• Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
• On the complexity of simulating space-bounded quantum computations
• Quantum computing with classical bits
• A little bit of classical magic to achieve (super-)quantum speedup
• Quantum and classical tradeoffs
• scientific article; zbMATH DE number 1406121 (Why is no real title available?)
• Quantum computers that can be simulated classically in polynomial time
• QUANTUM-CLASSICAL CORRESPONDENCE IN THE ORACLE MODEL OF COMPUTATION
• Fourier 1-norm and quantum speed-up

This page was built for publication: Quantum computers speed up classical with probability zero

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1573934)