Preparing Many Copies of a Quantum State in the Black-Box Model
arXiv:2207.11014 · doi:10.1103/PhysRevA.105.062440
Abstract
We describe a simple quantum algorithm for preparing copies of an -dimensional quantum state whose amplitudes are given by a quantum oracle. Our result extends a previous work of Grover, who showed how to prepare one copy in time . In comparison with the naive solution obtained by repeating this procedure~ times, our algorithm achieves the optimal running time of . Our technique uses a refinement of the quantum rejection sampling method employed by Grover. As a direct application, we obtain a similar speed-up for obtaining independent samples from a distribution whose probability vector is given by a quantum oracle.
arXiv comment5 pages, 2 figures
References in corpus (16)
- Quantum algorithm for solving linear systems of equations
- Quantum Amplitude Amplification and Estimation
- Efficient Simulation of Quantum Systems by Quantum Computers
- A Quantum Algorithm for Finding the Minimum
- Quantum-state preparation with universal gate decompositions
- Search via Quantum Walk
- Creating superpositions that correspond to efficiently integrable probability distributions
- High-order quantum algorithm for solving linear differential equations
- Quantum Simulations of Classical Annealing Processes
- Speed-up via Quantum Sampling
- Black-box quantum state preparation without arithmetic
- Quantum query complexity of some graph problems
- Quantum Inference on Bayesian Networks
- Wavefunction preparation and resampling using a quantum computer
- Rapid sampling through quantum computing
- Faster quantum mixing for slowly evolving sequences of Markov chains