2001/11/01 by Boris Tsirelson, Tsirelson, Boris
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/0111009
arxiv created 2001/11/01 · openalex publication_date 2001/11/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently T. Kieu (arXiv:quant-ph/0110136) claimed a quantum algorithm computing some functions beyond the Church-Turing class. He notes that "it is in fact widely believed that quantum computation cannot offer anything new about computability" and claims the opposite. However, his quantum algorithm does not work, which is the point of my short note. I still believe that quantum computation leads to new complexity but retains the old computability.