Simple quantum algorithm to efficiently prepare sparse states
- 10 September 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 110 (3) , 032609
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 analyze the performance of this algorithm when the state to prepare is sparse. We show that the gate complexity is linear in the number of nonzero 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 preparation.Keywords
All Related Versions
Funding Information
- Quantum Valley Lower Saxony
- Bundesministerium für Forschung, Technologie und Raumfahrt
This publication has 11 references indexed in Scilit:
- Quantum algorithms for approximate function loadingPhysical Review Research, 2023
- Quantum State Preparation with Optimal Circuit Depth: Implementations and ApplicationsPhysical Review Letters, 2022
- Efficient deterministic preparation of quantum states using decision diagramsPhysical Review A, 2022
- Double sparse quantum state preparationQuantum Information Processing, 2022
- Quantum Circuits for Sparse IsometriesQuantum, 2021
- Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on PrecisionSIAM Journal on Computing, 2017
- Quantum simulationReviews of Modern Physics, 2014
- Quantum-state preparation with universal gate decompositionsPhysical Review A, 2011
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Simulating quantum systems on a quantum computerProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1998