Rapid sampling though quantum computing

DOI10.1145/335305.335389MaRDI QIDQ3192034zbMATH OpenOpenAlexFDO

Authors Lov K. Grover

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9912001

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

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.

Recommendations

• scientific article; zbMATH DE number 2103524
• A panoply of quantum algorithms
• Rapid solution of problems by quantum computation
• Quantum search on structured problems
• scientific article; zbMATH DE number 1406118

Cited in

(7)

• Quantum counting: algorithm and error distribution
• Quantum speedup of Monte Carlo methods
• A new quantum claw-finding algorithm for three functions
• The equivalence of sampling and searching
• The equivalence of sampling and searching
• Solving NP-Complete Problems with Quantum Search
• Quantum sampling for balanced allocations

This page was built for publication: Rapid sampling though quantum computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192034)