1 Introduction
2 Preliminary
3 Amplitude estimation without phase estimation
3.1 Algorithm
3.2 Statistics: Cramér–Rao bound and Fisher information
- Linearly incremental sequence (LIS): \(N_k=N_{\mathrm{shot}}\) for all k, and \(m_k=k\), i.e., it increases as \(m_0=0, m_1=1, m_2=2, \ldots , m_M=M\).
- Exponentially incremental sequence (EIS): \(N_k=N_{\mathrm{shot}}\) for all k, and \(m_k\) increases as \(m_0=0, m_1=2^0, m_2=2^1,\ldots , m_M=2^{(M-1)}\).
3.3 Numerical simulation
Update rule of \(m_k\) | Query complexity | Computational complexity of post-processing |
---|---|---|
Classical (\(m_k=0 \forall k\)) | \({{\mathscr {O}}}(\varepsilon ^{-2})\) | \({{\mathscr {O}}}(\varepsilon ^{-2})\) |
Linearly incremental sequence (LIS) (\(m_0=0,m_1=1,m_2=2,\ldots ,m_M=M\)) | \({{\mathscr {O}}}(\varepsilon ^{-4/3})\) | \({{\mathscr {O}}}(\varepsilon ^{-5/3})\) |
Exponentially incremental sequence (EIS) (\(m_0=0,m_1=2^0,m_2=2^1,\ldots ,m_M=2^{(M-1)}\)) | \({{\mathscr {O}}}(\varepsilon ^{-1})\) | \({{\mathscr {O}}}(\varepsilon ^{-1}\ln \varepsilon ^{-1})\) |
4 Application to the Monte Carlo integration
4.1 The Monte Carlo integration as an amplitude estimation
4.2 Simple example: integral of the sine function
# Operators \({\mathbf {Q}}\) | Conventional amplitude estimation | Our algorithm | ||
---|---|---|---|---|
# CNOT gates | # Qubits | # CNOT gates | # Qubits | |
0 | – | – | 4 | 3 |
\(2^0\) | 135 | 7 | 18 | 3 |
\(2^1\) | 399 | 8 | 32 | 3 |
\(2^2\) | 927 | 9 | 60 | 3 |
\(2^3\) | 1981 | 10 | 116 | 3 |
\(2^4\) | 4085 | 11 | 228 | 3 |
\(2^5\) | 8287 | 12 | 452 | 3 |
\(2^6\) | 16,683 | 13 | 900 | 3 |
\(2^7\) | 33,465 | 14 | 1796 | 3 |
\(2^8\) | 67,017 | 15 | 3588 | 3 |