Quantum amplitude estimation from classical signal processing

• URL: http://arxiv.org/abs/2405.14697v1
• Date: Thu, 23 May 2024 15:31:46 GMT
• Title: Quantum amplitude estimation from classical signal processing
• Authors: Farrokh Labib, B. David Clader, Nikitas Stamatopoulos, William J. Zeng,
• Abstract summary: We show that the problem of amplitude estimation can be mapped directly to a problem in signal processing called direction of arrival estimation. We create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a total query complexity of $sim 4.9/varepsilon$ and a parallel query complexity of $sim 0.40/varepsilon$ at 95% confidence.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a total query complexity of $\sim 4.9/\varepsilon$ and a parallel query complexity of $\sim 0.40/\varepsilon$ at 95% confidence. This performance is a factor of $1.1\times$ and $14\times$ improvement over Rall and Fuller [Quantum 7, 937 (2023)], for worst-case complexity, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.

Related papers

• Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
  We establish the global convergence of the actor-critic algorithm with a significantly improved sample complexity of $O(epsilon-3)$. Our findings provide theoretical support for many algorithms that rely on constant step sizes.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• 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)
• Few Quantum Algorithms on Amplitude Distribution [0.5584060970507505]
  Amplitude filtering is concerned with identifying basis-states in a superposition whose amplitudes are greater than a specified threshold. Given the scarcity of qubits, the focus of this work is to design log-space algorithms for them.
  arXiv  Detail & Related papers  (2022-07-30T08:11:29Z)
• Amplitude Estimation from Quantum Signal Processing [0.30458514384586405]
  Amplitude estimation algorithms are based on Grover's algorithm: alternating reflections about the input state and the desired outcome. We find that quantum signal processing lets us estimate the amplitude in a more flexible way.
  arXiv  Detail & Related papers  (2022-07-18T14:22:10Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  We propose an adaptive algorithm for interval estimation of amplitudes. The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision. We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
  arXiv  Detail & Related papers  (2022-06-16T21:11:15Z)
• Low depth amplitude estimation on a trapped ion quantum computer [5.443245599372994]
  Amplitude estimation is a fundamental quantum algorithmic primitive that enables quantum computers to achieve quadratic speedups. Recent works have succeeded in somewhat reducing the necessary resources for such algorithms, by trading off some of the speedup for lower depth circuits. We report the results of an experimental demonstration of amplitude estimation on a state-of-the-art trapped ion quantum computer.
  arXiv  Detail & Related papers  (2021-09-20T16:57:19Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.