Cryoris
commented
3 years ago Actually, after looking into this more the algorithm is not really practical since it needs way too many circuit evaluations (see Fig. 3 of https://arxiv.org/pdf/1912.05559.pdf). Even if we would implement it it probably wouldn't finish in sensible time.
Description
Amplitude estimation is a quantum algorithm that is able to approximate the probability to measure a certain state in a provided quantum state.
This is a very important algorithm with practical applications, such as computing integrals or expectation values. The latter makes it particularly interesting for finance and option pricing!
In 2019, Aaronson et al (yes the guy from the famous Shtetl-optimized blog) presented an amplitude estimation algorithm with optimal complexity in the number of oracle queries/function calls, coined "Counting, Simplified". While there are several amplitude estimation algorithms implemented in Qiskit today, they don't have the same optimal asymptotic runtime.
The goal of this project is to implement the "Counting, Simplified" algorithm in Qiskit and compare it to the existing implementations. The paper to the algorithm is: : https://arxiv.org/abs/1908.10846.
Mentor/s
Julien Gacon (@Cryoris), Pre-Doc researcher at IBM Research Zurich, Qiskit Terra and Aqua core developer
Type of participant
You should be familiar with Python and some of Qiskit's algorithms. Ideally, you even played with the amplitude estimation algorithms before or even read the paper above!
Number of participants
1
Deliverable
A PR to Qiskit implementing the algorithm.