A Gentle Introduction to Quantum Computing Algorithms with Applications to Universal Prediction

• URL: http://arxiv.org/abs/2005.03137v1
• Date: Wed, 29 Apr 2020 11:46:52 GMT
• Title: A Gentle Introduction to Quantum Computing Algorithms with Applications to Universal Prediction
• Authors: Elliot Catt and Marcus Hutter
• Abstract summary: This technical report gives an elementary introduction to Quantum Computing for non-physicists. We describe some of the foundational Quantum Algorithms including: the Deutsch-Jozsa Algorithm, Shor's Algorithm, Grocer Search, and Quantum Counting Algorithm. We then attempt to use Quantum computing to find better algorithms for the approximation of Solomonoff Induction.
• Score: 21.344529157722366
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Fast Algorithms and Implementations for Computing the Minimum Distance of Quantum Codes [43.96687298077534]
  The distance of a stabilizer quantum code determines the number of errors that can be detected and corrected. We present three new fast algorithms and implementations for computing the symplectic distance of the associated classical code.
  arXiv  Detail & Related papers  (2024-08-20T11:24:30Z)
• A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
  This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states. It is executable on current (hybrid) quantum hardware and does not depend on quantum memory. We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
  arXiv  Detail & Related papers  (2024-05-29T14:40:24Z)
• Large-scale simulation of Shor's quantum factoring algorithm [0.0]
  We show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm. We find average success probabilities above 50 %, due to a high frequency of "lucky" cases. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors.
  arXiv  Detail & Related papers  (2023-08-09T16:19:52Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Algorithm For Estimating Eigenvalue [0.0]
  We provide a quantum algorithm for estimating the largest eigenvalue in magnitude of a given Hermitian matrix. Our quantum procedure can also yield exponential speedup compared to classical algorithms that solve the same problem.
  arXiv  Detail & Related papers  (2022-11-11T13:02:07Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Hybrid Quantum Computing -- Tabu Search Algorithm for Partitioning Problems: preliminary study on the Traveling Salesman Problem [0.8434687648198277]
  We introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses.
  arXiv  Detail & Related papers  (2020-12-09T11:21:50Z)
• Quantum algorithmic differentiation [0.0]
  We present an algorithm to perform algorithmic differentiation in the context of quantum computing. We present two versions of the algorithm, one which is fully quantum and one which employees a classical step.
  arXiv  Detail & Related papers  (2020-06-23T22:52:22Z)
• Towards quantum advantage via topological data analysis [0.0]
  We study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi. We provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis.
  arXiv  Detail & Related papers  (2020-05-06T06:31:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.