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
- Kaito Wada (ORCID: https://orcid.org/0000-0003-4976-4530)
- Naoki Yamamoto (ORCID: https://orcid.org/0000-0002-8497-4608)
- Kohei Oshio
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
- Keio University
- Ministry of Education, Culture, Sports, Science and Technology
- Japan Society for the Promotion of Science