pith. sign in

arxiv: 2508.06121 · v2 · submitted 2025-08-08 · 🪐 quant-ph

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

Kohei Oshio , Kaito Wada , Naoki Yamamoto This is my paper

Pith reviewed 2026-05-19 00:59 UTC · model grok-4.3

classification 🪐 quant-ph
keywords amplitude estimationparallel algorithmsHeisenberg limitGrover's algorithmquantum signal processingGHZ statesdistributed computing
0
0 comments X

The pith

Quantum amplitude estimation can achieve near-Heisenberg scaling in queries with only logarithmic circuit depth through parallelization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a parallel amplitude estimation algorithm that starts with preparing a global GHZ state across several qubits. It then runs separate low-depth Grover circuits on each, with the circuits designed using quantum signal processing to optimize for the target precision. This construction keeps the overall number of queries close to the Heisenberg bound of one over the error, but makes the depth of the circuits grow only as the logarithm of one over the error. A reader would care because this removes a major barrier for running high-precision estimation on quantum hardware that has limited coherence time. The authors further prove that this scaling is nearly optimal by using the parallel quantum adversary method.

Core claim

The central claim is that by preparing a global GHZ state and applying low-depth Grover circuits independently on the qubits, with optimization from quantum signal processing, amplitude estimation can be performed with query complexity scaling near O(1/ε) and circuit depth scaling as O(log 1/ε), where ε is the estimation precision, and this is shown to be nearly optimal.

What carries the argument

The combination of a global GHZ state with parallel low-depth Grover circuits optimized by quantum signal processing techniques.

If this is right

  • The algorithm takes the form of distributed quantum computing, making it potentially suitable for modular device implementations.
  • The number of qubits in the GHZ state and the depth of the circuits can be traded off to suit different hardware constraints.
  • The optimality proof counters previous beliefs that efficient parallelization of amplitude estimation is impossible.
  • The approach allows amplitude estimation to be performed with reduced depth requirements while maintaining high precision.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This technique might be extended to parallel versions of other quantum algorithms that rely on amplitude estimation as a subroutine.
  • In real devices, the challenge of generating and preserving the GHZ state across many qubits could limit the practical qubit numbers achievable.
  • One could test the logarithmic depth by implementing the algorithm for moderate precision values on current quantum simulators and measuring the required circuit size.

Load-bearing premise

The approach depends on being able to prepare a global GHZ state that remains intact while the separate circuits perform their operations.

What would settle it

If experiments show that the precision of the amplitude estimate does not improve proportionally to the inverse of the square root of the total queries, or if the circuit depth must be increased beyond logarithmic scaling to achieve the target precision, the claimed performance would be falsified.

Figures

Figures reproduced from arXiv: 2508.06121 by Kaito Wada, Kohei Oshio, Naoki Yamamoto.

Figure 1
Figure 1. Figure 1: FIG. 1. Quantum circuit of PAE, where [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. (a) Relationship between the number of queries to [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Construction of [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a parallel amplitude estimation (PAE) algorithm consisting of a global GHZ state preparation on a tunable number k of qubits followed by independent low-depth Grover circuits (optimized via quantum signal processing) acting on separate registers. It claims to achieve a tunable trade-off yielding near-Heisenberg query complexity O(1/ε) in total oracle uses while keeping circuit depth O(log(1/ε)), and proves this scaling is nearly optimal via the parallel quantum adversary method, framing the approach as suitable for distributed quantum computing.

Significance. If the central claims and proof hold, the result would be a meaningful contribution by providing an explicit construction that simultaneously attains near-optimal query scaling and logarithmic depth for amplitude estimation, directly addressing folklore on the difficulty of parallelizing this subroutine. The tunable GHZ-plus-QSP design and the attempt to prove optimality against lower bounds are concrete strengths that could influence implementations on hardware with coherence or connectivity constraints.

major comments (2)
  1. [Optimality proof section] Optimality proof section (invoking the parallel quantum adversary method): The derivation does not explicitly address whether the pre-shared global GHZ entanglement across registers modifies the effective query model or invalidates direct application of standard parallel-adversary bounds, which typically assume independent oracle calls without prior cross-register correlations. This is load-bearing for the claim that the construction refutes impossibility results and achieves near-optimality, as the abstract relies on this method to establish the Ω(1/ε) total-query lower bound under the distributed setting.
  2. [Algorithm construction] Algorithm description and error analysis: The combination of measurement outcomes from the parallel low-depth circuits into a single amplitude estimate with overall precision ε requires a detailed variance or bias propagation argument that accounts for the tunable k (number of GHZ qubits). Without this, it is unclear whether the claimed near-Heisenberg scaling in total queries is preserved after post-processing.
minor comments (2)
  1. [Introduction] Notation for the tunable parameter k and its relation to depth versus query trade-off could be introduced earlier and used consistently to improve readability.
  2. [Abstract] The abstract states 'near-Heisenberg-limited' without specifying the precise big-O form or logarithmic factors; a brief clarification would help readers assess the exact improvement over standard amplitude estimation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments, which have helped us improve the presentation of the optimality proof and error analysis. We address each major comment below and have revised the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Optimality proof section] Optimality proof section (invoking the parallel quantum adversary method): The derivation does not explicitly address whether the pre-shared global GHZ entanglement across registers modifies the effective query model or invalidates direct application of standard parallel-adversary bounds, which typically assume independent oracle calls without prior cross-register correlations. This is load-bearing for the claim that the construction refutes impossibility results and achieves near-optimality, as the abstract relies on this method to establish the Ω(1/ε) total-query lower bound under the distributed setting.

    Authors: We thank the referee for highlighting this subtlety in the query model. The parallel quantum adversary method is applied directly to the total number of oracle queries across the distributed registers; the GHZ state is prepared in a separate, oracle-independent stage and does not encode information about the unknown amplitude. Consequently, the initial entanglement does not alter the information-theoretic cost of each oracle call or invalidate the lower bound. In the revised manuscript we have added an explicit paragraph in the optimality section that states the model assumptions, confirms that the adversary argument continues to hold in the presence of fixed pre-shared entanglement, and notes that our construction therefore remains near-optimal in the distributed setting. revision: yes

  2. Referee: [Algorithm construction] Algorithm description and error analysis: The combination of measurement outcomes from the parallel low-depth circuits into a single amplitude estimate with overall precision ε requires a detailed variance or bias propagation argument that accounts for the tunable k (number of GHZ qubits). Without this, it is unclear whether the claimed near-Heisenberg scaling in total queries is preserved after post-processing.

    Authors: We agree that an expanded error-propagation argument improves clarity. In the revised manuscript we have added a dedicated subsection that derives the overall estimation error for tunable k. Each of the k parallel registers produces an independent estimate whose variance scales with its circuit depth; these estimates are combined via a classical maximum-likelihood estimator that exploits the GHZ correlations. We explicitly bound the bias (which remains negligible) and show that the total variance yields an overall precision ε while the aggregate query count remains O(1/ε). This confirms that the near-Heisenberg scaling is preserved after post-processing. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation remains self-contained

full rationale

The paper describes a PAE construction that prepares a global GHZ state followed by independent low-depth Grover/QSP circuits whose depth and qubit count are tunable parameters. It then invokes the parallel quantum adversary method to establish near-optimality of the resulting query-depth trade-off. No equation in the abstract or described chain reduces a claimed prediction or first-principles result to a fitted input or self-citation by construction. The adversary method is presented as an external bounding technique applied to the new distributed model rather than a self-derived uniqueness theorem or ansatz smuggled from prior overlapping-author work. The central algorithmic description and scaling claims therefore retain independent content and do not collapse to the inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the ability to prepare and use a global GHZ state in a distributed setting and on the applicability of the parallel quantum adversary method to bound the query complexity of the proposed circuits. No explicit free parameters or invented entities are mentioned in the abstract.

axioms (2)
  • domain assumption A global GHZ state can be prepared and maintained across the tunable number of qubits while independent low-depth circuits operate in parallel.
    Invoked in the description of the algorithm composition (abstract).
  • domain assumption The parallel quantum adversary method provides a valid lower bound on query complexity for this distributed amplitude estimation model.
    Used to prove near-optimality against folklore impossibility results (abstract).

pith-pipeline@v0.9.0 · 5673 in / 1532 out tokens · 30448 ms · 2026-05-19T00:59:01.550354+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Low-depth amplitude estimation via statistical eigengap estimation

    quant-ph 2026-03 unverdicted novelty 6.0

    A new ancilla-free amplitude estimation method uses statistical eigengap estimation to achieve near-optimal query-depth tradeoffs in low-depth regimes with provable guarantees.

Reference graph

Works this paper leans on

74 extracted references · 74 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

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

    The QSP operator denotes an engineered phase shifter constructed by quantum signal processing (QSP), represented as Vφ,T in the main text. Reducing the circuit depth even at the expense of in- creasing the number of qubits is often an effective ap- proach to make quantum circuits easier to implement, which is thus a central paradigm in quantum algorithm s...

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  2. [2]

    Full parallel

    That is, the phase φ is successfully kick backed to the ancilla space with multiplicative enhancement factorM = P T. Again, this is the transformation on the Grover plane. Also note that |0⟩⊗nP s can now be prepared without knowing |Q±⟩ . The quantum circuit for this operation is illustrated in Fig. 1, where the QSP operator denotes Vφ,T . Note that for a...

    work page

  3. [3]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Quantum metrology, Phys. Rev. Lett. 96, 010401 (2006)

    work page 2006

  4. [4]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Advances in quantum metrology, Nat. photonics 5, 222 (2011)

    work page 2011

  5. [5]

    Knill, G

    E. Knill, G. Ortiz, and R. D. Somma, Optimal quantum measurements of expectation values of observables, Phys. Rev. A—Atomic Molecular Optical Physics 75, 012328 (2007)

    work page 2007

  6. [6]

    Kimmel, G

    S. Kimmel, G. H. Low, and T. J. Yoder, Robust calibra- tion of a universal single-qubit gate set via robust phase estimation, Phys. Rev. A 92, 062315 (2015)

    work page 2015

  7. [7]

    G. Wang, D. E. Koh, P. D. Johnson, and Y. Cao, Mini- mizing estimation runtime on noisy quantum computers, PRX Quantum 2, 010346 (2021)

    work page 2021

  8. [8]

    Dutkiewicz, B

    A. Dutkiewicz, B. M. Terhal, and T. E. O’Brien, Heisenberg-limited quantum phase estimation of multi- ple eigenvalues with few control qubits, Quantum 6, 830 (2022)

    work page 2022

  9. [9]

    Ding and L

    Z. Ding and L. Lin, Even shorter quantum circuit for phase estimation on early fault-tolerant quantum com- puters with applications to ground-state energy estima- tion, PRX Quantum 4, 020331 (2023)

    work page 2023

  10. [10]

    H. Ni, H. Li, and L. Ying, On low-depth algorithms for quantum phase estimation, Quantum 7, 1165 (2023)

    work page 2023

  11. [11]

    K. Wada, K. Fukuchi, and N. Yamamoto, Quantum- enhanced mean value estimation via adaptive measure- ment, Quantum 8, 1463 (2024)

    work page 2024

  12. [12]

    Oshio, Y

    K. Oshio, Y. Suzuki, K. Wada, K. Hisanaga, S. Uno, and N. Yamamoto, Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits, Phys. Rev. A 110, 062423 (2024)

    work page 2024

  13. [13]

    K. Wada, N. Yamamoto, and N. Yoshioka, Heisenberg- limited adaptive gradient estimation for multiple observ- ables, PRX Quantum 6, 020308 (2025)

    work page 2025

  14. [14]

    Brassard, P

    G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemp. Math. 305, 53 (2002)

    work page 2002

  15. [15]

    Kassal, S

    I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics, Proc. Natl. Acad. Sci. 105, 18681 (2008)

    work page 2008

  16. [16]

    Lin and Y

    L. Lin and Y. Tong, Near-optimal ground state prepara- tion, Quantum 4, 372 (2020)

    work page 2020

  17. [17]

    Y. Dong, L. Lin, and Y. Tong, Ground-state prepara- tion and energy estimation on early fault-tolerant quan- tum computers via quantum eigenvalue transformation of unitary matrices, PRX quantum 3, 040305 (2022)

    work page 2022

  18. [18]

    T. E. O’Brien, M. Streif, N. C. Rubin, R. Santagati, Y. Su, W. J. Huggins, J. J. Goings, N. Moll, E. Kyoseva, M. Degroote, C. S. Tautermann, J. Lee, D. W. Berry, N. Wiebe, and R. Babbush, Efficient quantum computa- tion of molecular forces and other energy gradients, Phys. Rev. Res. 4, 043210 (2022)

    work page 2022

  19. [19]

    Rebentrost, B

    P. Rebentrost, B. Gupt, and T. R. Bromley, Quantum computational finance: Monte carlo pricing of financial derivatives, Phys. Rev. A 98, 022321 (2018)

    work page 2018

  20. [20]

    Woerner and D

    S. Woerner and D. J. Egger, Quantum risk analysis, npj Quantum Inf. 5, 15 (2019)

    work page 2019

  21. [21]

    Stamatopoulos, D

    N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner, Option pricing using quantum computers, Quantum 4, 291 (2020)

    work page 2020

  22. [22]

    Wiebe, A

    N. Wiebe, A. Kapoor, and K. M. Svore, Quantum algo- rithms for nearest-neighbor methods for supervised and unsupervised learning, Quantum Inf. Comput. 15, 316 (2015)

    work page 2015

  23. [23]

    Wiebe, A

    N. Wiebe, A. Kapoor, and K. M. Svore, Quantum deep learning, Quantum Inf. Comput. 16, 541 (2016)

    work page 2016

  24. [24]

    Kapoor, N

    A. Kapoor, N. Wiebe, and K. Svore, Quantum percep- tron models, Adv. neural inf. process. syst. 29 (2016)

    work page 2016

  25. [25]

    Kerenidis, J

    I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, q- means: A quantum algorithm for unsupervised machine learning, Adv. neural inf. process. syst. 32 (2019)

    work page 2019

  26. [26]

    Suzuki, S

    Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Amplitude estimation without phase estimation, Quantum Inf. Process. 19, 1 (2020)

    work page 2020

  27. [27]

    Grinko, J

    D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, Iterative quantum amplitude estimation, npj Quantum Inf. 7, 52 (2021)

    work page 2021

  28. [28]

    Aaronson and P

    S. Aaronson and P. Rall, Quantum approximate count- ing, simplified, in Symposium on simplicity in algorithms (SIAM, 2020) pp. 24–32

    work page 2020

  29. [29]

    Nakaji, Faster amplitude estimation, Quantum Inf

    K. Nakaji, Faster amplitude estimation, Quantum Inf. Comput. 20, 1109 (2020)

    work page 2020

  30. [30]

    Intallura, G

    P. Intallura, G. Korpas, S. Chakraborty, V. Kun- gurtsev, and J. Marecek, A survey of quantum alter- natives to randomized algorithms: Monte carlo inte- gration and beyond, arXiv preprint arXiv:2303.04945 10.48550/arXiv.2303.04945 (2023)

    work page doi:10.48550/arxiv.2303.04945 2023

  31. [31]

    Labib, B

    F. Labib, B. D. Clader, N. Stamatopoulos, and W. J. Zeng, Quantum amplitude estimation from clas- sical signal processing, arXiv preprint arXiv:2405.14697 10.48550/arXiv.2405.14697 (2024)

    work page doi:10.48550/arxiv.2405.14697 2024

  32. [32]

    Cleve and J

    R. Cleve and J. Watrous, Fast parallel circuits for the quantum fourier transform, in Proceedings 41st Annual Symposium on Foundations of Computer Science (IEEE,

    work page

  33. [33]

    Moore and M

    C. Moore and M. Nilsson, Parallel quantum computation and quantum codes, SIAM j. comput. 31, 799 (2001)

    work page 2001

  34. [34]

    Høyer and R

    P. Høyer and R. ˇSpalek, Quantum fan-out is powerful, Theory comput. 1, 81 (2005)

    work page 2005

  35. [35]

    Pham and K

    P. Pham and K. M. Svore, A 2d nearest-neighbor quan- tum architecture for factoring in polylogarithmic depth, Quantum Inf. Comput. 13, 937 (2013)

    work page 2013

  36. [36]

    Jiang, X

    J. Jiang, X. Sun, S.-H. Teng, B. Wu, K. Wu, and J. Zhang, Optimal space-depth trade-off of cnot circuits in quantum logic synthesis, in Proceedings of the Four- teenth Annual ACM-SIAM Symposium on Discrete Algo- rithms (SIAM, 2020) pp. 213–229

    work page 2020

  37. [37]

    Zhang, Q

    Z. Zhang, Q. Wang, and M. Ying, Parallel quantum al- gorithm for hamiltonian simulation, Quantum 8, 1228 (2024)

    work page 2024

  38. [38]

    J. M. Martyn, Z. M. Rossi, K. Z. Cheng, Y. Liu, and I. L. Chuang, Parallel quantum signal processing via poly- nomial factorization, arXiv preprint arXiv:2409.19043 10.48550/arXiv.2409.19043 (2024)

    work page doi:10.48550/arxiv.2409.19043 2024

  39. [39]

    Y. Quek, E. Kaur, and M. M. Wilde, Multivariate trace estimation in constant quantum depth, Quantum 8, 1220 (2024)

    work page 2024

  40. [40]

    L. Cui, T. Schuster, F. Brandao, and H.-Y. Huang, Uni- tary designs in nearly optimal depth, arXiv preprint arXiv:2507.06216 (2025)

    work page arXiv 2025

  41. [41]

    Giurgica-Tiron, I

    T. Giurgica-Tiron, I. Kerenidis, F. Labib, A. Prakash, 8 and W. Zeng, Low depth algorithms for quantum ampli- tude estimation, Quantum 6, 745 (2022)

    work page 2022

  42. [42]

    Rall and B

    P. Rall and B. Fuller, Amplitude Estimation from Quan- tum Signal Processing, Quantum 7, 937 (2023)

    work page 2023

  43. [43]

    D.-L. Vu, B. Cheng, and P. Rebentrost, Low-depth am- plitude estimation without really trying, ACM Trans. Quantum Comput. 10.1145/3748666 (2025)

    work page doi:10.1145/3748666 2025

  44. [44]

    G. H. Low and I. L. Chuang, Optimal hamiltonian sim- ulation by quantum signal processing, Phys. Rev. Lett. 118, 010501 (2017)

    work page 2017

  45. [45]

    D. Cruz, R. Fournier, F. Gremion, A. Jeannerot, K. Komagata, T. Tosic, J. Thiesbrummel, C. L. Chan, N. Macris, M.-A. Dupertuis, et al., Efficient quantum al- gorithms for ghz and w states, and implementation on the ibm quantum computer, Adv. Quantum Technol. 2, 1900015 (2019)

    work page 2019

  46. [46]

    G. J. Mooney, G. A. White, C. D. Hill, and L. C. Hollenberg, Generation and verification of 27-qubit greenberger-horne-zeilinger states in a superconducting quantum computer, J. Phys. Commun. 5, 095004 (2021)

    work page 2021

  47. [47]

    J. I. Cirac, A. Ekert, S. F. Huelga, and C. Macchiavello, Distributed quantum computation over noisy channels, Phys. Rev. A 59, 4249 (1999)

    work page 1999

  48. [48]

    Generalized GHZ States and Distributed Quantum Computing

    A. Yimsiriwattana and S. J. Lomonaco Jr, General- ized ghz states and distributed quantum computing, arXiv preprint quant-ph/0402148 10.48550/arXiv.quant- ph/0402148 (2004)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.quant- 2004

  49. [49]

    Van Meter, K

    R. Van Meter, K. Nemoto, W. Munro, and K. M. Itoh, Distributed arithmetic on a quantum multicomputer, ACM SIGARCH Comput. Archit. News 34, 354 (2006)

    work page 2006

  50. [50]

    Beals, S

    R. Beals, S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, Efficient dis- tributed quantum computing, Proc. R. Soc. A: Math. Phys. Eng. Sci. 469, 20120686 (2013)

    work page 2013

  51. [51]

    Caleffi, M

    M. Caleffi, M. Amoretti, D. Ferrari, J. Illiano, A. Man- zalini, and A. S. Cacciapuoti, Distributed quantum com- puting: a survey, Comput. Netw. 254, 110672 (2024)

    work page 2024

  52. [52]

    Barral, F

    D. Barral, F. J. Cardama, G. Diaz-Camacho, D. Fa´ ılde, I. F. Llovo, M. Mussa-Juane, J. V´ azquez-P´ erez, J. Vil- lasuso, C. Pi˜ neiro, N. Costas, et al. , Review of dis- tributed quantum computing: from single qpu to high performance quantum computing, Comput. Sci. Rev. 57, 100747 (2025)

    work page 2025

  53. [53]

    G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019)

    work page 2019

  54. [54]

    S. Uno, Y. Suzuki, K. Hisanaga, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Modified grover opera- tor for quantum amplitude estimation, New J. Phys. 23, 083031 (2021)

    work page 2021

  55. [55]

    Braun, T

    M. Braun, T. Decker, N. Hegemann, and S. Ker- stan, Error resilient quantum amplitude estimation from parallel quantum phase estimation, arXiv preprint arXiv:2204.01337 10.48550/arXiv.2204.01337 (2022)

    work page doi:10.48550/arxiv.2204.01337 2022

  56. [56]

    G. H. Low, Quantum signal processing by single-qubit dy- namics, Ph.D. thesis, Massachusetts Institute of Technol- ogy (2017)

    work page 2017

  57. [57]

    J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX quantum 2, 040203 (2021)

    work page 2021

  58. [58]

    Gily´ en, S

    A. Gily´ en, S. Arunachalam, and N. Wiebe, Optimiz- ing quantum optimization algorithms via faster quan- tum gradient computation, in Proceedings of the Thir- tieth Annual ACM-SIAM Symposium on Discrete Algo- rithms (SIAM, 2019) pp. 1425–1444

    work page 2019

  59. [59]

    Higgins, D

    B. Higgins, D. Berry, S. Bartlett, M. Mitchell, H. Wise- man, and G. Pryde, Demonstrating heisenberg-limited unambiguous phase estimation without adaptive mea- surements, New J. Phys. 11, 073023 (2009)

    work page 2009

  60. [60]

    Belliardo and V

    F. Belliardo and V. Giovannetti, Achieving heisenberg scaling with maximally entangled states: An analytic upper bound for the attainable root-mean-square error, Phys. Rev. A 102, 042613 (2020)

    work page 2020

  61. [61]

    M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information (Cambridge university press, 2010)

    work page 2010

  62. [62]

    Quantum computing with Qiskit

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum computing with Qiskit (2024), arXiv:2405.08810 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  63. [63]

    R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy, Finding angles for quantum signal processing with machine precision, arXiv preprint arXiv:2003.02831 10.48550/arXiv.2003.02831 (2020)

    work page doi:10.48550/arxiv.2003.02831 2003

  64. [64]

    https://github.com/alibaba-edu/angle-sequence

    work page

  65. [65]

    Koizumi, K

    Y. Koizumi, K. Wada, W. Mizukami, and N. Yoshioka, Comprehensive study on heisenberg-limited quantum algorithms for multiple observables estimation, arXiv preprint arXiv:2505.00698 10.48550/arXiv.2505.00698 (2025)

    work page doi:10.48550/arxiv.2505.00698 2025

  66. [66]

    Zalka, Grover’s quantum searching algorithm is opti- mal, Phys

    C. Zalka, Grover’s quantum searching algorithm is opti- mal, Phys. Rev. A 60, 2746 (1999)

    work page 1999

  67. [67]

    Lower bounds for parallel quantum counting

    P. Burchard, Lower bounds for parallel quan- tum counting, arXiv preprint arXiv:1910.04555 10.48550/arXiv.1910.04555 (2019)

    work page doi:10.48550/arxiv.1910.04555 1910

  68. [68]

    Motlagh and N

    D. Motlagh and N. Wiebe, Generalized quantum signal processing, PRX Quantum 5, 020368 (2024)

    work page 2024

  69. [69]

    D. W. Berry, D. Motlagh, G. Pantaleoni, and N. Wiebe, Doubling the efficiency of hamiltonian simulation via gen- eralized quantum signal processing, Phys. Rev. A 110, 012612 (2024)

    work page 2024

  70. [70]

    fully parallel

    J. Haah, Product decomposition of periodic functions in quantum signal processing, Quantum 3, 190 (2019). 9 SUPPLEMENT AL MA TERIAL S1. COMP ARISON WITH OTHER QAE Table S1 summarizes the comparison of PAE with prior QAEs in terms of the number of qubits, maximum circuit depth, and query complexity. Here, n denotes the number of qubits on which Ua acts. εa...

    work page 2019

  71. [71]

    Derive estimate \Mkφ′ k := atan2(2fi,k − 1, 2f+,k − 1) ∈ [0, 2π), where Mk = 2k−1

    work page

  72. [72]

    As shown in Fig

    Calculate bφ′ k,0 := \Mkφ′ k/Mk ∈ [0, 2π/Mk). As shown in Fig. S1, bφ′ k,0 represents the smallest candidate for bφ′ k in the range [0 , 2π)

    work page

  73. [73]

    If k > 1, select bφ′ k from the candidate estimates {bφ′ k,m = bφ′ k,0 + mπ/2k−2}2k−1 m=−1 based on the previous estimate bφ′ k−1

    If k = 1, adopt bφ′ 0,1 as bφ′ 1. If k > 1, select bφ′ k from the candidate estimates {bφ′ k,m = bφ′ k,0 + mπ/2k−2}2k−1 m=−1 based on the previous estimate bφ′ k−1. First, compute the partition index η := bφ′ k−1/2−k+2π ∈ {0, 1, ...,2k−1 −1}, which identifies the partition in which bφ′ k−1 lies (see Fig. S1). Then, select bφ′ k from the candidate estimate...

    work page

  74. [74]

    The final estimate bφ is given by bφK

    Map bφ′ k onto [−π, π) to obtain bφk. The final estimate bφ is given by bφK. Figure S1 schematically illustrates the above estimation procedure. 𝜑ොଵ, ଴ᇱ𝜑ොଶ, ଴ᇱ𝜑ොଶ, ଵᇱ𝑘= 1𝑘= 2𝑘= 3・・・𝜑ොଶ, ିଵᇱ 𝜑ොଶ, ଶᇱ𝜑′0 2𝜋𝜑ොଷ, ଶᇱ 𝜑ොଷ, ସᇱ𝜑ොଷ, ଴ᇱ𝜑ොଷ, ିଵᇱ𝜋/3𝜋/6𝜋/12𝜑ොଷ, ଵᇱ 𝜑ොଷ, ଷᇱ𝜂= 0𝜂= 0𝜂= 1𝜂= 2𝜂= 3𝜂= 1𝜂= 0 FIG. S1. Schematic diagram of the step-by-step estimation of φ in RPE....

    work page