Fast Black-Box Quantum State Preparation

Abstract

Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage. In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in $O(\sqrt{N})$ rounds of amplitude amplification, up to only $O(1)$ many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas (${\log }_{2}g$ vs $g+2$ in the bit precision $g$), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ($g+{\log }_{2}g$) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.

31 pages, 5 figures, 2 tables; v3: minor changes to 2.3.2

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Quantum-state preparation with universal gate decompositions
• A new quantum ripple-carry addition circuit
• Creating superpositions that correspond to efficiently integrable probability distributions
• Fixed-point quantum search with an optimal number of queries
• A divide-and-conquer algorithm for quantum state preparation
• Simulating chemistry efficiently on fault-tolerant quantum computers

Cited by in corpus (18)

• Quantum computing for finance
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Efficient quantum amplitude encoding of polynomial functions
• Quantum algorithms for approximate function loading
• Double sparse quantum state preparation
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Quantum State Preparation of Normal Distributions using Matrix Product States
• Representation of binary classification trees with binary features by quantum circuits
• Option pricing under stochastic volatility on a quantum computer
• Quantum state preparation for multivariate functions
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Noise-Aware Quantum Amplitude Estimation
• Quantum mean estimation for lattice field theory
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum state preparation via piecewise QSVT
• A general approach to quantum integration of cross sections in high-energy physics
• Quantum Encoding of Structured Data with Matrix Product States
• Time series generation for option pricing on quantum computers using tensor network