Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal

• URL: http://arxiv.org/abs/2208.14612v2
• Date: Mon, 14 Nov 2022 19:46:37 GMT
• Title: Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal
• Authors: Shion Fukuzawa, Christopher Ho, Sandy Irani, Jasen Zion
• Abstract summary: We provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) QAE algorithms appear as a subroutine in many applications for quantum computers.
• Score: 0.37798600249187286
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is $O\left(\frac{1}{\epsilon}\log \frac{1}{\alpha}\right)$ queries, providing a speedup of a factor of $1/\epsilon$ over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) was introduced by Grinko et al. with a near-optimal $O\left(\frac{1}{\epsilon}\log \left(\frac{1}{\alpha} \log \frac{1}{\epsilon}\right)\right)$ query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal $O\left(\frac{1}{\epsilon}\log \frac{1}{\alpha}\right)$ query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.

Related papers

• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  We introduce a quantum algorithm for reducing classical optimization problems to classical decoding problems. We show that DQI achieves a better approximation ratio than any quantum-time classical algorithm known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• High-precision and low-depth eigenstate property estimation: theory and resource estimation [2.6811507121199325]
  Estimating the eigenstate properties of quantum many-body systems is a long-standing, challenging problem for both classical and quantum computing. Here, we present a full-stack design of a random sampling algorithm for estimating the eigenenergy and the observable expectations on the eigenstates.
  arXiv  Detail & Related papers  (2024-06-06T17:54:26Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• Quantum Phase Estimation by Compressed Sensing [0.0]
  We present a new Heisenberg-limited quantum phase estimation algorithm for early quantum computers based on compressed sensing. Our algorithm is able to recover the frequency with a total runtime $mathcalO(epsilon-1textpolylog(epsilon-1))$, where $epsilon$ is the accuracy. We also consider the more general quantum eigenvalue estimation problem (QEEP) and show numerically that the off-grid compressed sensing can be a strong candidate for solving the QEEP.
  arXiv  Detail & Related papers  (2023-06-12T10:21:59Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing. Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization [33.12181620473604]
  We study a Fitted Q-Iteration with two-layer ReLU neural network parametrization, and find the sample complexity guarantees for the algorithm. We show that this approach achieves a sample complexity of $tildemathcalO (1/epsilon2)$, which is order-optimal.
  arXiv  Detail & Related papers  (2022-11-14T19:00:24Z)
• Study of Adaptative Derivative-Assemble Pseudo-Trotter Ansatzes in VQE through qiskit API [0.0]
  Variational Quantum Algorithms (VQAs) were designed to answer the problem of Quantum Phase Estimation Algorithm. ADAPT-VQE determines a quasi-optimal ansatz with a minimal number of parameters. We will compare all of these algorithms on different criterions such as the number of parameters, the accuracy or the number of CNOT gate used on H2 and LiH molecules.
  arXiv  Detail & Related papers  (2022-10-25T16:53:14Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.