Physics – Quantum Physics
Scientific paper
2011-03-14
Proceedings of the 3rd Conference on Innovations in Theoretical Computer Science (ITCS'12), ACM Press, 2012, pages 290-308
Physics
Quantum Physics
19 pages, 5 figures, minor changes and a more compact style (to appear in proceedings of ITCS 2012)
Scientific paper
10.1145/2090236.2090261
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.
Ozols Maris
Roetteler Martin
Roland Jérémie
No associations
LandOfFree
Quantum rejection sampling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum rejection sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum rejection sampling will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-138155