A simple quantum algorithm to efficiently prepare sparse states
Preprint
Abstract
State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper, we analyse the performance of this algorithm when the state to prepare is sparse. We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparationKeywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023
- Efficient deterministic preparation of quantum states using decision diagramsPhysical Review A, 2022
- Quantum-state preparation with universal gate decompositionsPhysical Review A, 2011
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009