Simple quantum algorithm to efficiently prepare sparse states

Research output: Contribution to journal › Article › Research › peer review

Authors

Research Organisations

View graph of relations

Details

Original languageEnglish
Article number032609
Pages (from-to)032609
Number of pages10
JournalPhysical Review A
Volume110
Issue number3
Publication statusPublished - 10 Sept 2024

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.

ASJC Scopus subject areas

Cite this

Simple quantum algorithm to efficiently prepare sparse states. / Ramacciotti, Debora; Lefterovici, Andreea I.; Rotundo, Antonio F.
In: Physical Review A, Vol. 110, No. 3, 032609, 10.09.2024, p. 032609.

Research output: Contribution to journal › Article › Research › peer review

Ramacciotti D, Lefterovici AI, Rotundo AF. Simple quantum algorithm to efficiently prepare sparse states. Physical Review A. 2024 Sept 10;110(3):032609. 032609. doi: 10.48550/arXiv.2310.19309, 10.1103/PhysRevA.110.032609
Ramacciotti, Debora ; Lefterovici, Andreea I. ; Rotundo, Antonio F. / Simple quantum algorithm to efficiently prepare sparse states. In: Physical Review A. 2024 ; Vol. 110, No. 3. pp. 032609.
Download
@article{549c785162ba48a5bda763f2a4b7df3a,
title = "Simple quantum algorithm to efficiently prepare sparse states",
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.",
author = "Debora Ramacciotti and Lefterovici, {Andreea I.} and Rotundo, {Antonio F.}",
note = "Publisher Copyright: {\textcopyright} 2024 American Physical Society.",
year = "2024",
month = sep,
day = "10",
doi = "10.48550/arXiv.2310.19309",
language = "English",
volume = "110",
pages = "032609",
journal = "Physical Review A",
issn = "2469-9926",
publisher = "American Physical Society",
number = "3",

}

Download

TY - JOUR

T1 - Simple quantum algorithm to efficiently prepare sparse states

AU - Ramacciotti, Debora

AU - Lefterovici, Andreea I.

AU - Rotundo, Antonio F.

N1 - Publisher Copyright: © 2024 American Physical Society.

PY - 2024/9/10

Y1 - 2024/9/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85204345807&partnerID=8YFLogxK

U2 - 10.48550/arXiv.2310.19309

DO - 10.48550/arXiv.2310.19309

M3 - Article

VL - 110

SP - 032609

JO - Physical Review A

JF - Physical Review A

SN - 2469-9926

IS - 3

M1 - 032609

ER -