2020/04/29 by Elliot Catt, Marcus Hutter, Catt, Elliot +2 · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.ET #quant-ph
paper · pdf · doi:10.48550/arxiv.2005.03137
arxiv created 2020/04/29 · openalex publication_date 2020/04/29 · arxiv updated 2020/05/08 · openalex created_date 2020/05/13 · openalex updated_date 2026/07/28
In this technical report we give an elementary introduction to Quantum Computing for non-physicists. In this introduction we describe in detail some of the foundational Quantum Algorithms including: the Deutsch-Jozsa Algorithm, Shor's Algorithm, Grocer Search, and Quantum Counting Algorithm and briefly the Harrow-Lloyd Algorithm. Additionally we give an introduction to Solomonoff Induction, a theoretically optimal method for prediction. We then attempt to use Quantum computing to find better algorithms for the approximation of Solomonoff Induction. This is done by using techniques from other Quantum computing algorithms to achieve a speedup in computing the speed prior, which is an approximation of Solomonoff's prior, a key part of Solomonoff Induction. The major limiting factors are that the probabilities being computed are often so small that without a sufficient (often large) amount of trials, the error may be larger than the result. If a substantial speedup in the computation of an approximation of Solomonoff Induction can be achieved through quantum computing, then this can be applied to the field of intelligent agents as a key part of an approximation of the agent AIXI.