Quantum rejection sampling

Abstract

Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann (1951) and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this paper is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle which allows to symmetrize any algorithm over the automorphism group of the problem. Our main technical innovation is an extension of the automorphism principle to continuous groups that arise for quantum state generation problems where the oracle encodes unknown quantum states, instead of just classical data. Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow, Hassidim and Lloyd. Secondly, we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al.. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function and relate its query complexity to "water-filling" of the Fourier spectrum.

19 pages, 5 figures, minor changes and a more compact style (to appear in proceedings of ITCS 2012)

References in corpus (12)

• Quantum algorithm for solving linear systems of equations
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum Copy-Protection and Quantum Money
• Quantum Simulations of Classical Annealing Processes
• A Quantum-Quantum Metropolis Algorithm
• Quantum query complexity of state conversion
• Simulating sparse Hamiltonians with star decompositions
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Wavefunction preparation and resampling using a quantum computer
• Approximating Fractional Time Quantum Evolution
• Quantum state preparation by phase randomization
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (14)

• Fixed-point quantum search with an optimal number of queries
• Quantum Inference on Bayesian Networks
• Preparing projected entangled pair states on a quantum computer
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Representation of binary classification trees with binary features by quantum circuits
• Reachability Analysis of Quantum Markov Decision Processes
• Easy and hard functions for the Boolean hidden shift problem
• Experimental Challenges of Implementing Quantum Phase Estimation Algorithms on IBM Quantum Computer
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
• Algorithmic Cooling of a Quantum Simulator
• Variational Quantum Algorithms for Gibbs State Preparation
• Quantum binary field inversion: improved circuit depth via choice of basis representation
• Quantum Speedup for Nonreversible Markov Chains