Near-Heisenberg-limited parallel amplitude estimation with logarithmic-depth circuits

Quantum amplitude estimation is one of the core subroutines in quantum algorithms. This paper gives a parallelized amplitude estimation (PAE) algorithm that simultaneously achieves near-Heisenberg scaling in the total number of queries and sub-linear scaling in the circuit depth, with respect to the estimation precision. The algorithm is composed of a global GHZ state followed by separated low-depth Grover circuits optimized by quantum signal processing techniques; the number of qubits in the GHZ state and the depth of each circuit is tunable as a trade-off way, which particularly enables even near-Heisenberg-limited and logarithmic-depth algorithm for amplitude estimation. We prove that this trade-off scaling is nearly optimal with use of the parallel quantum adversary method, against folklore on the impossibility of efficient parallelization in amplitude estimation. The proposed algorithm has a form of distributed quantum computing, which may be suitable for device implementation.

Authors

Publication Details

Journal
Physical Review Letters
Published
2026-11-17
DOI
https://doi.org/10.1103/kj68-lpjp
Citations
4
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
4.23

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Near-Heisenberg-limited parallel amplitude estimation with logarithmic-depth circuits

Kaito Wada, Naoki Yamamoto, Kohei Oshio
4 citations
Physical Review Letters
Quantum Computing Algorithms and Architecture
4.23
article

Near-Heisenberg-limited parallel amplitude estimation with logarithmic-depth circuits

Kaito Wada, Naoki Yamamoto, Kohei Oshio
article en
4 citations

Abstract

Quantum amplitude estimation is one of the core subroutines in quantum algorithms. This paper gives a parallelized amplitude estimation (PAE) algorithm that simultaneously achieves near-Heisenberg scaling in the total number of queries and sub-linear scaling in the circuit depth, with respect to the estimation precision. The algorithm is composed of a global GHZ state followed by separated low-depth Grover circuits optimized by quantum signal processing techniques; the number of qubits in the GHZ state and the depth of each circuit is tunable as a trade-off way, which particularly enables even near-Heisenberg-limited and logarithmic-depth algorithm for amplitude estimation. We prove that this trade-off scaling is nearly optimal with use of the parallel quantum adversary method, against folklore on the impossibility of efficient parallelization in amplitude estimation. The proposed algorithm has a form of distributed quantum computing, which may be suitable for device implementation.

Physical Review Letters
Keio University, Ministry of Education, Culture, Sports, Science and Technology, Japan Society for the Promotion of Science
Openalex Percentile: Top 6%
Quantum Computing Algorithms and Architecture
4.23
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon