2017/08/30 by Florian Neukart, Neukart, Florian, David Von Dollen +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1708.09354
openalex publication_date 2017/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quantum annealing algorithms belong to the class of metaheuristic tools,\napplicable for solving binary optimization problems. Hardware implementations\nof quantum annealing, such as the quantum annealing machines produced by D-Wave\nSystems, have been subject to multiple analyses in research, with the aim of\ncharacterizing the technology's usefulness for optimization and sampling tasks.\nHere, we present a way to partially embed both Monte Carlo policy iteration for\nfinding an optimal policy on random observations, as well as how to embed (n)\nsub-optimal state-value functions for approximating an improved state-value\nfunction given a policy for finite horizon games with discrete state spaces on\na D-Wave 2000Q quantum processing unit (QPU). We explain how both problems can\nbe expressed as a quadratic unconstrained binary optimization (QUBO) problem,\nand show that quantum-enhanced Monte Carlo policy evaluation allows for finding\nequivalent or better state-value functions for a given policy with the same\nnumber episodes compared to a purely classical Monte Carlo algorithm.\nAdditionally, we describe a quantum-classical policy learning algorithm. Our\nfirst and foremost aim is to explain how to represent and solve parts of these\nproblems with the help of the QPU, and not to prove supremacy over every\nexisting classical policy evaluation algorithm.\n