1999/02/08 by Giuseppe Castagnoli, Castagnoli, Giuseppe
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9902027
9 text pages, 3 figures in one additional ps file, manuscript of the presentation to be held at the SILFS Workshop on Logic and Quantum Computation, Cesena, Italy, February 16, 1999
arxiv created 1999/02/08 · openalex publication_date 1999/02/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A typical oracle problem is finding which software program is installed on a computer, by running the computer and testing its input-output behaviour. The program is randomly chosen from a set of programs known to the problem solver. As well known, some oracle problems are solved more efficiently by using quantum algorithms; this naturally implies changing the computer to quantum, while the choice of the software program remains sharp. In order to highlight the non-mechanistic origin of this higher efficiency, also the uncertainty about which program is installed must be represented in a quantum way.