Kavli Affiliate: Feng Wang
| First 5 Authors: Yunpeng Zhao, Haiyan Wang, Kuai Xu, Yue Wang, Ji Zhu
| Summary:
Quantum amplitude estimation is a key sub-routine of a number of quantum
algorithms with various applications. We propose an adaptive algorithm for
interval estimation of amplitudes. The quantum part of the algorithm is based
only on Grover’s algorithm. The key ingredient is the introduction of an
adjustment factor, which adjusts the amplitude of good states such that the
amplitude after the adjustment, and the original amplitude, can be estimated
without ambiguity in the subsequent step. We show with numerical studies that
the proposed algorithm uses a similar number of quantum queries to achieve the
same level of precision $epsilon$ compared to state-of-the-art algorithms, but
the classical part, i.e., the non-quantum part, has substantially lower
computational complexity. We rigorously prove that the number of oracle queries
achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo
sampling, and the computational complexity of the classical part achieves
$O(log(1/epsilon))$, both up to a double-logarithmic factor.
| Search Query: ArXiv Query: search_query=au:”Feng Wang”&id_list=&start=0&max_results=10