2005/01/04 by Antoni Wójcik, Antoni Wojcik, Wojcik, Antoni +2
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0501016
arxiv created 2005/01/04 · openalex publication_date 2005/01/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quantum computers are believed to surpass the classical ones. Moreover, it is claimed that this belief reaches the level of a mathematically proven fact within the oracle model of computation. Here we impair the whole class of the so-called rigorist proofs of quantum speed-up obtained within this model.