Rapid sampling through quantum computing

Abstract

This paper extends the quantum search class of algorithms to the multiple solution case. It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space. This yields new applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(N)) steps. By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(sqrt(N)) steps. A classical algorithm would need O(N) steps.

arXiv commentThe paper has been rewritten. It is to be presented at STOC '00 in May '00

References in corpus (1)

• Quantum Mechanics helps in searching for a needle in a haystack

Cited by in corpus (6)

• Quantum Inference on Bayesian Networks
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Quantum rejection sampling
• Robust Quantum Algorithms for Oracle Identification
• Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network
• Preparing Many Copies of a Quantum State in the Black-Box Model