---
tags: amplitude estimation, grover, quantum computing, 2019, QIP2019
---

# [Amplitude estimation without phase estimation](https://arxiv.org/abs/1904.10246)
Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, Naoki Yamamoto

## Abstract
This paper focuses on the quantum amplitude estimation algorithm, which is a core subroutine in quantum computation for various applications. The conventional approach for amplitude estimation is to use the phase estimation algorithm, which consists of many controlled amplification operations followed by a quantum Fourier transform. However, the whole procedure is hard to implement with current and near-term quantum computers. In this paper, we propose a quantum amplitude estimation algorithm without the use of expensive controlled operations; the key idea is to utilize the maximum likelihood estimation based on the combined measurement data produced from quantum circuits with different numbers of amplitude amplification operations. Numerical simulations we conducted demonstrate that our algorithm asymptotically achieves nearly the optimal quantum speedup with a reasonable circuit length.

## 背景
Amplitude EstimationはGrover探索+QFTで実現されるが、ゲート数(特に制御ゲート数)や使用するqubit数が多いことが問題だった(当然、GroverもQFTもQRAM上での実行を考えているのでNISQデバイスでは実行できない)。
そこで、Amplitude EstimationでQFTを回避する手法をこの論文で提案した。

## お気持ち
Amplitude EstimationでControlled Grover IterationとQFTを使う代わりに違う回数のGrover Iterationを適用した回路それぞれで測定を行なって、それを尤度関数に変更、その積に対するargmaxのthetaを取ると誤差がgrover iteratorの数Nqに対して1/Nq (← 1/sqrt(Nq) でないことがポイント) のスケールで収束することができる
- 回路が1つだと周期的なのでどのthetaなのかわからない
- Grover Iterationを1回だけでもthetaは推定できるけど誤差の収束速度や誤差の大きさにquantum advantageがない

→ 回路ごとに違う回数のGrover Iterationを適用

## Comments

This paper avoided using QFT in amplitude ampification, which would drastically decrease the controlled gate in the circuit, allowing it more available to NISQ devices.